B-Tree Resources

Open a PR if you've got a resource you think might fit in.

Visualization

• BTrees from USFCA
• B-Trees from OpenDSA

Descriptions

• B-Trees (Pseudocode) from Open Data Structures
• B-Trees (C++) from Open Data Structures
• Insertion Into a B-Tree from UAlberta
• B Trees from Radford University
• The Ubiquitous B-Tree (1979) from Purdue University
• Database Internals (2019) by Alex Petrov
• B-trees by Shachaf Ben-Kiki
• Evolution of b-tree data structures for indexing by Dmitry Dolgov

Extensions

• Closing the B+-tree vs. LSM-tree Write Amplification Gap on Modern Storage Hardware with Built-in Transparent Compression (2022)
• The Bw-Tree: A B-tree for New Hardware Platforms (2017)
• An Introduction to Bε-trees and Write-Optimization (2015)

Array Layouts

• Array Layouts for Comparison-Based Searching
• Eytzinger Binary Search
• Implicit Static B-Trees

Surveys & Design Space

• Modern B-Tree Techniques (2011) by Goetz Graefe

Comparison & Critique

• Btree vs LSM by MongoDB

Implementations & Discussion

• Rust Collections Case Study: BTreeMap
• B-tree Ordered Containers (2019) from Abseil
• C++ containers that save memory and time (2013) from Google

Guided Implementation

• CMU Database Systems B+ Tree Project