Hello Alvaro, On Thu, January 4, 2018 7:35 am, Alvaro Herrera 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. > > > 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.
Thank you for the explanation! You learn something new every time :) All the best, Tels
