I doubt that purpose build data structures optimizing L1/L2 cache, will be slower (or even similar to ) a database running on the same machine. Assuming, of co

I doubt that purpose build data structures optimizing L1/L2 cache, will be slower (or even similar to ) a database running on the same machine. Assuming, of course, that all that's needed can be fit into memory. Databases will do much better when you need to spill to disk. There is a data structure called Judy arrays, invented by Doug Baskins. Judy array was used at some point in time in Erlang to back up its ets tables. The paper (2003) comparing various data structures for that task is here [1] http://erlang.org/workshop/2003/paper/p43-fritchie.pdf http://erlang.org/workshop/2003/paper/p43-fritchie.pdf ".... For unsorted tables with populations of 70,000 keys or more, performance improvement by using the judyeh table type instead of set is easily measurable and significant. This improvement can be seen with keys in sequential order and random order during operations involving table insertion, lookup, and counter updates. The deletion operation is not as fast as set, but deletion’s extra cost is smaller than the benefit of insertion, lookup, and update operations combined. Furthermore, the additional RAM required by judyeh tables is quite modest. The judyeh table type requires only about 6% more than set tables, which is smaller than the additional 15% required for the same data in an ordered set table. The only operation this research examines which is significantly worse for judyeh tables than set tables is table traversal using the ets:next/2 function. …". Would be interesting how Judy arrays are compared to radix