A B⁺‑tree is a variant of the B‑tree in which all data (or record pointers) are stored only in the leaf nodes, while internal nodes hold only keys and pointers to child nodes. This structure makes B⁺‑trees especially good for range queries and sequential access, which are common in database workloads.
Because keys are repeated in internal nodes for navigation, B⁺‑trees remain balanced and shallow, so search, insertion, and deletion are all efficient and roughly in cost.
Structure of a B⁺‑Tree
Internal nodes:
Contain keys and child pointers but no data records.
Keys act as separators that guide the search down the tree.
Leaf nodes:
Contain the actual keys and data pointers (or records).
Leaves are linked together in a doubly or singly linked list, enabling fast sequential scans.
This design keeps internal nodes compact and maximizes the branching factor, which keeps the tree short and reduces disk I/O.
How Search Works in a B⁺‑Tree
To search for a key:
Start at the root and follow internal nodes using the stored keys to choose the correct child.
Reach the appropriate leaf node and scan within it to find the exact key and its data pointer.
Range queries (e.g., WHERE key BETWEEN 10 AND 50) are fast because:
The search finds the starting leaf and then follows the leaf‑level links to scan all qualifying keys in order.
Insertion and Deletion
Insertion:
Add the key and pointer to the appropriate leaf.
If the leaf overflows, split it and push a key up to the parent, possibly creating a new level at the root.
Deletion:
Remove the key and pointer from the leaf.
If the leaf becomes underfilled, merge with siblings or redistribute keys to maintain balance.
These operations preserve the B⁺‑tree’s balance and its ability to support both point queries and range/sequential scans.
Why B⁺‑Trees Are Widely Used in DBMS
Excellent for range queries: the linked leaf list and ordered keys make it easy to scan ranges.
Efficient sequential access: you can traverse leaves in order without going back up the tree.
High fan‑out: each node fits in one disk block but holds many keys, so the tree stays shallow.
Good for large databases: scales well with growing data sizes.
For beginners, a B⁺‑tree is like a smart, multi‑level index book where the table of contents (internal nodes) only lists page‑number ranges, and all the detailed information is at the bottom‑level pages (leaf nodes), which are also connected with arrows so you can flip through them in order.
Summary
A B⁺‑tree in DBMS is a balanced, multi‑level index in which all data resides in leaf nodes and internal nodes contain only keys for navigation. This design optimizes search, insertion, deletion, range queries, and sequential scans, making B⁺‑trees one of the most popular indexing structures in modern relational databases and file systems.