B+ Tree
A B-tree where all values live in linked leaves, making range scans sequential.
B-Tree: B+ tree: keys stay in the chained leaves
10 20 30 has 3 keys and the limit is 2, so it splits. The middle key, 20, is copied up to the parent and stays in the right leaf. The keys below it form the left node and the keys above it the right node.
Cost
- Search
- O(log n)
- Range scan
- O(log n + k)
- Insert
- O(log n)
- Space
- O(n)
Before this
Taught by the same lesson
B-Tree covers these too, in the same run.