Let’s Invent B(+)-Trees
Interesting. :-)<p>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.<p>Anyhow, it's here: <a href="https://github.com/alefore/weblog/blob/master/immutable-avl-trees.md" rel="nofollow">https://github.com/alefore/weblog/blob/master/immutable-avl-...</a><p>I have a small implementation here (which I use, among other things, to hold all lines in a file, in my text editor): <a href="https://github.com/alefore/edge/blob/master/src/const_tree.h" rel="nofollow">https://github.com/alefore/edge/blob/master/src/const_tree.h</a>