In the previous chapter, Indexing in DBMS, we saw that a multilevel index can find any record in just 3 or 4 block accesses. But a static multilevel index has a serious weakness: when rows are inserted or deleted, the sorted index blocks at every level must be shifted and rebuilt.
Real databases receive thousands of inserts per second. They need an index that stays balanced and shallow automatically, no matter how the data changes. That index is the B-tree, and its improved form, the B+ tree, which is the default index structure in MySQL (InnoDB), PostgreSQL, Oracle and SQL Server.
A B+ tree is a balanced, multi-way search tree in which all data entries are stored in the leaf level, the leaves are linked for sequential access, and nodes split or merge automatically so the tree stays shallow.
Why Not a Binary Search Tree?
You know binary search trees (BSTs) from data structures. Why not use them for a disk-based index?
A BST node has only 2 children. For 1 million keys, even a perfectly balanced BST has height about log2(1,000,000) ≈ 20. That means about 20 disk reads per lookup.
Each disk read fetches a whole block (often 4 KB to 16 KB), but a BST node uses only a few bytes of it. Most of every read is wasted.
A plain BST can become unbalanced (degenerate into a linked list) with sorted inserts.
The B-tree fixes all three: each node is one disk block holding many keys and many children (high fan-out), and the tree is always balanced. With a fan-out of a few hundred, three or four levels can index many millions of rows.
A Word About "Order"
Before any definitions, a warning: textbooks define the order of a B-tree differently.
Knuth-style order m = the maximum number of children of a node (so at most m − 1 keys). Most Indian university and GATE questions use this.
Minimum degree t (Cormen/CLRS): every non-root node has at least t − 1 keys and at most 2t − 1 keys.
Some books define order as the minimum number of keys.
In this chapter, order p (or m) means the maximum number of child pointers in a node. In an exam, always check which definition the question uses.
B-Tree
Properties of a B-Tree of Order m
Every node has at most m children and at most m − 1 keys.
Every internal node except the root has at least ⌈m/2⌉ children (so at least ⌈m/2⌉ − 1 keys).
The root has at least 2 children unless it is a leaf (a tree with one node).
A node with k keys has exactly k + 1 children (if it is internal).
Keys inside a node are sorted. All keys in the subtree between keys Ki and Ki+1 lie between those two values.
All leaves are at the same level. This is what "balanced" means.
In a B-tree, every key appears exactly once in the whole tree, and each key is stored with its record pointer (or the record itself), whether the key is in a leaf or an internal node.
Why the "at least half full" rule? It guarantees that the tree cannot become tall and thin. Every node (except the root) branches at least ⌈m/2⌉ ways, so height grows only logarithmically. It also guarantees at least about 50% space utilisation.
Structure of a B-Tree Node
+----+----+------+----+----+------+----+-- ... --+----+----+------+----+
| P1 | K1 | Pr1 | P2 | K2 | Pr2 | P3 | | Pq-1|Kq-1|Prq-1| Pq |
+----+----+------+----+----+------+----+-- ... --+----+----+------+----+
P = tree (child) pointer
K = key
Pr = record (data) pointer for that key
Searching a B-Tree
To search for key x, start at the root:
Look for x among the node's keys. If found, done: follow its record pointer.
Otherwise find the child pointer between the two keys that surround x, and repeat in that child.
If you reach a leaf and x is not there, x does not exist.
A search can stop early, at an internal node, if the key happens to be stored there.
Insertion in a B-Tree
Insertion always happens at a leaf:
Search for the leaf where the key belongs and insert it in sorted position.
If the leaf now has more than m − 1 keys (overflow), split it into two nodes and move the middle key up into the parent.
If the parent overflows, split it too, and so on upwards.
If the root splits, a new root is created. This is the only way a B-tree grows taller, which is why all leaves always stay at the same level.
Trace: order m = 4 (max 3 keys per node). Insert 10, 20, 30, 40, 50, 60, 70, 80, 25, 35, 45. Convention: when a node overflows to 4 keys, the left node keeps the first 2 keys, the 3rd key moves up, and the right node gets the 4th key. (Moving the 2nd key up is equally valid; just be consistent.)
Insert 10, 20, 30:
[10 20 30]
Insert 40 -> [10 20 30 40] overflows, 30 moves up (new root):
[30]
[10 20] [40]
Insert 50, 60 -> go to the right leaf:
[30]
[10 20] [40 50 60]
Insert 70 -> [40 50 60 70] overflows, 60 moves up:
[30 60]
[10 20] [40 50] [70]
Insert 80, 25, 35 -> each fits in its leaf:
[30 60]
[10 20 25] [35 40 50] [70 80]
Insert 45 -> middle leaf [35 40 45 50] overflows, 45 moves up:
[30 45 60]
[10 20 25] [35 40] [50] [70 80]
Notice: 30, 45 and 60 live only in the root. In a B-tree, a key that moves up leaves the leaf; it is not duplicated.
Deletion in a B-Tree (Idea)
If the key is in a leaf, remove it.
If the key is in an internal node, replace it with its in-order predecessor (largest key in the left subtree) or successor, which is always in a leaf, then delete that key from the leaf.
If a node falls below the minimum (underflow), first try to borrow a key from an adjacent sibling through the parent (a rotation). If both siblings are at the minimum, merge with a sibling, pulling the separating key down from the parent. Merging can cascade upwards, and if the root becomes empty the tree's height shrinks by one.
B+ Tree
A B+ tree changes two things about the B-tree, and both turn out to be very important for databases.
Key Differences in Structure
Internal nodes store only keys and child pointers, no record pointers. They are pure "signposts" for navigation.
All data entries (key + record pointer, or the full record) are stored in the leaves. Every key in the table appears in some leaf. Keys may also appear in internal nodes as copies.
Leaves are linked left to right (each leaf has a pointer to the next leaf), so all keys can be read in sorted order by walking the leaf level.
[ 50 ] <- internal: keys + child pointers only
/ \
[30 40] [70] <- internal
/ | \ / \
[10 20 25]->[30 35]->[40 45]->[50 60]->[70 80] <- leaves: every key + record pointer,
linked left to right
Properties of a B+ Tree (order p for internal nodes)
Each internal node has at most p children (p − 1 keys) and, except the root, at least ⌈p/2⌉ children.
The root has at least 2 children if it is internal.
Each leaf holds at most pleaf (key, record pointer) pairs and, unless it is the root, at least ⌈pleaf/2⌉ of them.
All leaves are at the same level.
For a separator key Ki in an internal node: keys in the left subtree are < Ki, keys in the right subtree are ≥ Ki (with this common convention).
Searching a B+ Tree
A search always goes down to a leaf, even if the key appears in an internal node, because only the leaf holds the record pointer. So every successful search costs exactly height node reads. This makes performance very predictable.
Range Search: The B+ Tree's Superpower
Query: find all keys between 28 and 62.
Search down for 28: root [50] → 28 < 50 go left → [30 40] → 28 < 30 go to leaf [10 20 25].
Nothing ≥ 28 there, so follow the leaf link to [30 35], then [40 45], then [50 60], collecting all keys. Move to [70 80]: 70 > 62, stop.
Result: 30, 35, 40, 45, 50, 60.
One root-to-leaf search, then a sequential walk. In a B-tree, the same range is scattered across internal nodes and leaves, so you would need an in-order traversal that jumps up and down the tree. This is the main reason databases prefer B+ trees: queries like BETWEEN, <, >, ORDER BY and prefix LIKE 'abc%' are extremely common.
B+ Tree Insertion
Insertion is like the B-tree, with one crucial difference in how a leaf split works:
Leaf split (copy up): split the overfull leaf into two leaves, and copy the first key of the right leaf into the parent. The key stays in the leaf too, because leaves must contain every key.
Internal node split (push up): split the overfull internal node and move the middle key up into the parent. It does not stay below, because internal keys are only signposts.
Trace: same keys as before: 10, 20, 30, 40, 50, 60, 70, 80, 25, 35, 45. Max 3 keys per node (leaf and internal). Convention: an overfull leaf (4 keys) splits 2 + 2 and copies the right leaf's first key up; an overfull internal node (4 keys) keeps 2 keys on the left, pushes the 3rd key up, and keeps the 4th key on the right.
Insert 10, 20, 30:
[10 20 30]
Insert 40 -> leaf [10 20 30 40] overflows.
Split into [10 20] and [30 40]; COPY 30 up (new root):
[30]
[10 20] [30 40]
Insert 50 -> fits:
[30]
[10 20] [30 40 50]
Insert 60 -> leaf [30 40 50 60] overflows.
Split into [30 40] and [50 60]; copy 50 up:
[30 50]
[10 20] [30 40] [50 60]
Insert 70 -> fits:
[30 50]
[10 20] [30 40] [50 60 70]
Insert 80 -> leaf [50 60 70 80] overflows.
Split into [50 60] and [70 80]; copy 70 up (root now has 3 keys, still OK):
[30 50 70]
[10 20] [30 40] [50 60] [70 80]
Insert 25 and 35 -> both fit:
[30 50 70]
[10 20 25] [30 35 40] [50 60] [70 80]
Insert 45 -> leaf [30 35 40 45] overflows.
Split into [30 35] and [40 45]; copy 40 up.
Parent becomes [30 40 50 70] -> internal overflow!
Split internal: left [30 40], PUSH 50 up, right [70]. New root [50]:
[50]
[30 40] [70]
[10 20 25] [30 35] [40 45] [50 60] [70 80]
Compare the two final trees from the same 11 keys:
B-tree result | B+ tree result |
|---|---|
2 levels, 5 nodes | 3 levels, 8 nodes |
11 keys stored once each | All 11 keys in leaves, plus copies 30, 40, 50, 70 in internal nodes |
With tiny nodes the B+ tree looks worse. In real systems, internal nodes hold only keys and child pointers (no record pointers), so they fit many more entries per block. That higher fan-out usually makes a B+ tree as shallow as, or shallower than, the corresponding B-tree. We will compute this below.
B+ Tree Deletion
Rules (minimum 2 keys per leaf and 1 key per internal node here, i.e., at least half full):
Find the leaf and remove the key.
If the leaf still has at least the minimum number of keys, stop. (A copy of the deleted key may remain in an internal node as a separator; that is allowed, because it still separates the subtrees correctly.)
If the leaf underflows, try to borrow one key from an adjacent sibling that has more than the minimum, and update the separator key in the parent.
If no sibling can lend, merge the leaf with a sibling and delete the separator from the parent. The parent may now underflow, and the same borrow/merge process repeats at the internal level.
If the root ends up with no keys, its single child becomes the new root and the height decreases by one.
Trace on the tree we just built:
Start:
[50]
[30 40] [70]
[10 20 25] [30 35] [40 45] [50 60] [70 80]
Delete 35 -> leaf [30] underflows (1 < 2).
Left sibling [10 20 25] has a spare key: BORROW 25.
Separator 30 in the parent becomes 25 (new first key of the leaf):
[50]
[25 40] [70]
[10 20] [25 30] [40 45] [50 60] [70 80]
Delete 45 -> leaf [40] underflows. Left sibling [25 30] has only 2, cannot lend.
MERGE [25 30] + [40] = [25 30 40]; remove separator 40 from parent:
[50]
[25] [70]
[10 20] [25 30 40] [50 60] [70 80]
Delete 80 -> leaf [70] underflows. Left sibling [50 60] has only 2.
MERGE into [50 60 70]; remove separator 70 -> internal node [ ] underflows.
Its sibling [25] has only 1 key, cannot lend.
MERGE internal nodes: [25] + separator 50 (pulled down from root) + [ ] = [25 50].
Root is now empty -> removed. Height shrinks from 3 to 2:
[25 50]
[10 20] [25 30 40] [50 60 70]
Notice how the tree shrinks only from the top (root removal), just as it grows only from the top (root split). That is why all leaves always stay at the same depth.
Calculating the Order of a B-Tree and a B+ Tree
This is a favourite GATE and university question. The rule is simple: everything a node holds must fit in one block.
Given: block size B = 1024 bytes, search key V = 10 bytes, block (tree) pointer P = 6 bytes, record pointer Pr = 8 bytes.
B+ Tree Internal Node
An internal node with order p has p child pointers and p − 1 keys:
p * P + (p - 1) * V <= B
6p + 10(p - 1) <= 1024
16p <= 1034
p <= 64.6 => p = 64
(check: 64*6 + 63*10 = 1014 <= 1024)
B+ Tree Leaf Node
A leaf holds pleaf (key, record pointer) pairs plus one pointer to the next leaf:
p_leaf * (V + Pr) + P <= B
18 * p_leaf + 6 <= 1024
p_leaf <= 56.55 => p_leaf = 56
(check: 56*18 + 6 = 1014 <= 1024)
B-Tree Node
A B-tree node stores a record pointer with every key:
p * P + (p - 1) * (V + Pr) <= B
6p + 18(p - 1) <= 1024
24p <= 1042
p <= 43.4 => p = 43
(check: 43*6 + 42*18 = 1014 <= 1024)
The B+ tree internal node has fan-out 64 versus 43 for the B-tree, because it does not waste space on record pointers.
How Many Records Can Three Levels Hold?
B+ tree (root + 1 internal level + leaf level), all nodes full:
root: 64 children -> 64 internal nodes -> 64 * 64 = 4096 leaves
records = 4096 * 56 = 229,376
B-tree with 3 levels, all nodes full (order 43, 42 keys per node):
nodes = 1 + 43 + 43*43 = 1893
keys = 1893 * 42 = 79,506 (= 43^3 - 1)
Same block size, same number of levels, and the B+ tree indexes almost three times as many records. That is the concrete reason databases use B+ trees.
Minimum and Maximum Keys in a B-Tree
For a B-tree of order m with h levels (a single root node counts as 1 level):
Maximum keys = mh − 1 (every node full).
Minimum keys = 2⌈m/2⌉h−1 − 1 for h ≥ 2 (root has 1 key, every other node has ⌈m/2⌉ − 1 keys).
Example, m = 5, h = 3: maximum = 53 − 1 = 124; minimum = 2 × 32 − 1 = 17 (root 1 key, 2 internal nodes with 2 keys each, 6 leaves with 2 keys each: 1 + 4 + 12 = 17).
B-Tree vs B+ Tree
Feature | B-Tree | B+ Tree |
|---|---|---|
Where data (record pointers) live | In every node, internal and leaf | Only in leaf nodes |
Duplicate keys in internal nodes | No, each key appears once | Yes, internal keys are copies used as separators |
Fan-out of internal nodes | Lower | Higher (no record pointers) |
Height for the same data | Often greater | Often smaller |
Search | May end early at an internal node | Always reaches a leaf (predictable cost) |
Range queries / sorted scan | Needs in-order traversal across levels | One search + walk the linked leaves |
Leaf split on insert | Middle key moves up | Separator key is copied up |
Typical use | Mostly textbooks and exams; real systems almost always use the B+ variant | Default index in almost all relational DBMSs |
B+ Trees in Real Databases
MySQL InnoDB uses B+ trees for both the clustered (primary key) index and secondary indexes. The default page size is 16 KB, so a node can hold hundreds of entries and even very large tables need only a few levels.
The leaf level of the InnoDB clustered index contains the full rows, so a primary-key lookup ends with the row in hand. Secondary-index leaves contain the primary-key values.
The top levels of a busy B+ tree stay cached in memory (the buffer pool), so in practice a lookup often costs just one or two actual disk reads.
Inserting keys in increasing order (like an AUTO_INCREMENT id) always adds to the rightmost leaf, which keeps splits cheap. Random keys (like random UUIDs) cause splits all over the tree and more page fragmentation.
Common Mistakes
Mixing up order definitions. Check whether "order" means max children, max keys, or minimum degree.
Moving the key up on a B+ leaf split. At the leaf level the key is copied up; it must remain in the leaf.
Copying the key on an internal split. At internal levels the middle key is moved up.
Forgetting the next-leaf pointer when calculating B+ leaf capacity.
Forgetting record pointers when calculating B-tree order (every key in a B-tree carries one).
Thinking B-trees grow at the leaves. They grow (and shrink) only at the root.
Calling the "B" in B-tree "binary". It is not binary; B-trees are multi-way trees. (The inventors, Rudolf Bayer and Edward McCreight, never officially said what the B stands for; "balanced", "Boeing" and "Bayer" are popular guesses.)
Interview Questions
1. Why do databases use B+ trees instead of binary search trees?
A B+ tree node fills a whole disk block and has hundreds of children, so the tree is only 3 to 4 levels deep for millions of keys, meaning very few disk reads. It also stays balanced automatically. A BST has fan-out 2, so it is far deeper and wastes most of each block read.
2. What is the main difference between a B-tree and a B+ tree?
In a B+ tree all data entries are in the leaves and the leaves are linked; internal nodes only guide the search. In a B-tree, data pointers are stored in every node and each key appears once.
3. Why are B+ trees better for range queries?
After one search to the first matching leaf, the DBMS simply follows the leaf links in sorted order. No back-and-forth traversal of internal nodes is needed.
4. How does a B+ tree stay balanced?
Inserts that overflow a node split it and push a separator up; deletes that underflow borrow from or merge with siblings. The height changes only when the root splits or disappears, so all leaves stay at the same depth.
5. Why does a B+ tree have a higher fan-out than a B-tree with the same block size?
B+ internal nodes store only keys and child pointers. B-tree nodes also store a record pointer per key, which takes space that could have held more keys.
6. What is the minimum occupancy of a B+ tree node, and why?
Every non-root node must be at least half full (⌈p/2⌉ children for internal nodes). This keeps the tree shallow and space utilisation at least about 50%.
7. What is the time complexity of search, insert and delete in a B+ tree?
O(log n) for all three, more precisely O(logf n) node accesses where f is the fan-out.
Summary
B-trees and B+ trees are balanced, multi-way, disk-friendly search trees: one node = one block.
Every non-root node is at least half full, and all leaves are at the same level.
Insertion splits overfull nodes; deletion borrows or merges. The tree grows and shrinks only at the root.
B-tree: each key stored once, with its record pointer, in any node.
B+ tree: all data in linked leaves; internal nodes hold separator copies. Leaf split copies up, internal split pushes up.
To find the order, make one node fit in one block. B+ internal nodes have a higher fan-out than B-tree nodes.
B+ trees are the default index in relational databases because of high fan-out, predictable lookups and fast range scans.
B-tree: data everywhere. B+ tree: data in the leaves, and the leaves hold hands.