Open a PostgreSQL table with a million rows and query for a single value. PostgreSQL finds it in under a millisecond. Not because it scanned all million rows — because it maintained a sorted tree of keys on disk, and each comparison eliminates half the remaining candidates.
Open a directory with 100,000 files and look up a filename. The operating system finds it in microseconds. Not by scanning — by traversing a tree structure that organises filenames by their position in a sorted order.
Parse a Python expression and evaluate it. The interpreter builds a tree of nodes, traverses it in post-order, and evaluates each node as it goes.
Three different domains. Three different systems. One structure: a tree. The specific variant — B-tree, directory tree, parse tree — differs by the constraints of the storage medium. The traversal logic is the same in all three.
In Book 1, you built binary search trees (Ch 25) and saw why B-trees minimise disk reads (Ch 26). The core insight of Ch 26: a disk read has a fixed cost regardless of how much data you read within a page boundary. A B-tree node is sized to match a disk page, so each level of the tree costs exactly one disk read.
This chapter traces Thread 2 (Trees) into three production systems. In each case, the specific tree variant is determined by the same analysis: what are the constraints of the storage medium, and what tree structure matches those constraints? The thread continues in Book 3, Ch 9, where B-tree indexes become the foundation of query optimisation.
A tree is a connected, acyclic graph. Its two fundamental operations are insertion (place a new node in its correct position) and search (find a node by key). Both operations traverse from the root toward a leaf, making a comparison at each node to determine which child to follow.
The performance of these operations depends on tree height. A balanced tree with N nodes has height O(log N). An unbalanced tree (a pathological case where each node has only one child) has height O(N) — equivalent to a linked list.
Three factors vary across tree variants: - Branching factor — how many children a node can have (binary = 2, B-tree = hundreds) - Balance guarantee — whether the tree maintains equal height across branches (BST: none by default; AVL, Red-Black, B-tree: guaranteed) - Node size — how much data fits in a node (BST: one key; B-tree: hundreds of keys, sized to match a disk page)
Each production tree variant chooses these factors based on the constraints of where it lives.