B-Tree vs B+ Tree comes down to one structural choice: where record pointers live. Both are self-balancing, multi-way search trees built for disk storage. A node is sized to match one disk block, so a wide branching factor keeps the tree shallow. In a B-tree, every node, root, internal, and leaf, holds keys together with record pointers. A search can therefore end at any level, even the root. There is no link between leaves. In a B+ tree, internal nodes hold only keys, acting as separators that route the search. Every record pointer sits in a leaf instead. Leaves are linked in a sequential list, so a range scan walks forward without climbing back up. Because internal nodes carry no record pointers, more keys fit in one block. More keys per block means higher fanout, and higher fanout means a shallower tree. A shallower tree needs fewer block reads per lookup. Most database indexes, and many filesystems, use B+ trees for exactly that reason.
B-trees and B+ trees both grew from the same problem: how to search fast when data sits on disk. Rudolf Bayer and Ed McCreight introduced the B-tree in 1972. The B+ tree came later, as a variant tuned for range scans and sequential access.
Students often treat the two as one structure with two names. They are not. One design choice, where record pointers live, separates them completely.
Binary search trees, compared in binary tree vs binary search tree, cap each node at two children. B-trees and B+ trees generalise that idea for many children.
Why Disk-Based Trees Look Different
A B-tree or B+ tree node is not a small object sitting in RAM. It is sized to fill one disk block. Reading a block from disk costs far more than comparing a few keys in memory.
So the design goal shifts. In a plain binary search tree, the metric that matters is comparisons. In a disk-based tree, the metric that matters is block reads. That is the number of nodes a search must fetch from disk.
That distinction is really about time complexity in a different cost model, the kind covered in data structure efficiency and time complexity. Counting block reads instead of comparisons changes which structure wins.
A wide node holds many keys, so one block read narrows the search a lot. That is why both trees chase high fanout: fewer levels, fewer block reads, faster lookups.
How a B-Tree Stores Data
A B-tree keeps keys and record pointers together, at every node. The root holds keys and pointers. Every internal node holds keys and pointers. Every leaf holds keys and pointers too.
A search walks down the tree, comparing the target key against the keys in each node it visits. If the target key sits in a node the search already reached, its record pointer is right there. The search can stop then, without ever touching a leaf.
There is no link between one leaf and the next. A range scan often spans several leaves. Each one means climbing back up to a parent, then back down again.
The main advantage is early termination. So a frequently searched key stored near the root returns fast, sometimes after a single block read.
The cost shows up in fanout, though. Every node carries record pointers alongside keys, so fewer keys fit in one block. Fewer keys per block means more levels, and more levels mean more block reads on average.
How a B+ Tree Stores Data
A B+ tree splits the two jobs a B-tree combines into one. Internal nodes route the search. Leaf nodes hold the data.
An internal node stores keys only, with no record pointers attached. Each key acts as a separator, marking the boundary between two child subtrees.
Every record pointer lives in a leaf instead. A search therefore always travels the full height of the tree, ending at a leaf, never earlier.
Leaves connect to each other in sequence. Once a search reaches the right leaf, a range scan walks forward without climbing back up the tree.
A clustered index, compared in clustered vs non-clustered index, is really a B+ tree under the hood. Rows sit at the leaves, in key order, ready for a scan.
A separator key in an internal node also appears again in a leaf. That duplication is expected, not a flaw; it is how a separator still marks a real record’s position.
Removing record pointers from internal nodes raises the fanout, and higher fanout keeps the tree shallow. That is why most database indexes, and many filesystems, use B+ trees for lookups and range scans alike.
The tradeoff is uniform cost. Every search reaches a leaf, even when the key sits high in the tree. A B-tree can occasionally return faster, simply by stopping early.
B-Tree vs B+ Tree: Comparison Table
| Aspect | B-Tree | B+ Tree |
|---|---|---|
| Where record pointers live | Every node: root, internal, and leaf | Leaves only |
| What internal nodes hold | Keys plus record pointers | Keys only, acting as separators |
| Where a search can end | Any level, including the root | Always at a leaf |
| Leaf linking | No link between leaves | Leaves linked in a sequential list |
| Range and sequential scan cost | Repeated climbs back up between leaves | One forward walk across linked leaves |
| Keys per block (4096-byte example) | 170 keys, 171 child pointers | 255 keys, 256 child pointers |
| Resulting tree height | Taller, for the same record count | Shorter, from the higher fanout |
| Uniformity of search cost | Variable, can stop early or go deep | Uniform, always reaches a leaf |
| Key duplication across levels | Not expected | Expected, separator keys reappear in leaves |
| Deletion complexity | Can remove a key directly from any level | Must rebalance from a leaf and fix separators above it |
| Space use in internal nodes | More space per key, since a pointer travels with it | Less space per key, separators only |
| Typical real-world use | Less common in modern database engines | Most database indexes and many filesystems |
| Behaviour on full-table ordered scans | Repeated root-to-leaf traversals | Single forward walk over linked leaves |
| What happens to internal nodes on delete | May lose a record pointer directly | Only separator keys need adjusting, not records |
Worked Example: How Many Keys Fit in a Block
Fanout is not abstract. It comes straight from block size and pointer size, arithmetic any student can redo in an exam.
Assume a disk block of 4096 bytes. A key takes 10 bytes. A record pointer takes 8 bytes. A block pointer takes 6 bytes. Let n be the number of keys stored in a node.
Start with the B-tree case. A B-tree node holds n keys, n record pointers, and n+1 block pointers. Each key still pairs with its own record pointer.
- Space needed: 6(n + 1) + (10 + 8)n ≤ 4096
- Expand the block-pointer term: 6n + 6 + 18n ≤ 4096
- Combine the n terms: 24n + 6 ≤ 4096
- Subtract 6 from both sides: 24n ≤ 4090
- Divide by 24: n ≤ 170.41
- Round down to a whole number of keys: n = 170
So one B-tree node holds 170 keys and 171 child pointers, one more pointer than keys.
Now the B+ tree case. An internal node here drops the record pointers entirely. It holds only n keys and n+1 block pointers.
- Space needed: 6(n + 1) + 10n ≤ 4096
- Expand the terms: 6n + 6 + 10n ≤ 4096
- Combine the n terms: 16n + 6 ≤ 4096
- Subtract 6 from both sides: 16n ≤ 4090
- Divide by 16: n ≤ 255.625
- Round down to a whole number of keys: n = 255
So one B+ tree internal node holds 255 keys and 256 child pointers.
Compare the two results directly. A B+ tree node fits 256 children. A B-tree node fits only 171. That works out to 1.50 times the fanout, gained by removing one field per key.
Follow that number through to its consequence. A wider node needs fewer levels to index the same number of records. Fewer levels mean fewer block reads for every lookup. Add linked leaves on top, and a range scan becomes one sequential walk instead of many separate root-to-leaf trips. Fanout, height, block reads, linked leaves: that chain is the entire argument for a B+ tree. It explains why database engines choose it over a B-tree.
Why Range Queries Favour the B+ Tree
A range query asks for every key between two bounds, not just one exact match.
In a B+ tree, the search finds the first matching leaf once. From there, the linked list of leaves carries the scan forward, key after key, until the range ends.
A B-tree can run a range query too; nothing blocks it from doing so. Without leaf links, though, it must climb back up to a parent and back down again for each new leaf. So that repeated climbing adds extra block reads.
So the real win for the B+ tree is not that range queries are impossible on a B-tree. It is that linked leaves turn a scan into one sequential pass instead of many separate traversals.
Order, Degree and the Minimum Fill Rule
GATE questions usually define a B-tree, or a B+ tree, by its order, written as m.
A node holds at most m − 1 keys. It holds at most m children, one more child than keys.
Still, a non-root internal node cannot be too empty. It needs at least ⌈m/2⌉ children, and therefore at least ⌈m/2⌉ − 1 keys.
The root is exempt from that minimum. It needs only one key, since it has no parent to keep it half full.
Leaf capacity in a B+ tree is where textbooks disagree slightly. Some count leaf slots the same way as internal nodes. Others size leaves around the record pointers each leaf holds instead. An exam question usually states its own convention, so read the given definition before applying any formula.
Where Each One Is Used
Most relational database indexes use a B+ tree, not a plain B-tree. MySQL’s InnoDB, PostgreSQL, and Oracle all build their default indexes this way.
Several filesystems use B+ trees too, for the same reason: fast lookups alongside fast sequential directory scans.
Plain B-trees still show up in a few in-memory indexing structures and older filesystem designs. Early termination matters more there than range scans.
Not every access pattern fits a B+ tree, though. Spatial data, compared in quad trees vs KD-trees, needs a structure built around location instead.
Indexing sits alongside other DBMS design choices too. Schema design brings its own tradeoffs, covered in lossless vs lossy decomposition.
Interview Questions
Frequently Asked Questions
Wrapping Up
B-Tree vs B+ Tree is not a contest with one universal winner. Both are multi-way search trees built for disk, and one design choice separates them.
Keep that one choice close for exams. A B-tree keeps record pointers at every node, so a search can stop early, but fewer keys fit per block. A B+ tree keeps record pointers only at the leaves, so fanout goes up. The tree gets shorter, and linked leaves make range scans sequential.
So the honest framing is a tradeoff, not a flaw on either side. Reach for the fanout math whenever a question asks how many keys fit in a block. Reach for the linked-leaf argument whenever a question asks about range queries.
Related reading on DiffStudy:
- Binary Tree vs Binary Search Tree: Key Differences
- Clustered vs Non-Clustered Index
- Data Structure Efficiency: Understanding Time Complexity
- Quad Trees vs KD-Trees
- CS Fundamentals hub
