Re: Faster inserts with mostly-monotonically increasing values

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.

--
Álvaro Herrera https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services