Re: Faster inserts with mostly-monotonically increasing values

On Tue, Jan 2, 2018 at 7:15 PM, Tels <nospam-pg-abuse(at)bloodgate(dot)com> wrote:

> Moin,
>
>
> >>
> >>
> > Hmm Ok. I am not entirely sure whether it's the depth or just purely
> > binary
> > searching through 3-4 index pages and/or pinning/unpinning buffers result
> > in much overhead. I will run some more tests and collect evidences.
>
> 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.

Thanks,
Pavan

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