Databases

A database must handle reads and writes on datasets that do not fit in RAM, often from thousands of concurrent clients. Naive structures like arrays or linked lists fail because they either require full scans or cannot be serialized efficiently to disk pages. Database engineers need structures that minimize disk I/O, support range queries, and maintain balance as data is inserted and deleted. Every design decision in a storage engine — from page size to branching factor — flows from this constraint.

A B-tree is a self-balancing search tree where each node can hold many keys, making it ideal for disk-based storage where reading a 4 KB page is roughly the same cost as reading a single byte. PostgreSQL, MySQL InnoDB, SQLite, and Oracle all use B-tree variants as their primary index structure. When you run CREATE INDEX, the database builds a B-tree over the indexed column, keeping keys sorted so that range queries like BETWEEN or ORDER BY can be served with a small number of node traversals. Insertions and deletions trigger splits and merges to keep the tree balanced without a full rebuild. The height of a B-tree over a billion rows is typically 4–5 levels, meaning most lookups touch only 4–5 disk pages.

When a query engine executes a hash join, it builds an in-memory hash table from the smaller of two relations, then probes it for each row of the larger relation. This turns an O(n²) nested-loop join into an O(n) operation under good hash distribution. Hash tables also power GROUP BY aggregation: as rows stream in, the engine hashes the group-by key and accumulates the aggregate value in the corresponding bucket. PostgreSQL's executor, MySQL's optimizer, and DuckDB's vectorized engine all implement hash join and hash aggregation as core operators. When the hash table exceeds the work memory limit, the engine spills partitions to disk and processes them in batches.

Before a single row is read, the query planner represents your SQL statement as a tree of relational operators — scans, filters, joins, projections — where each node's output feeds its parent. This operator tree is a binary tree (or n-ary tree for multi-way joins), and the planner's job is to search the space of equivalent trees for the one with the lowest estimated cost. Transformations like predicate pushdown, join reordering, and subquery unnesting are all tree rewrites. The planner uses dynamic programming to evaluate join orderings without re-evaluating the same subproblems, turning an exponential search into a manageable one. The final plan tree is then compiled into an execution pipeline.

When you submit SELECT * FROM orders JOIN customers ON orders.customer_id = customers.id WHERE orders.total > 100, the parser builds an AST, the planner rewrites it into an operator tree and picks index scans using B-tree indexes on the relevant columns. The executor walks the plan tree, using hash tables for the join and returning matching rows through the projection node. Write-ahead logging ensures that if the server crashes mid-transaction, the B-tree index and heap pages can be recovered to a consistent state. Every step of this pipeline is a direct application of the data structures you study.