B-Tree
A wide, shallow search tree tuned for block storage. Nodes hold many keys.
B-Tree: Four keys per node, fewer splits
3 8 15 27 40 has 5 keys and the limit is 4, so it splits. The middle key, 15, moves up to the parent. The keys below it form the left node and the keys above it the right node.
Cost
- Search
- O(log n)
- Insert
- O(log n)
- Delete
- O(log n)
- Space
- O(n)
Height is O(log_t n) for minimum degree t. Disk reads scale with height.
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
B-Tree covers these too, in the same run.