Introduction
A database index must locate records efficiently even when a table contains millions of rows. A search structure that grows too tall can require many page accesses before reaching the required record.
B-Trees and B+ Trees address this problem through balanced structures with many children per node. Their organization supports efficient searches while adapting as records are inserted and deleted.
Why Databases Use Multiway Trees
A binary search tree has at most two children per node. B-Trees and B+ Trees are multiway search trees, meaning a node can have many children.
Their nodes are commonly designed around database pages. A page can hold several keys and child pointers, allowing each node to cover a large portion of the indexed data.
The number of children a node has is its fan-out. High fan-out keeps the tree shallow, reducing the number of pages needed along a search path.
Both structures remain balanced: all leaf nodes are at the same depth.
What Is a B-Tree?
A B-Tree stores sorted search keys across internal nodes and leaf nodes. In the classic organization, keys at either level can have associated records or record references.
Consider this simplified tree:
What is B-Tree ?
The root divides the search space:
Keys below
30belong to the left subtree.Keys between
30and60belong to the middle subtree.Keys above
60belong to the right subtree.
To find 50, compare it with the root keys, follow the middle child, and locate it in [40 | 50].
A search for 30 can finish at the root because a B-Tree may store the associated record reference there.
What Is a B+ Tree?
A B+ Tree uses internal nodes to guide searches. Its leaf level contains the data entries: search keys together with records or record references.
Internal keys act as separators and may also appear at the leaf level.
What is B+ Tree ?
In this illustrative layout, values equal to a separator follow the child to its right.
To find 30:
Read the root separator.
Follow the middle child.
Locate the data entry for
30in the leaf.
Point lookups continue to a leaf, even when the search key appears in an internal node.
Leaf nodes are linked in key order. These links support moving through consecutive entries without restarting a search from the root.
B-Tree vs B+ Tree
Feature | B-Tree | B+ Tree |
|---|---|---|
Data-entry location | Internal and leaf nodes | Leaf nodes |
Internal-node role | Store keys and associated data entries | Guide searches using separator keys |
Search termination | May finish at an internal node | Continues to a leaf |
Leaf links | Not a defining requirement | Typically linked in key order |
Range traversal | Requires navigating the tree | Can continue through linked leaves |
Because B+ Tree internal nodes do not store the associated record payload, they can often fit more separator keys and child pointers into a page. The actual capacity depends on key sizes and implementation.
Why B+ Trees Help Range Queries
Suppose a query needs keys from 40 through 70.
Using the B+ Tree above:
Search for the first qualifying entry,
40.Read
40and50from the current leaf.Follow the leaf link.
Read
60and70.Stop before
80, which exceeds the range.
The qualifying keys are:
40, 50, 60, 70A B-Tree also supports range queries. The B+ Tree’s linked leaf level makes consecutive traversal especially convenient.
However, ordered index traversal does not guarantee the order of a SQL query’s output. Use ORDER BY when output order matters.
Insertion and Deletion
Both trees maintain sorted keys, capacity rules, and balance as entries change.
During insertion, the database locates the appropriate node and adds the entry. If the node overflows, it splits. This can require changes in the parent and may propagate upward. Splitting the root creates a new root and increases the height.
During deletion, the database removes the entry. If a node becomes too empty, entries may be redistributed from a sibling or nodes may be merged. Parent separators are adjusted as needed.
In a B+ Tree, a leaf split typically copies a separator into the parent while retaining the data entry at the leaf level.
Summary
B-Trees and B+ Trees use balanced, multiway branching to keep search paths short. Their main difference is where data entries are stored: B-Trees can store them throughout the tree, while B+ Trees keep them at the leaves.
B+ Trees also connect their leaves in key order, supporting efficient range traversal. Both structures preserve their organization through splits, redistribution, and merges as data changes.
Be the first to add a comment.