4 ms·
They are array encoded, but you still will be jumping all over the array to do your operations. Putting multiple “nodes” at the same location will mean fewer ju
by celeritascelery 2y ago
They are array encoded, but you still will be jumping all over the array to do your operations. Putting multiple “nodes” at the same location will mean fewer jumps, and hence fewer cache misses.
- o11c 2y agoThat's what the Eytzinger ordering is for. Using 1-based indexing like the article, a single lookup will only hit the following nodes: 1 2 or 3 (let's assume 2) 4 or 5 (let's assume 5) 10 or 11 Remember these are all adjacent. So the nodes near the root stay in cache (regardless of whether a path through them in particular was taken), and the other nodes are in cache if you've recently looked up a similar key. There won't be any further improvement from using a B-tree, which only scatters the memory further. (if anything, you might consider using a higher-base Eytzinger tree for SIMD reasons, but I've never actually seen anyone do this)
- kreelman 2y ago...So, could someone try putting one of these trees in place in... SQLite3 and see if it's any faster than it's use of B-Trees?.... Assuming this concept will work in C...
- kadoban 2y agoThe discussion above is nuanced, but in short: the concept doesn't work for B-Trees or as a replacement for B-Trees at all. It's for a different thing where you have a fixed set of keys (especially 1 to n or something of that form).
- rebanevapustus 2y agoThe eytzinger layout cannot be used for anything dynamic. B-Trees are dynamic structures.
- kadoban 2y agoThe discussion is about Fenwick trees.