B-Tree

A B-tree is a sorted tree where every node can hold many keys instead of just one. A binary search tree splits into two children at each node and gets tall fast. A B-tree splits into hundreds or thousands of children at each node and stays short. That shortness is the whole point, because the height of the tree is how many disk reads it takes to find something.

The B stands for balanced, not binary. All leaf nodes sit at the same depth, and the tree rebalances itself on every insert and delete so it never degenerates into a long chain. This guarantees that search, insert, and delete all stay O(log n) no matter what order the data arrives in.

Each node maps to one disk page or block, usually 4 KB, 8 KB, or 16 KB. Because a page holds many keys, the branching factor (often called the fanout) is large. A fanout of 1000 means a tree only 3 levels deep can index a billion keys. Three page reads to find any row in a billion is why B-trees have dominated databases since the 1970s.

Reading is a top-down walk. You start at the root, do a binary search inside the node to pick the right child pointer, follow it to the next node, and repeat until you hit a leaf. Each step is one page read. Within a page the search is in memory and effectively free compared to the disk hit.

Inserting starts the same way: find the leaf where the key belongs and put it there. If the leaf is now full, it splits in half and pushes the middle key up to the parent. If the parent overflows too, it splits as well, and a split can cascade all the way to the root. When the root splits, the tree grows one level taller. Deletes work in reverse, borrowing keys from siblings or merging underfull nodes so no page drops below half full.

Most real databases use a B+ tree, a variant where all the actual data or row pointers live only in the leaf nodes, and internal nodes hold just keys for routing. The leaves are also chained together in a linked list, so once you find the start of a range you can walk sideways through the leaves to read the rest. That is what makes range scans like WHERE created_at BETWEEN x AND y fast, and what powers ORDER BY without a separate sort.

B-trees are the default index for almost every relational workload because they handle both point lookups (find user 42) and range queries (find orders from last week) well, and they keep results in sorted order for free. If you do not know what to index with, a B-tree is the safe answer.

The cost is on writes. Every insert can trigger a page split and rewrite, and random inserts scatter writes across the tree, causing write amplification and fragmentation over time. Workloads with huge sustained write volume, like time-series ingestion or event logging, often do better with an LSM-tree (log-structured merge tree), which batches writes sequentially. RocksDB, Cassandra, and modern InnoDB-alternative engines lean on LSM-trees for exactly this reason.

A B-tree index also only helps when your query filters on a prefix of the indexed columns. An index on (last_name, first_name) speeds up a search by last name, but does nothing for a search by first name alone. And hash indexes beat B-trees for pure equality lookups since they are O(1), but a hash index cannot do ranges or sorting at all, so you give up the B-tree's biggest strength.

When you run CREATE INDEX idx_email ON users(email) in PostgreSQL, it builds a B+ tree keyed on email. A query like SELECT * FROM users WHERE email = 'a@b.com' then walks from the root down to a leaf in 3 or 4 page reads, finds a pointer to the row's location in the table, and fetches it. Without the index, Postgres would scan every row in the table.

Postgres goes a step further and caches the upper levels of the tree in shared memory. For a typical table the root and the level below it stay resident in RAM, so a lookup that logically needs 4 page reads often only hits disk once for the final leaf. That is why a well-indexed lookup stays in the low milliseconds even as the table grows from thousands to billions of rows.