Athreya aka Maneshwar

Posted on Feb 9

Operations on a B+-Tree: How the Search Works

#webdev #programming #database #architecture

Hello, I'm Maneshwar. I'm working on FreeDevTools online currently building "one place for all dev tools, cheat codes, and TLDRs" — a free, open-source hub where developers can quickly find and use tools without any hassle of searching all over the internet.

Up to yesterday, the B+-tree was a static shape in our heads: internal nodes, leaf nodes, keys as separators, data at the leaves. Today’s reading answers the obvious next question:

How does SQLite actually operate on this structure?

In this section, we look at how the tree is used, how entries are found, how iteration works, and why some choices in SQLite differ slightly from textbook implementations.

SQLite supports the standard set of B+-tree operations: search, search-next (ordered traversal), insert, and delete.

Today we focus on the first two, because they explain almost everything about cursor behavior you see at the SQL level.

Search: From Root to Leaf, Deterministically

A search operation begins exactly where you would expect: at the root.

The root of a B+-tree is always an internal node.

It contains a list of keys and child pointers that partition the key space.

Given a search key k, the node is examined to determine which subtree can possibly contain k.

If the node contains keys:

Key(0), Key(1), ..., Key(n-1)

and pointers:

Ptr(0), Ptr(1), ..., Ptr(n)

then the routing rule is simple and strict.

If k > Key(n-1), follow Ptr(n)
Otherwise, find the smallest j such that Key(j-1) < k ≤ Key(j) and follow Ptr(j)

This rule is applied repeatedly. If the chosen child is an internal node, the process continues. Eventually, the search reaches a leaf node, because all paths have the same depth.

Once at a leaf, SQLite performs a binary search over the leaf’s entries to check whether an entry with key k exists.

At that point, the search either:

succeeds and returns the entry, or
fails and reports absence

The important thing to notice is that all decisions above the leaf are routing decisions only. Actual data comparison happens only at the leaf level.

Walking Through the Example

Using the reference tree from Fig. 6.2, suppose we search for key 93.

The search begins at the root node N0. Since 93 < 100, it follows the left pointer to node N1. At N1, 93 > 90, so the search follows the rightmost pointer to node N5.

N5 is a leaf node. A binary search inside N5 finds key 93, and the search succeeds.

If instead we searched for 94, the traversal path would be identical — N0 → N1 → N5 — but the binary search inside N5 would fail. The tree structure tells us where the key would live, even if it doesn’t exist.

That property becomes crucial for insert and delete operations later.

Search-Next: Ordered Traversal Without Leaf Links

The “search next” operation is conceptually simple but structurally subtle in SQLite.

Suppose a previous search (or iteration step) ended at a leaf node N, at index i inside that node.

If there is another entry at index i + 1 within the same leaf, the job is easy. SQLite simply returns that next entry.

The complexity arises when i is the last entry in the leaf.

Because SQLite does not link leaf nodes together, it cannot simply follow a next-leaf pointer. Instead, it must reconstruct the logical successor leaf by walking the tree.

Finding the Logical Next Leaf

When a leaf is exhausted, SQLite climbs upward in the tree.

Starting from the current leaf N, it walks up the parent chain until it finds a node N′ that is not the rightmost child of its parent. If no such node exists, then the traversal has reached the rightmost leaf of the tree, and the operation returns EOT (end of tree).

If such a node N′ exists, suppose it is the j-th child of its parent P. Then the next leaf logically follows from the subtree rooted at Ptr(j + 1).

From there, SQLite descends down the tree, always choosing the leftmost child, until it reaches a leaf. The first entry in that leaf is the result of the search-next operation.

This upward-then-downward traversal is deterministic and preserves sorted order, even without explicit leaf links.

Example: Continuing After a Leaf

Continuing the earlier example, suppose a search for 93 ended at leaf node N5.

There are no entries greater than 93 in N5, and N5 is the rightmost child of its parent N1. However, N1 itself is not the rightmost child of the root N0.

So SQLite climbs up to N0, then descends into the subtree to the right of N1, eventually reaching leaf node N6. The first entry in N6, {110}, is returned.

A subsequent search-next simply advances within N6, returning {120} next.

This is exactly how ordered scans work internally, even though the SQL layer makes them look effortless.

Today we saw how SQLite reads from a B+-tree: point lookups and ordered traversal.

Tomorrow, we move to the harder part: