Let’s Invent B(+)-Trees
Interesting. :-)I recently posted a brief document I wrote about a similar structure, immutable AVL trees. I find AVL trees a very nifty structure, I think they don't get as much credits as they deserve: logn (which in practice is about the same as "constant" for most values of n one encounters in practice) insertion, lookup, deletion and even append (for position-based trees, with some assumptions). Incredibly simple implementation. And, if immutable (based on shared memory), allows trivial snapshotting, having multiple "concurrent" trees sharing most of their memory.Anyhow, it's here: https://github.com/alefore/weblog/blob/master/immutable-avl-...I have a small implementation here (which I use, among other things, to hold all lines in a file, in my text editor): https://github.com/alefore/edge/blob/master/src/const_tree.h