You could have invented Fenwick trees

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.

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.

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.

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)

...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...