§ 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
The Ubiquitous B-Tree, Douglas Comer, 1979 (pdf)
Modern B-Tree Techniques, G Graefe, 2011 (pdf)
Prefix B-Trees, Rudol Bayer, 1977 (pdf)