Tools: Insert Operation: How a B+-Tree Grows Without Losing Order

Step One: Find the Destination Leaf ## Step Two: Insert If There Is Space ## Step Three: Leaf Split When Space Runs Out ## Step Four: Inform the Parent ## Step Five: Propagating the Split Upward ## Root Splitting: The Special Case ## Walking Through the Example ## Why This Algorithm Works So Well ## HexmosTech / git-lrc ## Check AI generated code with Git Hooks ## git-lrc ## See It In Action 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. 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. 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. 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: 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. To reconnect the tree, SQLite inserts a separator entry into the parent of the original leaf. This entry is a pair (K, P): 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. If the parent node is full, the same split procedure applies: This split can propagate upward through multiple levels. In most cases, it stops quickly. But in the worst case, it reaches the root. 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: 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. 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. 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: Check AI-Generated Code With Git Hooks 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. A deliberately invalid Go line is staged for commit. git lrc catches it and blocks the commit before it ever lands. Templates let you quickly answer FAQs or store snippets for re-use. Are you sure you want to hide this comment? It will become hidden in your post, but will still be visible via the comment's permalink. Hide child comments as well For further actions, you may consider blocking this person and/or reporting abuse - a lower half - an upper half - K is the maximum key in the lower (original) leaf - P is a pointer to the new leaf node - 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 - Two new nodes are allocated: L and R - The lower half of N’s entries is moved into L - The upper half is moved into R - Node N is cleared and reused as the new root - A single entry (L, K, R) is placed into N, where K is the maximum key in L - 🤖 AI agents silently break things. Code removed. Logic changed. Edge cases gone. You won't notice until production. - 🔍 Catch it before it ships. AI-powered inline comments show you exactly what changed and what looks wrong. - 🔁 Build a habit, ship better code. Regular review → fewer bugs → more robust code → better results in your team. - 🔗 Why git? Git is universal. Every editor, every IDE, every AI toolkit…