Index - Btree structure (Balanced Tree)
1 - 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
- B in B*tree does not stand for binary but rather for balanced.
- A B*tree is not a binary tree at all
2 - Articles Related
3 - 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.