Huh. I'd love to see B-trees thrown in there. Especially using some of the tricks in the excellent "Algorithms for Modern Hardware" book:

https://en.algorithmica.org/hpc/data-structures/b-tree/

I’m surprised the run time doesn’t spike harder than this as they exceed L1 and L2 cache sizes. I expected the 40 bytes per node algorithm to be punished more heavily.

Or maybe that calls the benchmarks into suspicion.

In case it's interesting to others: This piece is written by Willy Tarreau, who is also the author of the HAProxy software load balancer! I did a double take when I saw the page header.