Re: Faster inserts with mostly-monotonically increasing values

Hello Alvaro,

On Thu, January 4, 2018 7:35 am, Alvaro Herrera wrote:
> Pavan Deolasee wrote:
>> On Tue, Jan 2, 2018 at 7:15 PM, Tels <nospam-pg-abuse(at)bloodgate(dot)com>
>> wrote:
>>
>> > Just a question trying to understand how btree indexes work:
>> >
>> > If one inserts ever-increasing value, is the tree a balanced tree with
>> a
>> > minimum (or at least not-as-high) number of levels, or does it
>> increase in
>> > height every insert and creates a "tall stack"?
>>
>> AFAIK all pages will be half-filled in this case. Imagine if one index
>> page
>> can accommodate N entries, the page will be split when (N+1)th entry is
>> added. The left page will have half the entries and the right page will
>> get
>> the remaining. The next split will happen when the right page is full
>> i.e.
>> when another N/2 entries are added. Thus there will be a split at every
>> N/2
>> inserts, creating an index with half filled pages.
>
> Not really -- quoth _bt_findsplitloc():
>
> * If the page is the rightmost page on its level, we instead try to
> arrange
> * to leave the left split page fillfactor% full. In this way, when we
> are
> * inserting successively increasing keys (consider sequences, timestamps,
> * etc) we will end up with a tree whose pages are about fillfactor% full,
> * instead of the 50% full result that we'd get without this special case.
>
>
> To answer Tels question: the tree is balanced by splitting pages and
> propagating the splits upwards to the parent pages, all the way up to
> the root. When the root page gets full, it is also split and a new root
> is created on top of the old root plus its new sibling page, which is
> the only point at which the tree grows in depth.

Thank you for the explanation! You learn something new every time :)

All the best,

Tels