Structure diff from B-tree
Internal nodes: only keys + children pointers. Leaves: keys + actual values (or pointers). Leaves linked left-to-right.
Advertisement
Range query
Descend to leftmost key. Walk the linked leaf list. O(log N + K) where K = matches.
Advertisement
Redundant keys
Routing keys in internal nodes are duplicated in leaves. Slight space overhead, big query benefit.
Splits + merges
Similar to B-tree but only leaf splits actually store data. Internal splits just move routing keys.