Search trees

In a binary search tree every node’s left subtree holds smaller keys and its right subtree larger ones, so a search goes left or right at each node. Every operation takes time proportional to the tree’s height, and the height depends on the order keys arrive in: random order gives about 1.39 lg n compares per search, but nothing guarantees it. Balanced trees restore the guarantee by rotating nodes after updates. AVL trees (Adelson-Velsky and Landis, 1962, the first such scheme) keep the heights of each node’s two subtrees within one of each other. Red-black trees spend one colour bit per node and keep the height at most 2 log₂(n+1). Java’s TreeMap is a red-black tree with guaranteed log(n) get, put and remove, and C++’s std::map is usually one.

B-trees put many keys in each node. Rudolf Bayer and Edward McCreight designed them in 1970 at Boeing Scientific Research Laboratories for indexes too big for main memory, kept on discs and drums that are slow to reach but fast once reading: retrieval, insertion and deletion take time proportional to log_k of the index size, and pages stay at least half full. The same trade works in RAM. Rust’s BTreeMap keeps B−1 to 2B−1 elements per node in a contiguous array, which needs B times fewer allocations and misses the cache less than a binary tree.

This is how databases index. By 1979 Douglas Comer called the B-tree “de facto, the standard organization for indexes in a database system”. PostgreSQL’s btree index is a multi-way balanced tree in which over 99% of pages are typically leaves; a full leaf splits and the split can cascade up to the root. SQLite stores tables and indexes as b-trees of pages, each interior page holding K keys and K+1 child page numbers. Wide nodes keep the tree shallow, so a lookup reads only a few pages from disk.