Databases · Cluster
Indexes
B-trees, LSM indexes, and access paths.
- 01 Fanout, Height, and Why B-Trees Stay Shallow How page size, key width, and pointer width determine the branching factor of a B-tree, and why three or four levels cover billions of keys.
- 02 Separator Keys and Search Routing in Internal Nodes How internal B-tree pages choose the keys that route a search, what happens when a separator is too short to be unique, and how duplicate keys are ordered.
- 03 Clustered and Secondary Access Paths and the Cost of a Row Fetch What separates a clustered index from a secondary index, how a secondary lookup pays for a second descent, and why covering indexes change the plan.
- 04 Node Splits, Merges, and What the Fill Factor Buys How a B-tree page divides when it overflows, why merges are rarely performed, and what setting a fill factor at build time actually changes.
- 05 The LSM Write Path from Memtable to Sorted Run How an insert becomes a log record, a memtable entry, a flushed sorted file, and finally a merged run, and what each step costs in write amplification.
- 06 Leveled Compaction and the Shape of the LSM Tree Why leveled compaction keeps each level ten times the size of the one above, what that costs in write amplification, and how tiering trades it back.
- 07 Point Lookups, Tombstones, and Read Amplification in LSM Trees How a single-key lookup consults memtables, filters, and runs, why deletion must write a tombstone, and when the tombstone can finally be dropped.
- 08 Prefix Compression and Suffix Truncation in Index Pages How shared key prefixes are stored once per page, why the first key of a page is stored whole, and what restart points cost a search inside a compressed page.
- 09 Concurrent Descent and Page Latching in a Shared B-Tree How readers descend without blocking writers, why a split needs the parent as well as the child, and how the Lehman-Yao protocol avoids deadlock.
- 10 Bitmap Index Scans and the Order of Heap Fetches Why a plan collects row identifiers into a bitmap before fetching rows, how the bitmap is compressed and ordered, and when losing row order is acceptable.