The B-tree
Characteristics:
- Multi-way tree:
- Very high branching factor, typically 100-200.
- So height is typically log100(N).
- A 3-level tree can index 1 million records.
- Balance: Always perfectly balanced.
- Storage utilization: Nodes are 50-100% full,
average is 70%.
|