B+ Tree Indexes
Lecture 8 · a B+ tree is a modified version of the B-tree and is more commonly used in database systems.
Definition
In a B+ tree:
- Internal nodes store only search keys.
- Actual record pointers are stored only in leaf nodes.
- Leaf nodes are linked together in sorted order.
Construction — keys 10 … 22, max 3 keys per node
| Insert | Action | Resulting shape |
|---|---|---|
| 10, 11, 12 | Fill the first leaf. | [10 11 12] |
| 13 | Leaf overflows (4 keys) → split 2 | 2 and copy up the separators. The parent keeps the first key of each child. | [10 12] → [10 11] · [12 13] |
| 14 | Goes into the right leaf. | [10 12] → [10 11] · [12 13 14] |
| 15 | [12 13 14 15] overflows → split, copy up 14. | [10 12 14] → [10 11] · [12 13] · [14 15] |
| 16 | Goes into the last leaf. | [10 12 14] → … · [14 15 16] |
| 17 | Leaf overflows → copy up 16, so the root becomes [10 12 14 16] which itself overflows → split the internal node. The height grows. | [10 14] → [10 12] , [14 16] |
| 18 | Goes into the leaf [16 17]. | [10 14] → … leaf [16 17 18] |
| 19 | [16 17 18 19] overflows → split, copy up 18 into the right internal node. | [10 14] → [10 12] , [14 16 18] |
| 20 | Goes into the leaf [18 19]. | leaf [18 19 20] |
| 21 | [18 19 20 21] overflows → copy up 20; the internal node [14 16 18 20] overflows → split it and push 18 up to the root. | [10 14 18] → [10 12] , [14 16] , [18 20] |
| 22 | Goes into the leaf [20 21] → [20 21 22]. No overflow. | final tree below |
Final B+ Tree
Operations
Searching
Start at the root and follow one child pointer per level until you reach a leaf. Every search ends at a leaf node, so every search costs exactly the height of the tree — which makes performance predictable.
Find key = 21 → 21 ≥ 18 → third child
[18 20] → 21 ≥ 20 → leaf [20 21 22] → found. 3 node reads.Range query
WHERE Emp_ID BETWEEN 13 AND 20 → descend once to the leaf containing 13 ([12 13]), then follow the leaf chain right: 13, 14, 15, 16, 17, 18, 19, 20. No further tree traversal is needed — this is exactly what a B-tree cannot do. Insertion & deletion
- Insertion — inserting a new key works the same as the B+ tree construction discussed above (insert into the correct leaf; split and copy up on overflow).
- Deletion — after deleting the key, the tree is restructured following the same rule used for constructing the tree (if needed): borrow from a sibling, or merge two underflowing nodes and remove the separator from the parent.
Fan-out
Fan-out means the number of children a node can have. In a B+ tree, internal nodes store only keys and child pointers — not actual data record pointers — so each internal node can store more keys, which means each node can have more children.
Higher fan-out = fewer tree levels = faster search
Suppose one node can point to 100 child nodes. Then a 3-level B+ tree can index a very large number of records: Root → Internal node → Leaf node. Only a few disk reads may be needed to find a record.
B-Tree vs B+ Tree
| Feature | B-tree | B+ tree |
|---|---|---|
| Data pointer location | Internal and leaf nodes | Only leaf nodes |
| Internal nodes | Store keys and record pointers | Store only keys for navigation |
| Leaf nodes | May or may not be linked | Usually linked |
| Search path | May end at an internal node | Always ends at a leaf node |
| Range query | Less efficient | More efficient |
| Fan-out | Lower | Higher |
| Common in DBMS | Less common | More common |
Why databases prefer B+ trees. Internal nodes carry no data, so more keys fit in one disk page → higher fan-out → shorter tree → fewer disk I/Os. Every search costs the same. And the linked leaves make
BETWEEN, ORDER BY and full scans cheap. In MySQL/InnoDB the primary key is a clustered B+ tree that stores the rows themselves in its leaves. Applied in the project (with a note on the two split conventions): Task 5 — B/B+ tree →