3 ms·
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.
by ww520 3y ago
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 https://link.springer.com/chapter/10.1007/3-540-60220-8_74
* G. S. Brodal, R. Fagerberg. Lower Bounds for External Memory Dictionaries. 2003. https://cs.au.dk/~gerth/papers/soda03.pdf https://cs.au.dk/~gerth/papers/soda03.pdf
* Bε-Tree, https://www.betrfs.org/ https://www.betrfs.org/, https://www.youtube.com/watch?v=fBt5NuNsoII https://www.youtube.com/watch?v=fBt5NuNsoII. An Introduction to Bε-trees and Write-Optimization, http://supertech.csail.mit.edu/papers/BenderFaJa15.pdf http://supertech.csail.mit.edu/papers/BenderFaJa15.pdf, https://www.youtube.com/watch?v=v_g4eZeWAng&t=15s https://www.youtube.com/watch?v=v_g4eZeWAng&t=15s
* Tokutek. How Fractal Trees Work. 2011. https://www.percona.com/blog/wp-content/uploads/2011/11/how-fractal-trees-work.pdf https://www.percona.com/blog/wp-content/uploads/2011/11/how-...
* Hitchhiker Tree. 2016. https://github.com/datacrypt-project/hitchhiker-tree https://github.com/datacrypt-project/hitchhiker-tree