Re: Faster inserts with mostly-monotonically increasing values

Pavan Deolasee wrote:
> On Tue, Jan 2, 2018 at 7:15 PM, Tels <nospam-pg-abuse@bloodgate.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.