The idea: where do the rows live?
A B-tree and a B+tree look almost the same: wide nodes, sorted keys, every leaf at the same depth. The difference is where the data goes. A B-tree stores each key once, with its row, in whatever node it lands in, so inner nodes hold rows too. A B+tree keeps every row in a leaf. Its inner keys are only signposts (copies used for routing), and the leaves are linked left to right. The canvas holds the same 12 keys, 10 to 120, in both trees, with order 3 (at most 2 keys and 3 children per node). The green strips are rows.
B-tree: a row next to every key
Every key appears exactly once. A search stops as soon as it meets the key, which can be in the root. Nothing is stored twice, so the tree holds slightly fewer keys in total. But every entry in an inner node carries a whole row, so an inner node fits far fewer entries, and an ordered walk has to come back up to the parents to return the keys stored there.
B+tree: signposts above, rows and links below
Inner nodes hold only keys and child pointers. When a leaf splits, its new first key is copied up as a signpost (see B+ Trees), so a key such as 30 can be in an inner node and in a leaf. A search always ends in a leaf. Each leaf points to the next one, so an ordered scan never goes back up.
Point lookups: a tie, almost always
The B+tree always pays its full height: root, middle, leaf, 3 pages here (Demo: point lookup 50). The B-tree can stop early. 40 sits in its root, so it costs 1 page (Demo: lookup 40, a key in the B-tree root). That case is rare. Here only 2 of the 12 keys are in the root and 3 more in the middle level, so the average B-tree lookup is 29 / 12 ≈ 2.4 pages against 3. In a real tree with 76 children per node, more than 98 % of the keys are in the leaves, and the early exit almost never happens.
Range scans: right along the leaves vs down and up
For 20..60 the B+tree goes down once to the leaf with 20, then follows the links: 5 moves, never back up. The B-tree walks the tree in order with a cursor stack. It returns 20 from a middle node, 30 from a leaf, climbs back to the root for 40, goes down for 50, and climbs to 60: 7 moves, 2 of them climbs to nodes it had already read (Demo: range scan 20..60). Both read 5 distinct pages here. The real gap is the path: the B+ leaves are next to each other on disk, so a scan is one sequential read, while the B-tree jumps between levels.
The longer the range, the bigger the difference. A full scan of all 12 keys takes the B-tree 15 moves with 5 climbs and 10 pages (every node). The B+tree takes 8 moves and 8 pages, and never reads its right-hand inner node at all (Demo: full scan 10..120).
Fan-out per page: the real reason
On disk a node is one page (16 KB in InnoDB). Take an 8-byte key, an 8-byte child pointer and a 200-byte row. A B-tree entry is key + row + pointer = 216 bytes, so a page holds 75 keys and has 76 children. A B+ inner entry is key + pointer = 16 bytes, so a page holds 1,023 keys and has 1,024 children. A B+ leaf holds 78 rows. Every level is one page read, so more children per page means fewer reads (Demo: fan-out per 16 KB page).
| Rows | B-tree levels (fan-out 76) | B+tree levels (fan-out 1,024, 78 rows per leaf) |
|---|---|---|
| 1 million | at least 4 | 3 |
| 10 million | at least 4 | 3 |
| 100 million | at least 5 | 4 |
There is a second win. For 10 million rows the B+tree has 128,206 leaves but only 127 inner pages, about 2 MB, which easily stay in memory. A lookup then reads about one page from disk: the leaf. A B-tree's upper pages are full of rows, so caching them means caching rows.
When to pick which
| B-tree | B+tree | |
|---|---|---|
| Rows stored | in every node | only in leaves |
| Point lookup | can stop early (rare) | always the full height |
| Range scan | in-order walk, climbs back up | down once, then along the leaf links |
| Fan-out per page | lower (rows take the space) | much higher, so a shorter tree |
| Keys stored twice | no | yes, as signposts |
| Used by | rare on disk today; textbooks and some in-memory ordered maps | almost every database and file system: InnoDB, PostgreSQL, SQLite, NTFS, ext4 directories, XFS |
In practice "B-tree" in a database manual (CREATE INDEX … USING btree) nearly always means a B+tree. See Database Index for how one serves a query, and LSM Tree vs B+ Tree for the write side.
What the page leaves out
Both trees are fixed, bulk-loaded shapes with order 3; inserts, splits and merges are on the B-tree and B+tree pages. The cost model counts node visits and distinct pages, not time, and treats every page as a disk read (no buffer pool). It leaves out page headers and fill factor, variable-length keys and prefix compression, duplicate keys, the backward links real B+ leaves also have, concurrency (latch coupling, B-link trees) and clustered vs secondary indexes.