Case Study • Data Structures

B-tree Insertion Logic

Designing a rule-based learning experience for ordered insertion, overflow detection, and key promotion in balanced tree structures.

B-tree insertion often appears straightforward until learners encounter overflow, median promotion, and split propagation. This module reframes insertion as a structured sequence of visible decisions, helping learners connect local key placement with global tree balance.

The project uses visualization, guided prediction, and step-by-step structural change to support understanding before implementation.

Watch Demo

Project Scope

Curricular Target

Upper-division Data Structures and introductory Algorithms coursework.

Delivery Model

Hybrid instructional module; adaptable for synchronous lecture or asynchronous self-study.

Learner Profile

Computer Science students moving from basic tree concepts to procedural insertion and balancing.

Primary Objective

Enable students to correctly insert keys while explaining why splits and promotions preserve B-tree invariants.

Core Learning Outcomes

Insert keys while preserving sorted order within each node.
Identify overflow conditions and determine when a split is required.
Explain median promotion during leaf, internal, and root-level splits.
Predict how structural changes propagate upward during insertion.

Learning Challenge

Learners often memorize insertion rules without understanding the structural reasoning behind them. Static diagrams usually show only the before-and-after states, making it difficult to track how overflow forms, why the middle key is promoted, and how balancing continues upward through the tree.

Design Strategy

Ordered Insertion First

The module begins with local key placement inside a single node so learners understand sorted insertion before tree-level balancing appears.

Overflow as a Visible Event

Overflow is shown explicitly before restructuring begins, helping learners recognize the condition that triggers a split.

Promotion Through Motion

Median promotion is animated as a visible upward movement so learners can connect local overflow with parent-level balancing.

Patterned Split Logic

Each split follows a consistent sequence—detect overflow, isolate the median, promote, reconnect—so learners build repeatable mental models.

Solution Design

The learning sequence was designed to make B-tree insertion structurally visible and cognitively manageable by separating each major transition into observable steps.

1. Local Ordering Before Hierarchy

The lesson begins with inserting keys into a single node while maintaining sorted order. This allows learners to focus on key placement before introducing balancing across multiple levels.

2. Overflow Detection Before Split

When a node exceeds capacity, the overflow state is shown clearly before the split occurs. This makes the trigger for restructuring explicit rather than implied.

3. Median Promotion as Structural Reasoning

The middle key is highlighted and promoted upward while the remaining keys are redistributed. This makes it easier to understand why the median, not just any key, preserves the B-tree’s ordering constraints.

4. Split Propagation Across Levels

Repeated overflow is modeled as a recursive balancing process. Learners see how one split can trigger another, building a stronger understanding of insertion as a tree-wide structural event.

5. Root Growth as a Visible Outcome

When promotion reaches the root, the animation makes the height increase explicit so learners can see how insertion preserves balanced growth across the tree.

Evaluation & Iteration:

Early learner feedback showed confusion around when a node should split and why the median key moves upward.

The design was revised to stage overflow before restructuring, slow the promotion sequence, and preserve stable subtree alignment during multi-level splits. These changes improved learner predictions and reduced confusion during root-level growth.

Interactive Implementation

The animation functions as a structured model for insertion, overflow detection, and recursive balancing.

Watch actively: pause, predict the next structural change, and decide when a split should occur.

This implementation demonstrates ordered insertion, overflow formation, median promotion, subtree redistribution, and root-level growth.

Guided Worksheet (Pause & Predict)

This worksheet is designed to support active learning during the animation. Pause the video at key moments, predict what will happen next, then continue to confirm or revise your understanding.

Step Example

Before watching the next step:

Where do you think the new key will be inserted?
Do you expect this insertion to cause overflow? Why or why not?
If a split occurs, which key do you think will be promoted?

After watching:

What actually changed in the tree?
Was your prediction correct? Why or why not?

Repeat this process for each major insertion event. Focus on understanding why the structure changes, not just what changes.

Assessment Strategy

This module evaluates understanding through guided practice and short assessment questions focused on structural reasoning.

Formative assessment (during learning): Guided prompts help students predict insertion outcomes and explain why a split does or does not occur.
- Where should the next key be inserted?
- Will this step cause overflow? What evidence supports your answer?
- What do you expect the node to look like after insertion?
Application assessment (structure + process): Students track how local insertion affects higher levels of the tree.
- Which key is promoted during the split?
- How are the remaining keys redistributed?
- Does this split cause another split above it?
Summative assessment (after learning): A short exit check confirms whether students can independently apply insertion logic.
- Why is the median key promoted during a split?
- What happens when the root overflows?
- How does insertion preserve balanced height in a B-tree?

Assessment Activities

Prediction prompts before overflow and split events.
Sketch-and-justify exercises for split outcomes.
Reflection prompts focused on promotion and balance.
Exit-ticket questions aligned to insertion rules and invariants.

Inclusive Design

Captions support multilingual learners and varied processing speeds.
Explicit visual cues reduce cognitive search during overflow and promotion.
Non-color reliant cues reduce reliance on color alone.
Guided worksheet prompts support different learning preferences.

Instructional Impact

The module helps learners move from memorizing insertion steps to understanding how local ordering, overflow, and promotion work together to maintain B-tree balance.