COMMON FOUNDATION / M08

Core Data Structures, Disk & Spatial Indexes

Master the on-disk and in-memory data structures that power storage engines, caches, routers, and telemetry pipelines: B+ trees, spatial indexes (Geohash/H3/S2/R-trees), LSM-trees, Bloom filters, consistent hashing rings, and probabilistic sketches.

5 topics360 min estimatedPublished

Every high-throughput database, cache tier, and stream processor is built upon a small set of specialized data structures designed around the physical asymmetry between CPU cache lines, DRAM, and NVMe flash pages. Choosing between a Tree and an LSM-Tree, or between an R-Tree and a discrete H3 hexagonal grid, directly dictates a storage engine’s read amplification, write amplification, and space amplification.

This chapter progresses systematically from disk-backed indexing to probabilistic memory structures. You first dissect 16 KB slotted-page Trees and two-dimensional spatial indexes (CORE-M08-004), then contrast their in-place random write amplification against append-only LSM-Trees and SSTable compaction (CORE-M08-003). Next, you eliminate SSTable point-lookup I/O waste using Bloom and Cuckoo Filters (CORE-M08-001), distribute keys across cluster nodes via Consistent Hashing with Virtual Nodes (CORE-M08-002), and bound high-cardinality streaming telemetry in kilobytes of RAM using HyperLogLog and Count-Min Sketch (CORE-M08-005).

What you will learn

  • Deconstruct 16 KB slotted-page B+ trees, latch crabbing concurrency, and hierarchical spatial indexes (Geohash, Uber H3, Google S2, R-trees)
  • Contrast in-place B+ tree page updates against append-only Log-Structured Merge (LSM) trees, MemTables, SSTables, and Leveled vs. Size-Tiered compaction
  • Derive optimal bit-array sizing and hash function counts () for Bloom filters eliminating unnecessary SSTable disk reads
  • Implement Consistent Hashing rings with Virtual Nodes and Bounded Loads to bound partition skew and node rebalancing movement to
  • Bound sub-linear memory error rates for HyperLogLog cardinality estimation () and Count-Min Sketch heavy-hitter frequency tracking
STAGE TOPICS

Topics in this chapter

Step 16B+ Trees & Disk-Based Indexing InternalsDeconstruct the foundational storage structure of relational databases: B+ Tree slotted page layouts, dynamic node splits and merges, Latch Crabbing concurrency, and write amplification.60 min ↗Step 17LSM-Trees and SSTables: Write-Optimized Storage ArchitectureMaster the mechanics of Log-Structured Merge-Trees and Sorted String Tables, from in-memory MemTables and Write-Ahead Logs to Leveled vs. Size-Tiered compaction algorithms and the RUM conjecture.45 min ↗Step 18Bloom FiltersMaster memory-efficient probabilistic membership testing, false-positive mathematics, and SSTable storage engine optimizations.30 min ↗Step 19Consistent HashingMaster distributed key partitioning, hash ring topology, virtual nodes (vnodes), and minimal key migration under node churn.30 min ↗Step 20Probabilistic Data Structures: HyperLogLog & Count-Min SketchMaster sub-linear space streaming algorithms: HyperLogLog cardinality estimation, Count-Min Sketch frequency estimation, conservative updates, and top-K heavy hitter tracking.45 min ↗