About

B*Tree indexes :

• has a tree structure
• provides fast access, by key, to an individual row or range of rows
• normally requiring few reads to find the correct row
• are similar in implementation to a binary search tree
• there is a one-to-one relationship between an index entry and a row: an entry points to a row. Not the case of Relation - Bitmap Indexes.

The index records are stored in the leaf pages of the tree.

Structure

The lowest level blocks in the tree, called leaf nodes or leaf blocks, contain every indexed key and a rowid that points to the row it is indexing. The interior blocks, above the leaf nodes are known as branch blocks. They are used to navigate through the structure.

That makes satisfying a predicate, such as the followings, pretty simple :

• where x between 20 and 30
• where x = 30

All leaf blocks should be at the same level.