3 ms·
That'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 assu
by o11c 2y ago
That'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.