Chapter Six · Trees
Trees
The shape that lets a computer skip most of its data. Six topics: trees and the orders to walk them, the binary search tree and the input that ruins it, the rotations that repair it, and three trees shaped by one job each: the heap, the trie and the B-tree.
A list makes a program read everything to find anything. A tree changes the question from "how many items are there" to "how many levels are there", and the answer to the second is almost always small: 20 levels for a million keys in a balanced binary tree, 3 or 4 for billions of keys in a B-tree. Every fast ordered lookup in the systems you run, from a database index to a scheduler's queue, is a descent through a few levels of some tree.
The catch is that levels are not free and not guaranteed. A binary search tree fed sorted keys becomes a chain a million levels deep, and nothing in its code complains. A pointer-based tree pays a potential cache miss at every level, and on disk it pays a page read. So this chapter follows two numbers through every structure it meets: the fan-out, how many children each node has, and the height, how many levels a search must pass.
It starts with trees in general and the orders in which to walk them, adds order to get the binary search tree, and repairs its failure with rotations. Then it turns to three trees built for one job each. The heap keeps the smallest item on top, and Lantern uses one to keep its ten best results. The trie serves prefixes, and Lantern's autocomplete is one. The B-tree turns a page read into a several-hundred-way choice, and Lantern's index on disk is one, which is also where this book hands databases over to PostgreSQL Deep Dive.