Part 6 · 1 chapters · ~8 min

Data Structures Behind Storage

The B-tree family (B, B+, B*) with height and fanout maths, LSM trees and read, write and space amplification, the RUM conjecture, hash indexes with extendible and linear hashing, skip lists, Bloom, counting Bloom and cuckoo filters with false-positive maths, HyperLogLog error bounds, tries, radix trees and ART, and fractal trees and Bε-trees.

12

The maths

code
B+tree height:        h = ⌈log_f(N)⌉,  f ≈ 500 for 16 KB pages → N = 10^9 needs h = 4 (500^4 = 6.25 × 10^10)
Bloom false positives: p ≈ (1 - e^(-kn/m))^k, best k = (m/n) ln 2 → 9.6 bits per key for p = 1%
HyperLogLog:          standard error ≈ 1.04 / √m registers; Redis uses m = 16,384 → ≈ 0.81%
                      (Algorithms course measured 0.40% on one million ids: within the bound)
skip list:            expected height log_{1/p} n, expected search O(log n) for promotion probability p
LSM, leveled:         write amplification ≈ T per level × L levels; space amplification ≈ 1 + 1/T
STRUCTURES BEHIND STORAGE, FORMALLY
the RUM conjecture: optimise two of read, update, memory
B+treeHeight log_f(N): fanout ~500 gives3-4 levels for billions of keys.LSM treeWrite amplification O(T·L)leveled; read amplificationreduced by Bloom filters.hashingExtendible and linear hashing growwithout full rehash.tries and ARTAdaptive radix trees:memory-efficient ordered in-memoryindexes.Bε-treesBuffers in internal nodes batchwrites: between B-tree and LSM.sketchesBloom: (1 - e^(-kn/m))^k falsepositives; HyperLogLog: ~1.04/√merror.
swipe the figure sideways, or tap expand for full screen
1/4
the RUM conjecture
Athanassoulis et al. (2016): an access method can optimise at most two of read overhead, update overhead and memory overhead. B-trees favour reads, LSM trees favour updates, sketches favour memory.
read, update, memory: pick twoevery structure is a choice