On Thu, Jan 4, 2018 at 6:05 PM, Alvaro Herrera <alvhe...@alvh.no-ip.org> wrote:
> Pavan Deolasee wrote: > > On Tue, Jan 2, 2018 at 7:15 PM, Tels <nospam-pg-ab...@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. > > 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
