MySQL InnoDB uses B+ trees (a variant where all data is stored in leaf nodes, with leaf nodes linked in a doubly-linked list for efficient range scans). The clustered index is the primary key B+ tree; secondary indexes point to the primary key, not directly to the row. A secondary index lookup requires two B-tree traversals: one to find the primary key, one to find the row.
Linux ext4 uses HTree indexes for directories with
more than ~10 entries. The HTree is a two-level radix tree based on a
hash of the filename. Lookup is O(1) average (one hash computation, two
tree levels). Large directories (/usr/bin with thousands of
entries) benefit from this design; the alternative would be linear scan
of directory blocks.
Python’s ast module exposes the AST for
any Python expression or statement. Linters (pylint, flake8), static
type checkers (mypy), and code formatters (black) work by traversing
this AST and applying rules at each node. The AST’s structure makes it
easy to find all function calls, all variable assignments, or all return
statements without writing a custom parser.
Concept: B-Tree Index (and tree structures in production systems)
Thread: T2 (Trees) ← BST (Book 1, Ch 25), B-tree intro (Book 1, Ch 26) → database query optimisation (Book 3, Ch 9)
Core Idea: A B-tree is a BST redesigned for disk-based storage: nodes hold hundreds of keys (sized to match a disk page), so tree height is log₄₀₀(N) instead of log₂(N). Three disk reads can search 64 million rows. The same principle appears in file system directories and parse trees — each tree variant matches its branching factor and node size to the constraints of its storage medium.
Tradeoff: AT4 — Precomputation vs. On-Demand (the index is precomputed at write time; it pays off only for selective queries; sequential scans beat index scans when many rows match)
Failure Mode: FM5 — Latency Amplification (index lookup triggers random heap fetches; for low-selectivity queries this is slower than sequential scan)
Signal: When query latency is high and the query filters on a column — check if an index exists and whether the query’s selectivity justifies using it. When table inserts are slow — check write amplification from index maintenance.
Maps to: Reference Book, Framework 8, Infrastructure Components (Primary Database)