What Is a B-Tree?

A B-tree is a self-balancing tree that keeps data sorted and stores many keys per node, so it needs very few disk reads to find a value. Most database indexes (MySQL InnoDB, PostgreSQL) are B-trees or B+trees.

The concept

Each node holds many sorted keys and has many children, making the tree very shallow: millions of rows may need only 3–4 levels. Each level costs one disk page read.

Inserts split full nodes and deletes merge sparse ones, keeping all leaves at the same depth and operations at O(log n).

Shallow and wide

Practical examples

Create an index (B-tree in MySQL/PostgreSQL)

CREATE INDEX idx_users_email ON users (email);

Range queries work well

SELECT * FROM orders WHERE created_at BETWEEN '2026-01-01' AND '2026-01-31';

Check usage

EXPLAIN SELECT * FROM users WHERE email = 'a@x.com';

Common mistakes

• Thinking a B-tree stores one key per node like a BST.
• Indexing low-cardinality columns that give little benefit.
• Using functions on indexed columns and bypassing the index.

Key takeaways

• Wide, shallow, balanced tree.
• Fits disk pages, so few reads.
• Backbone of database indexes.

FAQ

B-tree vs B+ tree?

B+ trees keep all values in leaves linked together, ideal for range scans.

Why not a binary tree?

Too deep: more levels mean more disk reads.