Re: Faster inserts with mostly-monotonically increasing values

On Thu, Jan 4, 2018 at 6:05 PM, Alvaro Herrera <alvherre(at)alvh(dot)no-ip(dot)org>
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.
>
>
Ah ok. Thanks for pointing that out. Makes a lot more sense.

Thanks,
Pavan

--
Pavan Deolasee http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services