hitchhiker-tree

Here're what I found on the idea of adding buffers to branch nodes. L. Arge described the Buffer Tree idea in 1995 with (a,b)-Tree for other data structures. Brodal and Fagerberg formalized it for B+Tree in 2003. There's also the more modern Bε-Tree, the B-epsilon Tree, with similar idea, used in the BetrFS file system and various DBs. Tokutek built TokuDB using a similar idea and called it Fractal Tree (which was derived from Bε-Tree). Hitchhicker Tree is the append-only version of Fractal Tree, similar to the append-only B+Tree. * L. Arge. The buffer tree: A new technique for optimal I/O-algorithms. In Proc. 4th Workshop on Algorithms and Data Structures (WADS), volume 955 of Lecture Notes in Computer Science, pages 334–345, Springer Verlag, Berlin. 1995. https://link.springer.com/chapter/10.1007/3-540-60220-8_74 * G. S. Brodal, R

This project might be of interest actually https://github.com/datacrypt-project/hitchhiker-tree

I don't understand the difference between this data structure [0] and buffered B-trees, as described in "Lower Bounds for External Memory Dictionaries", by Gerth Stølting Brodal and Rolf Fagerberg [1], or in "On External Memory Graph Traversal" by Adam L. Buchsbaum, Michael Goldwasser, Suresh Venkatasubramanian, and Jeffery R. Westbrook [2]. Granted, this adds in path-copying, but I'm not sure what new innovation this has that merits the description "Hitchhiker trees are a newly invented (by @dgrnbrg) datastructure". 0: https://github.com/datacrypt-project/hitchhiker-tree/blob/ma... 1: http://www.cs.au.dk/~gerth/papers/alcomft-tr-03-75.pdf 2: http://euler.slu.edu/~goldwasser/publications/SODA2000.pdf