B-tree variants
B+-tree vs. B-tree
B+-tree advantages
- Key-only is smaller than (key, value). Often a lot smaller.
- B+-tree internal nodes store keys only, so more of them fit on a page.
- So the branching factor is higher.
Example:
- 4k pages
- 8-byte key
- 8-byte value
- 70% average storage utilization: 2867 bytes per page
Branching factors:
- B-tree: 2867 / (8 + 8) = 179
- B+-tree: 2867 / 8 = 358
|