3 ms·

In the same way that B-trees have emerged as a more cache friendly version of binary trees, it seems like you could create a Fenwick tree that stores multiple “

In the same way that B-trees have emerged as a more cache friendly version of binary trees, it seems like you could create a Fenwick tree that stores multiple “children” at the same location. It would probably be less algorithmically beautiful, but would be faster over all.

kadoban 2y ago
I am not sure that is something worth trying. In practice Fenwick trees are array-encoded, in memory they're just an array you index into. The reason B-trees are used is kind of because you can't do that with a dynamic binary tree.
- 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 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 ago
        The 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 ago
      The eytzinger layout cannot be used for anything dynamic. B-Trees are dynamic structures.
      - kadoban 2y ago
        The discussion is about Fenwick trees.

kadoban 2y ago

I am not sure that is something worth trying. In practice Fenwick trees are array-encoded, in memory they're just an array you index into. The reason B-trees are used is kind of because you can't do that with a dynamic binary tree.

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 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 ago
      The 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 ago
    The eytzinger layout cannot be used for anything dynamic. B-Trees are dynamic structures.
    - kadoban 2y ago
      The discussion is about Fenwick trees.