B-Tree  Index

A B-tree is a special data structure format for an index that allows rapid access of the data in the index. One of the properties of this data structure is that the index is always balanced. That means that each node at the lowest level is equidistant from the top most node, or the root node of the tree. And each side of the index has the same number of nodes. The nodes at the lowest levels are known as leaf nodes. All other nodes are known as branch nodes. Branches point to other branches or leaf nodes. Leaf nodes store value-rowid pairs, or the values of the indexed columns and the rowid that points to a distinct row that has those values.  The actual distribution will depend on the number of data values in each range of values in a B-tree with the overall goal to reduce the number of required levels that must be traversed to get to a specific value. The advantages of a B-tree structure are:

• All leaf blocks are of the same depth (number of values).
   
• The height of the B-tree, or the total number of nodes from the root to any leaf, is typically pretty small. In some cases, the root node is the only leaf node and the height is 1. As the table gets more rows inserted into it, the index must grow to accommodate this. But even in tables with over 1 million rows, the B-tree index typically has a height of 3. In the very largest of tables, the height may only be 4. This means that for even the largest of tables, it only takes 4 blocks to find the rowid of the row you are looking for. This is extremely efficient.
   
• In the case of randomly entered data, the B-tree stays balanced automatically. In fact, the B-tree stays balanced no matter what data is entered into it.
   
• All blocks of a B-tree index are three-quarters full (on the average), allowing insertion without rebuild.
   
• B-trees provide excellent performance for all types of selects.
   
• Insert, update, and deletes tend to be efficient in a B-tree structure.
   
• B-tree performance stays optimal even when tables vary from small to large.
• OLAP databases we will B-tree indexes