Re:Coding tricks I learnt at Apple
by jamn on Saturday June 11, 2011 @04:29AM
(#2643475)
B-Trees actually have superior cache performance compared to other types of trees (such as T-Trees or BST Trees). In part, this is because B-Trees have a higher density of actual data to pointers.
There is a tradeoff of computation (doing binary search inside the node) and amount of storage (keeping less pointers). In environments where memory access is much more expensive than a CPU instruction, it is preferable to perform these computations than to have to read all the extra pointer data to jump to the right places.
In fact, a breed of cache-friendly data structures are precisely based on the B+Trees but with even less pointers, having the algorithm compute these pointers instead (CSS-, CSB-Trees)
There is a tradeoff of computation (doing binary search inside the node) and amount of storage (keeping less pointers). In environments where memory access is much more expensive than a CPU instruction, it is preferable to perform these computations than to have to read all the extra pointer data to jump to the right places.
In fact, a breed of cache-friendly data structures are precisely based on the B+Trees but with even less pointers, having the algorithm compute these pointers instead (CSS-, CSB-Trees)