5. Tree Indexing
5.1. Tree Indexing (1)
Linear index is poor for insertion/deletion.
Tree index can efficiently support all desired operations:
Insert/delete
Multiple search keys (multiple indices)
Key range search
5.2. Tree Indexing (2)
5.3. Tree Indexing (3)
Difficulties when storing tree index on disk:
Tree must be balanced.
Each path from root to leaf should cover few disk pages.
5.4. Tree Indexing (4)
5.5. 2-3 Tree
A 2-3 Tree has the following properties:
A node contains one or two keys
Every internal node has either two children (if it contains one key) or three children (if it contains two keys).
All leaves are at the same level in the tree, so the tree is always height balanced.
The 2-3 Tree has a search tree property analogous to the BST.
5.6. 2-3 Tree Example
The advantage of the 2-3 Tree over the BST is that it can be updated at low cost.