B-Tree

Updated September 30, 20263 min read

In short

A B-tree is a self-balancing search tree whose nodes hold many sorted keys and children, which keeps it shallow so lookups need very few disk or page reads.

What is a B-tree?

A B-tree is a balanced search tree designed for data stored in large blocks, such as pages on a disk or SSD. Instead of holding one key and two children like a binary search tree, each node holds many sorted keys, often hundreds, and has one more child than it has keys. This makes the tree very wide and very shallow: with a few hundred keys per node, a B-tree can index billions of rows in just four or five levels.

To search, you start at the root, find where the target falls among the node's sorted keys, and follow the child pointer between the two neighboring keys, repeating until you reach a leaf. Every node has a minimum and a maximum number of keys: when an insert overfills a node, it splits in two and pushes its middle key up to the parent, and when a delete leaves one too empty, it borrows from or merges with a sibling. Because the tree only grows taller at the root, all leaves stay at the same depth, which guarantees O(log n) search, insert, and delete. Most databases use the B+ tree variant, which keeps all values in the leaves and links the leaves together in order, so range scans can walk sideways without climbing back up the tree.

A B-tree works like a multi-volume encyclopedia: the spine labels tell you which volume to open, the guide words at the top of each page narrow it to one page, and only then do you read entries. Reading one node costs one page read, and reading from storage is far slower than comparing keys in memory, so fewer levels mean faster queries. That is why B-trees, and especially B+ trees, are the default index structure in most relational databases, and why many file systems use them to organize directories and file metadata.

Despite the name, a B-tree is not a binary tree: its nodes have far more than two children, and the B doesn't stand for binary. Its inventors, Rudolf Bayer and Edward McCreight, never settled what the B means, and the name is written both as b-tree and B-tree. B-trees are also often compared with LSM trees (log-structured merge trees), which many write-heavy databases use instead: B-trees update data in place and excel at reads, while LSM trees buffer writes in memory and merge them to disk later, trading slower reads for faster writes.

Key takeaways

A B-tree node holds many sorted keys and child pointers, so the tree is wide and shallow.
All leaves are at the same depth, so search, insert, and delete are O(log n).
Nodes split when they overflow and merge when they get too empty, keeping the tree balanced.
Fewer levels mean fewer page reads, which is why databases and file systems use B-trees.
Most database indexes use the B+ tree variant, which links its leaves for fast range scans.

Example

B-tree indexes in SQLsql

-- A standard index in most relational databases is a B-tree (usually a B+ tree)
CREATE INDEX idx_orders_created_at ON orders (created_at);

-- An equality lookup walks from the root to one leaf: a handful of page reads
SELECT * FROM orders WHERE id = 42;

-- A range query finds the first matching leaf, then scans the linked leaves in order
SELECT * FROM orders
WHERE created_at BETWEEN '2026-09-01' AND '2026-09-30'
ORDER BY created_at;

-- In PostgreSQL, btree is the default index type, but it can be named explicitly
CREATE INDEX idx_users_email ON users USING btree (email);

Readers ask

What is the difference between a B-tree and a binary search tree?

A binary search tree node holds one key and has at most two children, so a large tree is many levels deep. A B-tree node holds many keys and has many children, which keeps the tree only a few levels deep and minimizes slow reads from storage.

What is the difference between a B-tree and a B+ tree?

In a B-tree, keys and their values can live in any node. In a B+ tree, internal nodes only guide the search and all values live in the leaves, which are linked in sorted order, making range scans faster; most database indexes are B+ trees.

What does the B in B-tree stand for?

Nobody knows for sure. Rudolf Bayer and Edward McCreight, who invented it around 1970, never defined it, and popular guesses include balanced, broad, Bayer, and Boeing, where they worked at the time.