jump to navigation

So When Does An Oracle B-Tree Index Increase In Height ? (Almost Grown) April 3, 2008

Posted by Richard Foote in Index Height, Index statistics, Oracle General, Oracle Indexes, Oracle Myths.
59 comments

So when does an Oracle B-Tree index actually increase in height ?

I’ve basically been asked this same question a number of times over the past few days with regard to the discussions on indexes and different block sized tablespaces, so I thought it might be worth quickly sharing the answer to a wider audience.

Imagine a new, empty table and a corresponding new, empty index. At this stage, the index structure basically consists of one, empty block. The index has a BLEVEL of 0 (from DBA_INDEXES) and a HEIGHT of 1 (from INDEX_STATS), yes it can be confusing ;) This block is basically the Root block of the index as it’s the first (and currently only) block to be accessed during an index scan, but at this stage is used to also store the actual index entries as well (and so can kinda be viewed as being a Leaf block as well).

We now start to insert rows into the table and thus row entries into the index. These index entries basically consist of the indexed column(s) and its corresponding ROWID, and are sorted based on the indexed column values.

Eventually, this single index block will fill; Oracle simply can’t add any more index entries into it. Now comes the fun bit.

When Oracle wants to insert a new index entry but it can’t as this Root index block is full, Oracle will allocate two new index blocks. If the new index entry is the maximum value currently to be indexed, Oracle will move all the index entries from the full block and put it into one of the new index blocks and place the new index entry into the other block. This is known as a 90-10 index block split.

If the new index entry isn’t the maximum value, Oracle will place the lower 1/2 valued index entries into one new block and the other 1/2 into the other new block. This is known as a 50-50 index block split.

These two new blocks are now the new leaf blocks in the index structure.

The contents of the previously single filled block is now totally replaced with pointers to the two new blocks. This block therefore remains the Root block in the index structure. These pointers basically consist of the Relative Block Address (RBA) to the new index blocks and a value which represents the lowest indexed value found in the specific referenced leaf block. These indexed values in the Root block are now used by Oracle as the method by which it can navigate the index structure to find the specific index leaf block containing a required indexed entry.

The index has just increased in height and now has a BLEVEL of 1 and a HEIGHT of 2.

As we continue to add more rows into the table, we add more index entries into our 2 leaf blocks. Eventually they will fill again and will again perform either a 90-10 or 50-50 block split depending on the new index value to be inserted. With a non Root block split, only one additional index block is allocated and the index entries are distributed between the full and new index block. Each time a leaf block splits in a BLEVEL 1 index, a new entry is also added into the Root block to point to the new Leaf block. 

Once we have enough Leaf blocks, the Root block will again eventually fill. At this point, Oracle will again allocate two new blocks and distribute the contents of the Root block into these two new blocks, again 90-10 or 50-50 depending on the new indexed value to be inserted. The contents of the Root block is now totally replaced with pointers to these 2 new “Branch” blocks which of course in turn now contain the pointers to the Leaf blocks.

The index has again increased in height and we now have an index with a BLEVEL of 2 and a HEIGHT of 3.

As the leaf blocks continue fill and split, a new entry is added to the corresponding Branch block each time. When these Branch blocks fill and split, a new entry is added to the Root block. When the Root block eventually fills, it will again allocate 2 new blocks and so the index grows in height again.

So basically, an index increases in height whenever the index Root block splits and the two new allocated blocks result in a new level within the index structure. Note the index Root block remains the same throughout the entire life of the index, no matter the index height.

Note also a Root block split is the only time an index increases in height. Therefore, the number of levels between the Root block and any/all of the Leaf blocks is always and must always be the same. Hence, an Oracle B-Tree index is always structurally height balanced, always.

Follow

Get every new post delivered to your Inbox.

Join 1,703 other followers