B+-Tree Structure: How Order Is Maintained at Scale

Source: Dev.to

What a B‑tree Solves

A B‑tree (the “B” stands for balanced) addresses the practical problem of keeping data sorted, searchable, and efficient when it lives on disk rather than in memory. Binary trees and linked lists are not suitable for this scenario.

B‑trees are height‑balanced, n‑ary trees designed specifically for external storage. In a classic B‑tree, both internal nodes and leaf nodes store actual entries, so search keys and data coexist throughout the tree, providing good performance for inserts, deletes, point lookups, and ordered traversal.

The B⁺‑tree Variant

SQLite primarily uses a B⁺‑tree. Its key characteristics are:

• All actual entries live only in leaf nodes as (key, value) pairs.
• Internal nodes store only keys and child pointers; they act as routing tables, not data holders.
• Because internal nodes contain only separators, they can be packed more densely, reducing tree height and disk I/O during traversal.

Height Balance

Both B‑trees and B⁺‑trees are height‑balanced: every leaf node sits at the same depth. No matter which key you search for, you traverse the same number of levels from the root to a leaf, giving the structure predictability.

Internal Nodes

Internal nodes are decision points that contain:

• An ordered list of keys.
• A corresponding list of child pointers.

For an internal node with an upper bound of n + 1 children:

• It holds at most n keys.
• It holds at most n + 1 child pointers.

The keys act as separators that partition the key space into non‑overlapping ranges:

• The leftmost pointer refers to keys ≤ the first key.
• Each subsequent pointer refers to keys > the previous key and ≤ the next key.
• The rightmost pointer covers keys > the last key.

These separators are not duplicates of data entries; they merely guide the search.

Leaf Nodes

Leaf nodes store the actual data:

• Sorted (key, value) pairs.
• Enough entries to satisfy minimum and maximum occupancy constraints.

In many implementations, including SQLite’s, leaf nodes are linked together in key order. This linked leaf chain makes range scans efficient: after locating the first matching key, the engine can walk forward leaf by leaf without climbing back up the tree. This is why B⁺‑trees excel at queries such as:

SELECT * FROM table WHERE key BETWEEN A AND B;

Node Capacity and the Root

• Internal nodes can have many children—dozens or even hundreds—depending on page size and entry size.
• Implementation‑dependent upper and lower bounds exist, typically with the lower bound around ½ of the upper bound.
• The root node is special: it may violate the minimum occupancy rule and can have as few as one child, simplifying tree growth and shrinkage.

All of this is designed with disk pages in mind; a node’s size matches a page to minimize disk reads and writes.

Search Complexity

Because the tree is height‑balanced and wide, the search complexity is tightly bounded:

• Finding a key requires traversing one internal node per level until a leaf is reached.
• The number of levels grows as O(log m), where m is the total number of entries.

In practice, B⁺‑trees are very shallow—often just two or three levels deep—which explains their dominance in disk‑based database systems decades after their invention.

Supporting Infrastructure

• The pager ensures pages arrive safely in memory.
• The tree module interprets those pages as nodes.
• Cursors traverse nodes without worrying about disk I/O.
• Structural invariants are preserved across crashes and rollbacks.

Understanding the B⁺‑tree shape clarifies why SQLite’s layers are arranged as they are.

What’s Next

Future posts will walk through:

• Search
• Insert
• Delete
• Node splitting and merging

For hands‑on experiments related to SQLite, see the repository: .

Reference
SQLite Database System: Design and Implementation. N.p.: Sibsankar Haldar, (n.d.).