2 ms·
B-trees are supposed to address the bad cache behavior of binary trees because they are generally much shallower. Crit-bit trees as originally described do not
by fweimer 2y ago
B-trees are supposed to address the bad cache behavior of binary trees because they are generally much shallower. Crit-bit trees as originally described do not have this property.
- crest 2y agoYes and no. A lot of it depends on how the low fan-out tree is laid out in memory. Also some binary tree structures (e.g. binary heaps) are often stored in an array with one child implied and only the other child index stored in each node. In such cases chasing down the child references may no be more expensive that searching inside a B(+)-tree node.