Course contentsShow
← Computer Science
Lesson 1680 of 2,87238. Database Transactions and IndexingFree lesson

B-Tree Insertion Basics

Inserting keys into leaf nodes while maintaining the sorted order and B-Tree properties.

B-Tree Insertion Basics

What you'll learn: How to insert new keys into a B-Tree while preserving its structural properties and maintaining sorted order within nodes.

The Core Idea

When you insert a key into a B-Tree, you always start by finding the correct leaf node where that key belongs. Since B-Trees maintain sorted order within each node, you must insert the new key in its proper position among the existing keys in that leaf.

Think of it like organizing books on a shelf that's already arranged alphabetically. You don't just toss the new book anywhere—you slide it into its correct spot between the books that come before and after it alphabetically.

The Basic Insertion Process

Step 1: Search for the leaf
Use the B-Tree search operation you learned previously to traverse from the root down to the appropriate leaf node where the key should reside.

Step 2: Insert in sorted order
Once you've located the correct leaf, insert the new key while maintaining the sorted sequence. If the leaf contains keys [10, 30, 50] and you're inserting 25, the result becomes [10, 25, 30, 50].

Step 3: Check capacity
B-Trees have a maximum number of keys per node (determined by the tree's order). If the leaf hasn't exceeded this maximum after insertion, you're done! The operation is complete.

Example Walkthrough

Imagine a leaf node in a B-Tree of order 5 (max 4 keys):

  • Current keys: [15, 35, 60]
  • Insert 45: Result is [15, 35, 45, 60] ✓ Done!
  • Insert 20: Result is [15, 20, 35, 45, 60] ✓ Still fits!

Key Takeaway: B-Tree insertion places new keys in the appropriate leaf node while maintaining sorted order; if the node has room, the insertion is straightforward and complete.