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.
