We use analytics cookies.We use cookies to analyze site traffic and improve your experience.
Loading...
System Design and AI Engineering, by Roni Das. 984 interactive lessons.
Start LearningFoundation · Database Fundamentals
A self-balancing search tree in which each node is a page holding many sorted keys, so it stays wide and shallow. Most database indexes use it: finding one key among millions takes only a few page reads.
In short
A B-tree is a self-balancing search tree in which every node is a page holding many sorted keys and child pointers. That keeps the tree very wide and very short. Databases use it because finding one key among millions takes only a few page reads: in my SQLite test, 3 levels for a million rows and 4 for ten million.
In short
A B-tree is a self-balancing search tree in which every node is a page holding many sorted keys and child pointers. That keeps the tree very wide and very short. Databases use it because finding one key among millions takes only a few page reads: in my SQLite test, 3 levels for a million rows and 4 for ten million.
Learn it in the course
This page is the free part.
₹1,111 in India$25 everywhere elseonce, for the whole course
The System Design course covers B-Tree across a run of lessons, not one page. These 3 alone are about 66 minutes of step-by-step reading, every one with a quiz.
Ten million rows sat in three levels and a hundred rows in one. The same million keys took 21.4 MB inserted in order and 29.6 inserted at random, and after churn the index was 21.92 percent full.
The planner stopped using an index somewhere between 19.7 and 39.8 percent of the table. A query on the second column of a composite index took 37.269 ms against 0.054, and five indexes took the same inserts from 160 ms to 751.
When your database indexes rot and queries slow to a crawl, how to fix it without taking the system down.
all part of
System Design Masterclass
770 lessons · about 287 hours · 18 free to read
₹1,111in India, by UPI
$25everywhere else, by PayPal
It is really nice and good Please join the course
You own this course
Continue with B-Treespay once,
yours for life
A B-tree keeps keys sorted so you can find any one of them quickly. You can add and remove keys without ever re-sorting everything. It is the structure behind the index in almost every relational database, including SQLite, PostgreSQL, MySQL, SQL Server and Oracle, and behind many file systems.
Some words first. A key is the value you search by, such as an email address. An index is a separate structure that lets the database find rows by a key without reading the whole table. A node is one box in the tree. A page is the fixed-size block a database reads from storage in one go. It is 4,096 bytes by default in SQLite, 8 KB in PostgreSQL and 16 KB in MySQL's InnoDB. In a B-tree, one node is one page.
The trick is in the shape. Each node holds many keys in sorted order, with a pointer to a child node between each pair of keys. One node can have hundreds of children, so the tree branches hundreds of ways at every level and stays very short. All leaves, the nodes at the bottom, sit at the same depth, so every search takes the same small number of steps. That is what self-balancing means here: the tree never grows lopsided, however the keys arrive.
Rudolf Bayer and Edward McCreight invented it at Boeing's research labs and published it in 1970 and 1972. They never said what the B stands for. In his 1979 survey, Douglas Comer wrote that "balanced", "broad" or "bushy" might apply, and that others suggest Boeing. He added: "it seems appropriate to think of B-trees as 'Bayer'-trees."
A binary search tree, the one taught first in most courses, has at most two children per node. To find one key among a million you walk about 20 levels down, because 2 to the power of 20 is just over a million. In memory that is fine. On storage it is slow, because each level can be a separate page read. Reading a page from disk or SSD costs far more than comparing keys in memory.
A B-tree fixes that by filling each page with as many keys as fit. The database pays for a whole page whenever it reads one key, so it might as well use the whole page. In my SQLite index on email addresses, sqlite3_analyzer reported an average fanout (children per page) of 109. The tree for 1,000,001 rows was 3 levels deep, not 20.
Search starts at the root, the single page at the top. The root's keys split the whole key range into slices. The database follows the pointer for the slice that could hold the key it wants. It repeats that on each page down until it reaches a leaf, which holds the key itself or says it is absent. The number of pages read is the number of levels.
Insert finds the leaf where the new key belongs and puts it there in sorted position. If the leaf is full, it splits. Half the keys move to a new page, and one key that separates the two halves goes up to the parent page. If the parent is full too, it splits the same way, and so on up. When the root itself splits, a new root is made above it, and the tree is one level taller.
That last step is why every leaf stays at the same depth. A B-tree never grows downwards at one branch; it grows upwards at the top, for everyone at once. Delete is the mirror image. The key is removed, and a page that gets too empty may borrow keys from a neighbour or merge with it. Real databases often just leave the space to be reused.
Textbook B-tree pages show a tree with three keys per node. Real ones look very different, so I built four SQLite files on 2026-10-04. Each has a users table with 100, 10,000, 1,000,000 or 10,000,000 random email addresses. I added one known row to each, roni@example.com, so there is something to look up. Each has an index on the email column, built after loading the data. Then I read the shape of each tree straight out of the file with dbstat, SQLite's built-in view of its own pages.
build.sh
#!/bin/bash
# Build one SQLite file per size: a users table and an index on email.
SQ=/opt/homebrew/opt/sqlite/bin/sqlite3
for n in 100 10000 1000000 10000000; do
rm -f users_$n.db
$SQ users_$n.db <<SQL
CREATE TABLE users(id INTEGER PRIMARY KEY, email TEXT NOT NULL, name TEXT NOT NULL);
WITH RECURSIVE seq(i) AS (SELECT 1 UNION ALL SELECT i+1 FROM seq WHERE i < $n)
INSERT INTO users(email, name) SELECT lower(hex(randomblob(6))) || '@example.com', 'user ' || i FROM seq;
INSERT INTO users(email, name) VALUES ('roni@example.com', 'the row we look for');
CREATE INDEX idx_users_email ON users(email);
ANALYZE;
SQL
done
ls -l users_*.dbshape.sql: levels and page counts for the table and the index, from dbstat
-- Read the tree shape straight out of the file with the dbstat virtual table.
SELECT name,
max(length(path) - length(replace(path, '/', ''))) AS levels,
sum(pagetype = 'internal') AS interior_pages,
sum(pagetype = 'leaf') AS leaf_pages,
count(*) AS total_pages
FROM dbstat
WHERE name IN ('users', 'idx_users_email')
GROUP BY name ORDER BY name DESC;Output for each file (run on 2026-10-04, SQLite 3.53.4)
$ sqlite3 -box users_100.db < shape.sql
╭─────────────────┬────────┬────────────────┬────────────┬─────────────╮
│ name │ levels │ interior_pages │ leaf_pages │ total_pages │
╞═════════════════╪════════╪════════════════╪════════════╪═════════════╡
│ users │ 1 │ 0 │ 1 │ 1 │
│ idx_users_email │ 1 │ 0 │ 1 │ 1 │
╰─────────────────┴────────┴────────────────┴────────────┴─────────────╯
$ sqlite3 -box users_10000.db < shape.sql
╭─────────────────┬────────┬────────────────┬────────────┬─────────────╮
│ name │ levels │ interior_pages │ leaf_pages │ total_pages │
╞═════════════════╪════════╪════════════════╪════════════╪═════════════╡
│ users │ 2 │ 1 │ 103 │ 104 │
│ idx_users_email │ 2 │ 1 │ 79 │ 80 │
╰─────────────────┴────────┴────────────────┴────────────┴─────────────╯
$ sqlite3 -box users_1000000.db < shape.sql
╭─────────────────┬────────┬────────────────┬────────────┬─────────────╮
│ name │ levels │ interior_pages │ leaf_pages │ total_pages │
╞═════════════════╪════════╪════════════════╪════════════╪═════════════╡
│ users │ 3 │ 29 │ 11079 │ 11108 │
│ idx_users_email │ 3 │ 74 │ 8028 │ 8102 │
╰─────────────────┴────────┴────────────────┴────────────┴─────────────╯
$ sqlite3 -box users_10000000.db < shape.sql
╭─────────────────┬────────┬────────────────┬────────────┬─────────────╮
│ name │ levels │ interior_pages │ leaf_pages │ total_pages │
╞═════════════════╪════════╪════════════════╪════════════╪═════════════╡
│ users │ 3 │ 317 │ 115441 │ 115758 │
│ idx_users_email │ 4 │ 740 │ 80652 │ 81392 │
╰─────────────────┴────────┴────────────────┴────────────┴─────────────╯
From 100 rows to 10,000,001 rows the data grew 100,000 times, and the index grew from 1 level to 4. A lookup in the biggest index reads 4 pages out of 81,392. Notice too that the table itself is only 3 levels at ten million rows. In SQLite the table is also a tree, keyed by the row id. The next section explains why it is shorter than the index.
Depth is only interesting because of what it costs. I asked SQLite for the plan, then counted pages read from the file on a fresh connection, then timed it. NOT INDEXED is SQLite's way of telling the query to ignore the index, which gives a fair full scan of the same data.
The plan with and without the index, 1,000,001 rows
$ sqlite3 users_1000000.db "EXPLAIN QUERY PLAN SELECT id, name FROM users WHERE email = 'roni@example.com';"
QUERY PLAN
`--SEARCH users USING INDEX idx_users_email (email=?)
$ sqlite3 users_1000000.db "EXPLAIN QUERY PLAN SELECT id, name FROM users NOT INDEXED WHERE email = 'roni@example.com';"
QUERY PLAN
`--SCAN usersPages read from the file ("Page cache misses"), counted by the sqlite3 shell's .stats
$ printf "SELECT count(*) FROM sqlite_schema;\n.stats on\nSELECT id, name FROM users WHERE email = 'roni@example.com';\n" | sqlite3 users_1000000.db | grep -E '^[0-9]+\||Page cache misses|Fullscan Steps'
1000001|the row we look for
Page cache misses: 9
Fullscan Steps: 0
$ printf "SELECT count(*) FROM sqlite_schema;\n.stats on\nSELECT id, name FROM users NOT INDEXED WHERE email = 'roni@example.com';\n" | sqlite3 users_1000000.db | grep -E '^[0-9]+\||Page cache misses|Fullscan Steps'
1000001|the row we look for
Page cache misses: 11111
Fullscan Steps: 1000000The schema statement on its own
$ printf ".stats on\nSELECT count(*) FROM sqlite_schema;\n" | sqlite3 users_1000000.db | grep -E 'Page cache misses'
Page cache misses: 3Timing: warm file cache, median of 2,000 index lookups and 5 full scans (timing.py)
$ python3 timing.py
10,000 rows index 8.9 us full scan 0.48 ms 54x
1,000,000 rows index 8.9 us full scan 70.47 ms 7,903x
10,000,000 rows index 7.7 us full scan 511.22 ms 66,323x
sqlite 3.53.4 | python 3.13.15The first statement on a fresh connection reads 3 pages just to load the schema. So of the 9 pages the index lookup read, 6 were the query. That is 3 levels of the email index to find the row id, then 3 levels of the table to fetch the row. The full scan read 11,111 pages and stepped through all 1,000,000 other rows. That is the whole argument for an index, in two numbers.
The timings tell the same story. The index lookup took about 8 microseconds at every size, including Python's own overhead. 3 or 4 page reads cost the same whether the tree holds ten thousand keys or ten million. The full scan grew with the table, to half a second at ten million rows, 66,323 times slower. These are warm runs, with the file already in the operating system's memory. On a cold disk the gap only widens, since each page becomes a real read from storage.
A B+ tree is a B-tree variant. Its upper pages hold only copies of keys used for steering, and every real entry, with its data, lives in the leaves. In a classic B-tree, entries can live on any level, and each entry is stored exactly once. Almost every database index today is a B+ tree or close to one, but people say B-tree for both.
SQLite uses both kinds in the same file. Its file format document says: "Table b-trees use a 64-bit signed integer key and store all data in the leaves. Index b-trees use arbitrary keys and store no data at all." I counted what dbstat finds on each kind of page in the 10,000,001-row file:
kind.sql: cells and payload bytes on upper (internal) pages and on leaves
-- Where do the keys live? Count the cells and their payload bytes on interior pages and on leaves.
SELECT name, pagetype,
count(*) AS pages,
sum(ncell) AS cells,
sum(payload) AS payload_bytes
FROM dbstat
WHERE name IN ('users', 'idx_users_email') AND pagetype IN ('internal', 'leaf')
GROUP BY name, pagetype ORDER BY name DESC, pagetype;
SELECT count(*) AS rows_in_table FROM users;
-- How many children hang off each root page?
SELECT name, ncell + 1 AS root_children FROM dbstat WHERE path = '/' AND name IN ('users', 'idx_users_email') ORDER BY name DESC;Output, 10,000,001 rows
$ sqlite3 -box users_10000000.db < kind.sql
╭─────────────────┬──────────┬────────┬──────────┬───────────────╮
│ name │ pagetype │ pages │ cells │ payload_bytes │
╞═════════════════╪══════════╪════════╪══════════╪═══════════════╡
│ users │ internal │ 317 │ 115440 │ 0 │
│ users │ leaf │ 115441 │ 10000001 │ 398888936 │
│ idx_users_email │ internal │ 740 │ 80651 │ 2432363 │
│ idx_users_email │ leaf │ 80652 │ 9919350 │ 299146158 │
╰─────────────────┴──────────┴────────┴──────────┴───────────────╯
╭───────────────╮
│ rows_in_table │
╞═══════════════╡
│ 10000001 │
╰───────────────╯
╭─────────────────┬───────────────╮
│ name │ root_children │
╞═════════════════╪═══════════════╡
│ users │ 316 │
│ idx_users_email │ 7 │
╰─────────────────┴───────────────╯
The index is a classic B-tree. Its upper pages hold 80,651 real keys and its leaves hold 9,919,350. And 80,651 + 9,919,350 = 10,000,001: one entry per row, each stored once. The table is a B+ tree. Its upper pages carry 0 bytes of row data, only row ids to steer by. All 10,000,001 rows sit in the leaves.
This explains the depth difference above. The table's upper pages hold only small integers, so one page can point to hundreds of children; the table's root had 316. The table stayed at 3 levels. The index's upper pages hold full email addresses of about 30 bytes, so fewer fit per page; its root had 7 children. It needed a fourth level. Lean upper levels are why B+ trees are popular: more fanout and fewer levels. The leaves also hold everything in key order, so a range query such as BETWEEN or ORDER BY is a walk across neighbouring leaves.
Other databases make their own choices. PostgreSQL's B-tree follows Lehman and Yao's 1981 design, with "pivot tuples" on upper pages used only for navigation and the real entries in the leaves. MySQL's InnoDB documents that its indexes, apart from spatial ones, are B-trees with 16 KB pages by default. It stores each table's rows in the leaves of the primary key index.
A hash index finds an exact key in one step on average. But it keeps no order, so it cannot answer a range query or an ORDER BY. A B-tree answers both, which is why it is the default index almost everywhere.
An LSM tree, used by RocksDB, Cassandra and many write-heavy stores, takes a different bet. It collects writes in memory and writes them out in large sorted batches, merging files in the background. That makes writes cheaper than updating B-tree pages in place, at the cost of reads that may have to check several files. Read-heavy workloads with point and range lookups suit a B-tree; very write-heavy ones often suit an LSM tree.
A B-tree index is not free, and it is not always used.
If you are deciding which columns to index, start with my database indexing lesson. If you want to see what a B-tree looks like inside a production database, my B-Trees lesson opens real PostgreSQL index pages with pageinspect. It measures how deep the tree is at ten million rows and how full its pages are, depending on the order keys arrive. It also shows how much space churn leaves behind after VACUUM, and when REINDEX is worth it.
SQLite
Every table is a B+ tree keyed by row id, and every index is a B-tree. All live in one file of 4,096-byte pages by default.
PostgreSQL
The default index type is a B-tree based on Lehman and Yao's design, with 8 KB pages. pageinspect lets you read its pages directly.
MySQL InnoDB
Indexes other than spatial ones are B-trees with 16 KB pages, and table rows live in the leaves of the primary key index.
MongoDB
Its default storage engine, WiredTiger, keeps collections and indexes in B-trees.
File systems
Btrfs is named after the B-tree, and NTFS, HFS+, APFS and XFS use B-tree variants for directories and metadata.
A B-tree is a sorted tree where each node holds many keys and many child pointers. Example: my SQLite index on 1,000,001 email addresses was a B-tree 3 levels deep, about 109 children per page on average. To find one email, SQLite read one page per level, 3 pages, then fetched the row.
Nobody knows for sure. Its inventors, Rudolf Bayer and Edward McCreight, then at Boeing, never explained the B. Douglas Comer's 1979 survey lists balanced, broad, bushy and Boeing as guesses and suggests thinking of them as Bayer-trees.
In a B-tree, entries can live on any level and each is stored once. In a B+ tree, upper levels hold only keys used for steering and all entries live in the leaves, which are kept in key order. SQLite uses a B+ tree for tables and a B-tree for indexes; most database indexes are B+ trees.
No. A binary tree node has at most two children; a B-tree node can have hundreds, because each node fills a whole storage page. For a million keys a balanced binary tree is about 20 levels deep, while my SQLite B-tree index was 3.
Database indexes and tables, and file system metadata. Small upper levels give more children per page and fewer levels. Keeping all entries in sorted leaves makes range queries and ORDER BY cheap.
Every write to an indexed column also updates the index, and page splits leave empty space behind. The index takes disk and memory: 42 percent of my test file. And it gives no benefit for tiny tables or queries that match most rows. Very write-heavy workloads often prefer an LSM tree.
Both stay balanced, but an AVL tree is a binary tree designed for memory, with two children per node and rotations to rebalance. A B-tree is designed for storage that reads whole pages: many keys per node, splits instead of rotations, and far fewer levels.
Checked against these on .
Database Indexing
The planner stopped using an index somewhere between 19.7 and 39.8 percent of the table. A query on the second column of a composite index took 37.269 ms against 0.054, and five indexes took the same inserts from 160 ms to 751
Index Rebuilding
When your database indexes rot and queries slow to a crawl, how to fix it without taking the system down
Index
A data structure that speeds up database lookups. Like the index at the back of a book that lets you jump to the right page instead of reading every page.
LSM Tree
Log-Structured Merge Tree: a write-optimized data structure that buffers writes in memory and periodically flushes sorted runs to disk. Used by Cassandra, RocksDB, and LevelDB.
Hash Index
An index that uses a hash function to map keys directly to storage locations. O(1) lookups for exact matches but useless for range queries. Memcached and Redis use hash indexes.
Primary Key
A column (or combination of columns) that uniquely identifies each row in a database table. Must be unique and not null.
Database
An organized collection of data that can be easily accessed, managed, and updated. The backbone of almost every application.
SQL
Structured Query Language for managing relational databases. Tables, rows, columns, and powerful joins to query related data.
This page explains the idea. The "B-Trees" lesson builds it up step by step, with diagrams. It is part of the System Design Masterclass course, which has 770 lessons. 18 of them are free to read. You pay once and keep it for life, with no subscription.
Open the B-Trees lessoncourse 1
From absolute beginner to principal engineer, drawn step by step.
Asked about B-Tree in an interview?
Each question has why it is asked, a full answer, what the interviewer listens for, the follow-ups, the common mistakes and a diagram (268 diagrams in all). A PDF you keep, junior to staff level.
India: UPI, cards or netbanking through Razorpay. Elsewhere: card or PayPal. Download at once from My packs.
