3 ms·

But is it cache-friendly? Linked structures are great and all, but it seems that nowadays even in-memory B-trees might be better than overly-linked structures f

But is it cache-friendly? Linked structures are great and all, but it seems that nowadays even in-memory B-trees might be better than overly-linked structures for the same reasons B-trees were efficient for on-disk storage (less moving around = better locality). I suppose some cache-friendliness may also come from the chosen memory allocator for allocating new nodes. If objects are all the same size, a reasonably good slab allocator might continue to provide cache-friendliness. I think I need an adult! Can someone help me sort this out?

attractivechaos 6y ago
In-memory B-tree is faster and uses less memory for small keys [1]. However, intrusive binary search trees (BSTs) are much more flexible and are the right choice for implementing kernels and malloc(). In addition, intrusive BSTs are often used to organize memory blocks scattered around. In-memory B-tree would lose its cache-efficiency in this case anyway. [1] https://attractivechaos.wordpress.com/2008/09/24/b-tree-vs-binary-search-tree/ https://attractivechaos.wordpress.com/2008/09/24/b-tree-vs-b...
louai 6y ago
A characteristic of intrusive data structures is generally good cache friendliness. In this context "intrusive" means that the data structure is embedded with the data that's being stores. In C terms as in this case that means that the pointers required of individual nodes aren't allocated in separate structs and are instead embedded in one struct that also includes the payload. This means that the cache behavior is improved, as a given node is stored in a single location. Once you access a node the associated data is already in the cache, instead of having to be fetched via a separate pointer dereference.
loeg 6y ago
Not especially cache efficient compared to trees with higher branching factor, true. But intrusive data structures can be manipulated without memory allocation, such as when holding locks. That is the main reason they are useful in place of B-trees.

attractivechaos 6y ago

In-memory B-tree is faster and uses less memory for small keys [1]. However, intrusive binary search trees (BSTs) are much more flexible and are the right choice for implementing kernels and malloc(). In addition, intrusive BSTs are often used to organize memory blocks scattered around. In-memory B-tree would lose its cache-efficiency in this case anyway. [1] https://attractivechaos.wordpress.com/2008/09/24/b-tree-vs-binary-search-tree/ https://attractivechaos.wordpress.com/2008/09/24/b-tree-vs-b...

louai 6y ago

A characteristic of intrusive data structures is generally good cache friendliness. In this context "intrusive" means that the data structure is embedded with the data that's being stores. In C terms as in this case that means that the pointers required of individual nodes aren't allocated in separate structs and are instead embedded in one struct that also includes the payload. This means that the cache behavior is improved, as a given node is stored in a single location. Once you access a node the associated data is already in the cache, instead of having to be fetched via a separate pointer dereference.

loeg 6y ago

Not especially cache efficient compared to trees with higher branching factor, true. But intrusive data structures can be manipulated without memory allocation, such as when holding locks. That is the main reason they are useful in place of B-trees.