Hello, I’m Maneshwar. I’m working on git-lrc: a Git hook for Checking AI generated code.
AI agents write code fast. They also silently remove logic, change behavior, and introduce bugs — without telling you. You often find out in production.
git-lrc fixes this. It hooks into git commit and reviews every diff before it lands. 60-second setup. Completely free.

Search and search-next showed us how a B+-tree is used.
Insert shows us how it evolves.

An insert is the moment where the tree is allowed to change its shape but only in very controlled ways.

The defining promise of a B+-tree is that it always remains sorted, balanced, and shallow, no matter how many entries are added.

The insert algorithm exists entirely to preserve that promise.

Step One: Find the Destination Leaf

Every insert begins with a normal search.

Given a key k (and its associated data), SQLite first searches the tree to locate the leaf node where k would belong.

This is the same search logic we discussed yesterday: start at the root, follow routing keys through internal nodes, and terminate at a leaf.

If the key k is already present, the operation fails immediately.

SQLite’s B+-trees enforce unique keys, so duplicates are rejected at this point.

If the key is not present, the leaf node we’ve reached is the only valid place where it could be inserted.

Step Two: Insert If There Is Space

If the target leaf has enough free space, the insert is straightforward.

The new (key, data) pair is placed into the leaf in sorted order. No other nodes are touched. No structural changes occur. The insert ends here.

This is the fast path — and in a well-sized tree, it’s the common case.

Step Three: Leaf Split When Space Runs Out

Things get interesting when the leaf node is already full.

In that case, SQLite performs a split.

The existing entries in the leaf, together with the new entry being inserted, are logically sorted and divided into two equal halves:

• a lower half
• an upper half

All keys in the upper half are strictly greater than those in the lower half.

A new leaf node is allocated, and the upper half of the entries is moved into it. The original leaf retains the lower half.

At this point, the data is correct but the tree is no longer connected properly. The parent does not yet know about the new leaf.

Step Four: Inform the Parent

To reconnect the tree, SQLite inserts a separator entry into the parent of the original leaf.

This entry is a pair (K, P):

• K is the maximum key in the lower (original) leaf
• P is a pointer to the new leaf node

This pair tells the parent:
“keys ≤ K go left, keys > K go right”.

If the parent has space for this new entry, it is inserted in sorted order, and the insert operation completes.

If not, the parent itself must be split.

Step Five: Propagating the Split Upward

If the parent node is full, the same split procedure applies:

• Combine existing entries with the new (K, P) pair
• Split them into lower and upper halves
• Allocate a new internal node
• Promote a separator pair to the parent of the parent

This split can propagate upward through multiple levels.

In most cases, it stops quickly. But in the worst case, it reaches the root.

Root Splitting: The Special Case

Splitting the root requires special handling, because the root has no parent — and in SQLite, the root page is never relocated.

Here’s how SQLite handles it.

Let N be the root node. When it becomes full and must be split:

1. Two new nodes are allocated: L and R
2. The lower half of N’s entries is moved into L
3. The upper half is moved into R
4. Node N is cleared and reused as the new root
5. A single entry (L, K, R) is placed into N, where K is the maximum key in L

The depth of the tree increases by one, but all leaves remain at the same depth. The B+-tree remains height-balanced, and no invariants are violated.

This is the only situation where the height of the tree changes.

Walking Through the Example

Using the reference tree from Fig. 6.2, suppose we insert key 200.

The search for 200 terminates at leaf node N8. That node is already full.

SQLite allocates a new leaf node, say N9. The entry 180 is moved from N8 into N9, and the new key 200 is inserted into N9 as well. Now N8 contains the lower half, and N9 contains the upper half.

Next, SQLite inserts a separator pair (170, N9) into the parent of N8. From here, either the parent has room and the insert finishes or the split propagates upward.

Each step preserves sorted order, balance, and correctness.

Why This Algorithm Works So Well

There are a few important properties worth noticing.

First, splits are local. Only nodes along a single root-to-leaf path are affected.

Second, balance is preserved automatically. Every split divides nodes evenly, and all leaves stay at the same depth.

Third, disk locality is respected. Splits happen at page boundaries, which aligns naturally with SQLite’s pager and cache design.

This is why B+-trees scale so gracefully even on disk-backed storage.

👉 Check out: git-lrc
Any feedback or contributors are welcome! It’s online, open-source, and ready for anyone to use.
⭐ Star it on GitHub: