| slug | 2018-07-22-b-tree-vs-b-plus-tree | |
|---|---|---|
| id | 2018-07-22-b-tree-vs-b-plus-tree | |
| title | B tree vs. B+ tree | |
| date | 2018-07-22 11:54 | |
| comments | true | |
| tags |
|
|
| description | A B+ tree can be seen as B tree in which each node contains only keys. Pros of B+ tree can be summarized as fewer cache misses. In B tree, the data is associated with each key and can be accessed more quickly. | |
| references |
Pros of B tree
- Data associated with each key ⟶ frequently accessed nodes can lie closer to the root, and therefore can be accessed more quickly.
Pros of B+ tree
- No data associated in the interior nodes ⟶ more keys in memory ⟶ fewer cache misses
- Leaf nodes of B+ trees are linked ⟶ easier to traverse ⟶ fewer cache misses