What Is a B-Tree? The Structure Behind DB Indexes

A B-tree is a self-balancing tree data structure that keeps its elements sorted and guarantees logarithmic-time search, insertion, and deletion, even as the tree grows to billions of entries. It’s the structure underneath most database indexes and many filesystems, chosen specifically because it’s optimized for reading and writing in large blocks from disk rather than following pointers one at a time in memory.

Why not a regular binary search tree

A binary search tree keeps each node’s left subtree smaller and right subtree larger, giving O(log n) operations — but only if the tree stays balanced. Worse, each node holds exactly one key and points to at most two children, so navigating a large tree means following a long chain of individual pointers. On disk, where each pointer-following step can mean a separate, relatively slow I/O operation, a tree with millions of entries and only two children per node ends up with a tree height — and therefore a number of disk reads per lookup — that’s larger than necessary.

A B-tree fixes this by letting each node hold many keys and many children — often hundreds — instead of just one and two. That collapses the tree’s height dramatically: a B-tree indexing a billion rows might only be three or four levels deep, meaning a lookup touches three or four disk blocks instead of the twenty-plus a binary tree of the same size would require.

Structure

Every B-tree node holds a sorted list of keys and, for internal nodes, one more child pointer than it has keys. Each child subtree holds keys that fall between the two keys bracketing it in the parent — the same ordering invariant as a binary search tree, just generalized to more than two children per node.

A B-tree of “order m” (sometimes called the branching factor) constrains node size: every node holds between ⌈m/2⌉ - 1 and m - 1 keys (except the root, which can have fewer). This minimum-fill constraint is what keeps the tree balanced — a node is never allowed to become nearly empty, so the tree can’t degenerate into something resembling a long chain.

                 [ 30 | 60 ]
                /      |      \
         [10|20]   [40|50]   [70|80|90]

Searching for a key means starting at the root, finding which gap the target key falls into among the node’s sorted keys, and descending into the corresponding child — repeating until reaching a leaf. Each step is a binary or linear search within one node’s small key list, which is cheap because the whole node was already pulled into memory in one disk read.

Insertion, deletion, and rebalancing

Inserting a key finds the correct leaf and inserts it in sorted order. If that leaf now holds more keys than its maximum allowed (m - 1), it splits: the middle key moves up into the parent, and the leaf divides into two nodes. If the parent then overflows, the split propagates upward — in the worst case all the way to the root, which is the one case where the tree’s height increases.

Deletion is the mirror image: removing a key from a node that would then fall below the minimum fill triggers either borrowing a key from an adjacent sibling (if the sibling has one to spare) or merging with a sibling (if not), which can propagate a height decrease upward from a shrinking root. Both operations are more involved than in a binary tree, but they’re what guarantee the tree never becomes lopsided — every root-to-leaf path stays the same length, which is the property that makes worst-case performance predictable rather than dependent on insertion order.

B-tree vs B+tree

Most production database indexes actually use a variant called a B+tree, not a plain B-tree, though the two names get used loosely. The difference: in a B+tree, all actual data (or row pointers) lives only in the leaf nodes — internal nodes store keys purely for routing, not payload — and the leaves are additionally linked together in a chain. That leaf-level linked list makes range queries (WHERE age BETWEEN 20 AND 30) fast: once you’ve found the starting leaf, you scan forward through linked leaves instead of re-traversing the tree for each subsequent row. This is a large part of why relational indexes handle both point lookups and ranges efficiently, and it’s relevant to how SQL window functions can scan ordered ranges efficiently once the underlying rows are already sorted by an index.

B-trees vs hash tables

It’s worth being clear about when a B-tree is the right structure versus a hash table, since databases offer both as index types:

	B-tree	Hash table
Exact-match lookup	O(log n)	O(1) average
Range queries (<, >, BETWEEN)	Efficient (sorted order)	Not supported directly
Sorted iteration	Native	Requires a separate sort
Worst-case behavior	Predictable, balanced	Can degrade under bad hash distribution

A hash index wins for pure equality lookups on a column that’s never queried by range. A B-tree wins the moment range queries, sorting, or ORDER BY on the indexed column matter — which is most of the time, and why B-trees (or B+trees) are the default index type in nearly every relational database.

The takeaway

A B-tree generalizes a binary search tree to many keys and children per node, which shrinks tree height and matches how disks read and write in blocks rather than following pointers one at a time. Its minimum-fill invariant, maintained through node splits on insert and merges or borrows on delete, keeps every root-to-leaf path the same length, guaranteeing logarithmic-time operations regardless of insertion order. The B+tree variant, with data confined to linked leaf nodes, is what most database indexes actually implement, since it handles both point lookups and range scans efficiently.