📝§ B-tree

tags

§ Data structures

B-tree data structure is a search tree (similar to binary trees) with high branching factor. B-tree (and its variants) performs much better for high-latency memory with block reads (e.g., hard drives) because it has lower height and thus needs less read operations.

• Fractal tree index — adds a buffer for “pending” operations (optimization for writes)

• Hitchhiker tree — immutable B-tree

References

• The Ubiquitous B-Tree, Douglas Comer, 1979 (pdf)

• Modern B-Tree Techniques, G Graefe, 2011 (pdf)

• Prefix B-Trees, Rudol Bayer, 1977 (pdf)

• “Modern B-Tree techniques” by Dmitrii Dolgov (Strange Loop 2022) - YouTube

• Petrov₂₀₁₉