Database Management Systems (DBMS) Module 9 – Indexing

B+ tree insertion and deletion: step by step

How a B+ tree inserts and deletes keys: leaf splits that copy a key up, internal splits that push one up, borrowing and merging, traced in a simulator.

Intermediate
20 minutes
Examples run with sql.js 1.14.2, Python 3.14.8 and Pyodide 314.0.7
By MySmartCoPilot

Free: Three rules hold after every change · Insertion splits full nodes and grows the tree at the root · Deletion: borrow first, merge when you must · Practise: split an overfull leaf and an overfull node. With a pass: 2 in-depth parts and 3 interview answers, about 13 minutes.

What you will learn

Trace B+ tree insertion through leaf and internal splits, and tell a copied-up key from a pushed-up one
Delete keys with borrowing from a sibling and merging, up to the root
Build a B+ tree bottom-up from sorted data and choose a fill factor
Check a B+ tree against its invariants after every change

Before you start

B-trees and B+ trees: structure and order

What you’ll learn · Before you start

What you will learn

Trace B+ tree insertion through leaf and internal splits, and tell a copied-up key from a pushed-up one
Delete keys with borrowing from a sibling and merging, up to the root
Build a B+ tree bottom-up from sorted data and choose a fill factor
Check a B+ tree against its invariants after every change

Before you start

B-trees and B+ trees: structure and order

On this page

Eleven keys inserted into an empty B+ tree of at most 3 keys a node cause four leaf splits and one internal split, and the tree grows to 3 levels with every leaf at the same depth. Every change starts at a leaf and works upwards. B+ tree insertion puts the key into its leaf; an overflowing leaf splits and copies its right half’s first key into the parent, and an overflowing parent splits too and pushes its middle key up. Deletion removes the key; a leaf left under half full borrows one from a sibling, or merges with it when none can spare one.

Three rules hold after every change

A B+ tree is correct when these hold after every operation:

Keys in each node are sorted, and each internal node with k keys has k + 1 children. Child i holds keys below the node’s key i, and child i + 1 holds keys from key i upwards.
Every leaf is at the same depth, and the leaves are linked left to right in key order.
No node holds more keys than the maximum, and every node except the root holds at least about half of it.

This lesson uses small nodes so that every change is visible: at most 3 keys in a node, at least 2 keys in a leaf and at least 2 children in an internal node. When a split cannot share its keys evenly, the left node keeps the extra one. Books and exam papers also use the opposite rule, so the convention is part of every answer. Step through the rules on the tree the eleven inserts build:

Interactive · step by step The tree after the eleven inserts, rule by rule The root sits on the left between the two nodes under it, and the leaves are on the right. Step through the rules every change must keep.

The drawing shows the whole scene; its 6 steps are listed below.

Every step as text

Eleven inserts later. This is the tree the eleven inserts build. The root, 50, sits between the two nodes under it, 25 · 40 above and 60 below, and the five leaves are on the right, in key order. Every rule below holds in it.
One child more than keys. The node 25 · 40 holds its keys in order and has three children, one more than its keys. Every internal node with k keys has k + 1 children.
Each child holds a range. Its middle child holds the keys from 25 up to below 40, so 25, 30 and 35 are there. A search for 30 follows the ranges down and reads no other leaf.
Every leaf at one depth. Every leaf is two steps from the root, so every search reads exactly three nodes, whichever key it looks for.
Leaves linked in order. The dashed links chain the leaves in key order, so a range of keys is read leaf after leaf without climbing back up the tree.
Full, but never too empty. No node holds more than 3 keys, and every node but the root keeps at least 2 keys in a leaf or 2 children above the leaves. The node 60 is exactly at that minimum.

Checkpoint

Check: The rules every change keeps

Question 1 of 2 An internal node of a B+ tree holds 3 keys. How many children does it have?
Type a number.
Your answer children

Show the answer: Question 1 of 2

Answer: 4 children

An internal node with k keys has k + 1 children: the keys are the boundaries between the children's ranges, so 3 keys separate 4 ranges.
Question 2 of 2 Nodes hold at most 3 keys and a leaf at least 2. Which of these trees breaks a rule? Each is written root first, then its leaves.
Choose one answer.

A single leaf [10, 20], with no root above it Root [30], leaves [10, 20, 25] and [30, 40, 50] Root [30], leaves [10, 20] and [30, 40] Root [30], leaves [10] and [30, 40]

Show the answer: Question 2 of 2

Answer: Root [30], leaves [10] and [30, 40]

The size rules are a maximum of 3 keys for every node and a minimum of 2 keys for every leaf but the root. The tree with the leaf [10] breaks the minimum; a delete that left it so would have to borrow or merge.

Insertion splits full nodes and grows the tree at the root

B+ tree insertion follows one path down and, at most, one path back up:

Search from the root to the leaf where the key belongs, and put the key there in sorted order.
If the leaf now holds too many keys, split it into two leaves and copy the right leaf’s first key into the parent as the separator between them. The key stays in its leaf, because every key of a B+ tree lives in a leaf.
If the parent now holds too many keys, split it as well and push its middle key up: the key moves to the grandparent and stays in neither half. A split of the root creates a new root, and the tree grows one level.

The two splits of B+ tree insertion: a leaf split copies its separator up, an internal split pushes its middle key up

Text description of the diagram

Top, a leaf split. Before: a parent holding 40 and 60 above a leaf holding 10, 20, 25 and 30, drawn with a dashed border because 4 keys are one more than a node may hold. After: the leaf has become two leaves, 10 and 20, then 25 and 30, linked left to right, and the parent holds 25, 40 and 60. The key 25 is highlighted in the parent and in the right leaf: it was copied up and is still in its leaf.

Bottom, an internal split. Before: an internal node holding 25, 40, 50 and 60, dashed because it is overfull, with 50 highlighted. After: a new root holding only 50, with two children, one holding 25 and 40 and one holding 60. The key 50 moved up and is in neither half.

Step through the last of the eleven inserts, 55, which causes both kinds of split:

Interactive · step by step Inserting 55, the insert that splits twice Step through the last insert. Watch which key is copied, which one moves, and where the tree grows.

The drawing shows the whole scene; its 7 steps are listed below.

Every step as text

Before 55. The tree has 2 levels. Its upper node, the root, holds 25, 40 and 60, the most a node may hold, and 55 belongs in the leaf holding 40, 45 and 50. The other three leaves take no part.
55 overflows the leaf. 55 goes into the leaf in sorted order. Four keys are one more than a node may hold, so the leaf splits.
The leaf splits. The leaf keeps 40 and 45, and a new leaf to its right takes 50 and 55. Four keys share evenly, two and two.
50 is copied up. The new leaf's first key, 50, is copied into the upper node as the separator between the two leaves. 50 also stays in its leaf, where its record is.
The upper node overflows. The upper node now holds 4 keys, one too many. An internal node splits as well, but its middle key stays in neither half.
The upper node splits. The upper node keeps 25 and 40 with their three children. A new upper node takes 60 and the last two children, among them the new leaf.
50 moves up. 50 moves up into a new root of its own and is now in neither upper node. The tree has 3 levels; it grew at the top, so every leaf is still at the same depth.

The same eleven inserts as one program, which prints every split as it happens:

One program · 13 languages Eleven inserts into a B+ tree of 3 keys a node O(h) nodes visited and split per insert, h levels

Python 3.14 · main.py

# B+ tree insertion: at most 3 keys a node; the left half keeps an extra key.
MAX_KEYS = 3


class Node:
    def __init__(self, keys: list[int], children: list["Node"] | None = None) -> None:
        self.keys = keys
        self.children = children or []  # empty in a leaf


def insert(node: Node, key: int) -> tuple[int, Node] | None:
    i = sum(1 for k in node.keys if k <= key)
    if not node.children:
        node.keys.insert(i, key)
    elif split := insert(node.children[i], key):
        node.keys.insert(i, split[0])
        node.children.insert(i + 1, split[1])
        print(f"  parent now {node.keys}")
    if len(node.keys) <= MAX_KEYS:
        return None
    if not node.children:
        # Leaf split: the right half's first key is copied up.
        cut = (len(node.keys) + 1) // 2
        right = Node(node.keys[cut:])
        node.keys = node.keys[:cut]
        print(f"  leaf split {node.keys} | {right.keys}, copy {right.keys[0]} up")
        return right.keys[0], right
    # Internal split: the middle key moves up, into neither half.
    cut = len(node.keys) // 2
    up = node.keys[cut]
    right = Node(node.keys[cut + 1 :], node.children[cut + 1 :])
    node.keys, node.children = node.keys[:cut], node.children[: cut + 1]
    print(f"  internal split {node.keys} | {right.keys}, push {up} up")
    return up, right


root = Node([])
for key in [20, 50, 10, 40, 30, 60, 70, 25, 35, 45, 55]:
    print(f"insert {key}")
    if split := insert(root, key):
        root = Node([split[0]], [root, split[1]])
        print(f"  new root {root.keys}")

In Python: elif split := insert(...) assigns and tests in one step, and slicing copies the halves, so the left node and the new one never share a list.

Recorded with CPython 3.14.8 on macOS 26 arm64. It runs in your browser with Pyodide 314.0.7 (CPython 3.14.2). To run it yourself: python3 main.py

JavaScript Node 24 · main.mjs

// B+ tree insertion: at most 3 keys a node; the left half keeps an extra key.
const MAX_KEYS = 3;
const text = (keys) => `[${keys.join(", ")}]`;

function insert(node, key) {
  const i = node.keys.filter((k) => k <= key).length;
  if (node.children.length === 0) {
    node.keys.splice(i, 0, key);
  } else {
    const split = insert(node.children[i], key);
    if (split !== null) {
      node.keys.splice(i, 0, split[0]);
      node.children.splice(i + 1, 0, split[1]);
      console.log(`  parent now ${text(node.keys)}`);
    }
  }
  if (node.keys.length <= MAX_KEYS) return null;
  if (node.children.length === 0) {
    // Leaf split: the right half's first key is copied up.
    const right = { keys: node.keys.splice(Math.ceil(node.keys.length / 2)), children: [] };
    console.log(`  leaf split ${text(node.keys)} | ${text(right.keys)}, copy ${right.keys[0]} up`);
    return [right.keys[0], right];
  }
  // Internal split: the middle key moves up, into neither half.
  const cut = Math.floor(node.keys.length / 2);
  const right = { keys: node.keys.splice(cut + 1), children: node.children.splice(cut + 1) };
  const up = node.keys.pop();
  console.log(`  internal split ${text(node.keys)} | ${text(right.keys)}, push ${up} up`);
  return [up, right];
}

let root = { keys: [], children: [] };
for (const key of [20, 50, 10, 40, 30, 60, 70, 25, 35, 45, 55]) {
  console.log(`insert ${key}`);
  const split = insert(root, key);
  if (split !== null) {
    root = { keys: [split[0]], children: [root, split[1]] };
    console.log(`  new root ${text(root.keys)}`);
  }
}

In JavaScript: splice(cut) removes the right half from node.keys and returns it, so one call both shrinks the left node and fills the new one.

Recorded with Node.js 24.21.0 LTS (V8 13.6) on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0). To run it yourself: node main.mjs

Java 25 LTS · Main.java

import java.util.ArrayList;
import java.util.List;

public class Main {
  // B+ tree insertion: at most 3 keys a node; the left half keeps an extra key.
  static final int MAX_KEYS = 3;

  record Node(List<Integer> keys, List<Node> children) { // children: empty in a leaf
    Node {
      keys = new ArrayList<>(keys);
      children = new ArrayList<>(children);
    }
  }

  record Split(int separator, Node right) {}

  static <T> List<T> cut(List<T> from, int start) {
    List<T> moved = new ArrayList<>(from.subList(start, from.size()));
    from.subList(start, from.size()).clear();
    return moved;
  }

  static Split insert(Node node, int key) {
    int i = (int) node.keys().stream().filter(k -> k <= key).count();
    if (node.children().isEmpty()) {
      node.keys().add(i, key);
    } else {
      Split split = insert(node.children().get(i), key);
      if (split != null) {
        node.keys().add(i, split.separator());
        node.children().add(i + 1, split.right());
        System.out.println("  parent now " + node.keys());
      }
    }
    int count = node.keys().size();
    if (count <= MAX_KEYS) {
      return null;
    }
    if (node.children().isEmpty()) {
      // Leaf split: the right half's first key is copied up.
      Node right = new Node(cut(node.keys(), (count + 1) / 2), List.of());
      int up = right.keys().get(0);
      System.out.println(
          "  leaf split " + node.keys() + " | " + right.keys() + ", copy " + up + " up");
      return new Split(up, right);
    }
    // Internal split: the middle key moves up, into neither half.
    Node right = new Node(cut(node.keys(), count / 2 + 1), cut(node.children(), count / 2 + 1));
    int up = node.keys().remove(count / 2);
    System.out.println(
        "  internal split " + node.keys() + " | " + right.keys() + ", push " + up + " up");
    return new Split(up, right);
  }

  public static void main(String[] args) {
    Node root = new Node(List.of(), List.of());
    for (int key : new int[] {20, 50, 10, 40, 30, 60, 70, 25, 35, 45, 55}) {
      System.out.println("insert " + key);
      Split split = insert(root, key);
      if (split != null) {
        root = new Node(List.of(split.separator()), List.of(root, split.right()));
        System.out.println("  new root " + root.keys());
      }
    }
  }
}

In Java: The record's compact constructor copies both lists, so no node shares a list with List.of(...), and cut moves the tail of a list into a new one.

Recorded with OpenJDK 25.0.4.1 LTS (Eclipse Temurin) on macOS 26 arm64. It runs in your browser with a TeaVM 0.16.0 build in QuickJS (quickjs-emscripten 0.32.0). To run it yourself: java Main.java

C++23 · main.cpp

#include <algorithm>
#include <memory>
#include <optional>
#include <print>
#include <utility>
#include <vector>

// B+ tree insertion: at most 3 keys a node; the left half keeps an extra key.
constexpr int max_keys = 3;

struct Node {
  std::vector<int> keys;
  std::vector<std::unique_ptr<Node>> children; // empty in a leaf
};

using Split = std::pair<int, std::unique_ptr<Node>>;

std::optional<Split> insert(Node &node, int key) {
  const auto i =
      std::ranges::count_if(node.keys, [key](int k) { return k <= key; });
  if (node.children.empty()) {
    node.keys.insert(node.keys.begin() + i, key);
  } else if (auto split = insert(*node.children[i], key)) {
    node.keys.insert(node.keys.begin() + i, split->first);
    node.children.insert(node.children.begin() + i + 1,
                         std::move(split->second));
    std::println("  parent now {}", node.keys);
  }
  const auto count = std::ssize(node.keys);
  if (count <= max_keys)
    return std::nullopt;
  auto right = std::make_unique<Node>();
  if (node.children.empty()) {
    // Leaf split: the right half's first key is copied up.
    right->keys.assign(node.keys.begin() + (count + 1) / 2, node.keys.end());
    node.keys.resize((count + 1) / 2);
    std::println("  leaf split {} | {}, copy {} up", node.keys, right->keys,
                 right->keys[0]);
    return Split{right->keys[0], std::move(right)};
  }
  // Internal split: the middle key moves up, into neither half.
  const int up = node.keys[count / 2];
  right->keys.assign(node.keys.begin() + count / 2 + 1, node.keys.end());
  std::ranges::move(node.children.begin() + count / 2 + 1, node.children.end(),
                    std::back_inserter(right->children));
  node.keys.resize(count / 2);
  node.children.resize(count / 2 + 1);
  std::println("  internal split {} | {}, push {} up", node.keys, right->keys,
               up);
  return Split{up, std::move(right)};
}

int main() {
  auto root = std::make_unique<Node>();
  for (const int key : {20, 50, 10, 40, 30, 60, 70, 25, 35, 45, 55}) {
    std::println("insert {}", key);
    if (auto split = insert(*root, key)) {
      auto top = std::make_unique<Node>(Node{{split->first}, {}});
      top->children.push_back(std::move(root));
      top->children.push_back(std::move(split->second));
      root = std::move(top);
      std::println("  new root {}", root->keys);
    }
  }
}

In C++: Children are std::unique_ptr, so the tree frees itself, and std::ranges::move hands the right half's children to the new node without copying them.

Recorded with Apple clang 21.0.0 (C++23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang++ -std=c++23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.cpp -o main && ./main

C# 14 · .NET 10 · app.cs

using System.Globalization;

CultureInfo.CurrentCulture = CultureInfo.InvariantCulture;

// B+ tree insertion: at most 3 keys a node; the left half keeps an extra key.
const int MaxKeys = 3;

var root = new Node([], []);
foreach (int key in new[] { 20, 50, 10, 40, 30, 60, 70, 25, 35, 45, 55 })
{
    Console.WriteLine($"insert {key}");
    if (Insert(root, key) is (int separator, Node right))
    {
        root = new Node([separator], [root, right]);
        Console.WriteLine($"  new root {Text(root.Keys)}");
    }
}

static string Text(List<int> keys) => $"[{string.Join(", ", keys)}]";

static (int Separator, Node Right)? Insert(Node node, int key)
{
    int i = node.Keys.Count(k => k <= key);
    if (node.Children.Count == 0)
    {
        node.Keys.Insert(i, key);
    }
    else if (Insert(node.Children[i], key) is (int lifted, Node sibling))
    {
        node.Keys.Insert(i, lifted);
        node.Children.Insert(i + 1, sibling);
        Console.WriteLine($"  parent now {Text(node.Keys)}");
    }
    int count = node.Keys.Count;
    if (count <= MaxKeys)
    {
        return null;
    }
    if (node.Children.Count == 0)
    {
        // Leaf split: the right half's first key is copied up.
        int cut = (count + 1) / 2;
        var leaf = new Node(node.Keys[cut..], []);
        node.Keys.RemoveRange(cut, count - cut);
        Console.WriteLine(
            $"  leaf split {Text(node.Keys)} | {Text(leaf.Keys)}, copy {leaf.Keys[0]} up");
        return (leaf.Keys[0], leaf);
    }
    // Internal split: the middle key moves up, into neither half.
    int middle = count / 2;
    int up = node.Keys[middle];
    var half = new Node(node.Keys[(middle + 1)..], node.Children[(middle + 1)..]);
    node.Keys.RemoveRange(middle, count - middle);
    node.Children.RemoveRange(middle + 1, count - middle);
    Console.WriteLine($"  internal split {Text(node.Keys)} | {Text(half.Keys)}, push {up} up");
    return (up, half);
}

// Children is empty in a leaf.
sealed record Node(List<int> Keys, List<Node> Children);

In C#: Insert(...) is (int lifted, Node sibling) tests the nullable tuple and takes it apart in one step; node.Keys[cut..] copies the right half into a new list.

Recorded with C# 14 on .NET 10.0.12 (SDK 10.0.401) on macOS 26 arm64. It runs in your browser with the .NET runtime for WebAssembly 10.0.12. To run it yourself: dotnet run app.cs

C23 · main.c

C is left out of this example: C's standard library has no growable list, so each node needs fixed arrays shifted by memmove and its own allocation and freeing: about twice the code.

PHP 8.5 · main.php

<?php

declare(strict_types=1);

// B+ tree insertion: at most 3 keys a node; the left half keeps an extra key.
const MAX_KEYS = 3;

final class Node
{
    /**
     * @param list<int> $keys
     * @param list<Node> $children empty in a leaf
     */
    public function __construct(public array $keys, public array $children = []) {}
}

/** @param list<int> $keys */
function text(array $keys): string
{
    return '[' . implode(', ', $keys) . ']';
}

/** @return array{int, Node}|null */
function insert(Node $node, int $key): ?array
{
    $i = count(array_filter($node->keys, fn(int $k): bool => $k <= $key));
    if ($node->children === []) {
        array_splice($node->keys, $i, 0, [$key]);
    } elseif (($split = insert($node->children[$i], $key)) !== null) {
        array_splice($node->keys, $i, 0, [$split[0]]);
        array_splice($node->children, $i + 1, 0, [$split[1]]);
        echo '  parent now ', text($node->keys), "\n";
    }
    $count = count($node->keys);
    if ($count <= MAX_KEYS) {
        return null;
    }
    if ($node->children === []) {
        // Leaf split: the right half's first key is copied up.
        $right = new Node(array_splice($node->keys, intdiv($count + 1, 2)));
        $halves = text($node->keys) . ' | ' . text($right->keys);
        echo "  leaf split {$halves}, copy {$right->keys[0]} up\n";
        return [$right->keys[0], $right];
    }
    // Internal split: the middle key moves up, into neither half.
    $cut = intdiv($count, 2);
    $right = new Node(array_splice($node->keys, $cut + 1), array_splice($node->children, $cut + 1));
    $up = array_pop($node->keys);
    echo '  internal split ', text($node->keys), ' | ', text($right->keys), ", push {$up} up\n";
    return [$up, $right];
}

$root = new Node([]);
foreach ([20, 50, 10, 40, 30, 60, 70, 25, 35, 45, 55] as $key) {
    echo "insert {$key}\n";
    if (($split = insert($root, $key)) !== null) {
        $root = new Node([$split[0]], [$root, $split[1]]);
        echo '  new root ', text($root->keys), "\n";
    }
}

In PHP: array_splice with an offset and no length removes the tail of the array and returns it, as JavaScript's splice does.

Recorded with PHP 8.5.11 (CLI) on macOS 26 arm64. It runs in your browser with php-wasm 0.2.0 (PHP 8.5.2). To run it yourself: php main.php

Rust 1.99 · main.rs

// B+ tree insertion: at most 3 keys a node; the left half keeps an extra key.
const MAX_KEYS: usize = 3;

struct Node {
    keys: Vec<i32>,
    children: Vec<Node>, // empty in a leaf
}

fn insert(node: &mut Node, key: i32) -> Option<(i32, Node)> {
    let i = node.keys.iter().filter(|&&k| k <= key).count();
    if node.children.is_empty() {
        node.keys.insert(i, key);
    } else if let Some((up, right)) = insert(&mut node.children[i], key) {
        node.keys.insert(i, up);
        node.children.insert(i + 1, right);
        println!("  parent now {:?}", node.keys);
    }
    let count = node.keys.len();
    if count <= MAX_KEYS {
        return None;
    }
    if node.children.is_empty() {
        // Leaf split: the right half's first key is copied up.
        let keys = node.keys.split_off(count.div_ceil(2));
        println!(
            "  leaf split {:?} | {keys:?}, copy {} up",
            node.keys, keys[0]
        );
        let children = Vec::new();
        return Some((keys[0], Node { keys, children }));
    }
    // Internal split: the middle key moves up, into neither half.
    let keys = node.keys.split_off(count / 2 + 1);
    let children = node.children.split_off(count / 2 + 1);
    let up = node.keys.remove(count / 2);
    println!("  internal split {:?} | {keys:?}, push {up} up", node.keys);
    Some((up, Node { keys, children }))
}

fn main() {
    let mut root = Node {
        keys: Vec::new(),
        children: Vec::new(),
    };
    for key in [20, 50, 10, 40, 30, 60, 70, 25, 35, 45, 55] {
        println!("insert {key}");
        if let Some((up, right)) = insert(&mut root, key) {
            let old = std::mem::replace(
                &mut root,
                Node {
                    keys: vec![up],
                    children: Vec::new(),
                },
            );
            root.children = vec![old, right];
            println!("  new root {:?}", root.keys);
        }
    }
}

In Rust: split_off(at) moves the tail of a Vec into a new one, and std::mem::replace swaps the old root out so that it can become a child of the new one.

Recorded with rustc 1.99.0 (edition 2024) on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: rustc --edition 2024 -O main.rs && ./main

TypeScript 6.0 · main.ts

// B+ tree insertion: at most 3 keys a node; the left half keeps an extra key.
type TreeNode = { keys: number[]; children: TreeNode[] };
type Split = [separator: number, right: TreeNode];

const MAX_KEYS = 3;
const text = (keys: number[]): string => `[${keys.join(", ")}]`;

function insert(node: TreeNode, key: number): Split | null {
  const i = node.keys.filter((k) => k <= key).length;
  if (node.children.length === 0) {
    node.keys.splice(i, 0, key);
  } else {
    const split = insert(node.children[i], key);
    if (split !== null) {
      node.keys.splice(i, 0, split[0]);
      node.children.splice(i + 1, 0, split[1]);
      console.log(`  parent now ${text(node.keys)}`);
    }
  }
  if (node.keys.length <= MAX_KEYS) return null;
  if (node.children.length === 0) {
    // Leaf split: the right half's first key is copied up.
    const right = { keys: node.keys.splice(Math.ceil(node.keys.length / 2)), children: [] };
    console.log(`  leaf split ${text(node.keys)} | ${text(right.keys)}, copy ${right.keys[0]} up`);
    return [right.keys[0], right];
  }
  // Internal split: the middle key moves up, into neither half.
  const cut = Math.floor(node.keys.length / 2);
  const right = { keys: node.keys.splice(cut + 1), children: node.children.splice(cut + 1) };
  const up = node.keys.pop() as number;
  console.log(`  internal split ${text(node.keys)} | ${text(right.keys)}, push ${up} up`);
  return [up, right];
}

let root: TreeNode = { keys: [], children: [] };
for (const key of [20, 50, 10, 40, 30, 60, 70, 25, 35, 45, 55]) {
  console.log(`insert ${key}`);
  const split = insert(root, key);
  if (split !== null) {
    root = { keys: [split[0]], children: [root, split[1]] };
    console.log(`  new root ${text(root.keys)}`);
  }
}

In TypeScript: The labelled tuple [separator: number, right: TreeNode] names what a split returns; pop() as number is safe because the node holds four keys.

Recorded with TypeScript 6.0.3 (strict), run by Node.js 24.21.0 on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0) after Sucrase 3.35.1. To run it yourself: npx -p typescript@6.0.3 tsc --noEmit --strict main.ts && node main.ts

Go 1.27 · main.go

package main

import (
	"fmt"
	"slices"
	"strings"
)

// B+ tree insertion: at most 3 keys a node; the left half keeps an extra key.
const maxKeys = 3

type node struct {
	keys     []int
	children []*node // empty in a leaf
}

func text(keys []int) string { return strings.ReplaceAll(fmt.Sprint(keys), " ", ", ") }

func insert(n *node, key int) (int, *node) {
	i := 0
	for i < len(n.keys) && n.keys[i] <= key {
		i++
	}
	if len(n.children) == 0 {
		n.keys = slices.Insert(n.keys, i, key)
	} else if up, right := insert(n.children[i], key); right != nil {
		n.keys = slices.Insert(n.keys, i, up)
		n.children = slices.Insert(n.children, i+1, right)
		fmt.Println("  parent now", text(n.keys))
	}
	if len(n.keys) <= maxKeys {
		return 0, nil
	}
	if len(n.children) == 0 {
		// Leaf split: the right half's first key is copied up.
		cut := (len(n.keys) + 1) / 2
		right := &node{keys: slices.Clone(n.keys[cut:])}
		n.keys = n.keys[:cut]
		fmt.Printf("  leaf split %s | %s, copy %d up\n",
			text(n.keys), text(right.keys), right.keys[0])
		return right.keys[0], right
	}
	// Internal split: the middle key moves up, into neither half.
	cut := len(n.keys) / 2
	up := n.keys[cut]
	right := &node{keys: slices.Clone(n.keys[cut+1:]), children: slices.Clone(n.children[cut+1:])}
	n.keys, n.children = n.keys[:cut], n.children[:cut+1]
	fmt.Printf("  internal split %s | %s, push %d up\n", text(n.keys), text(right.keys), up)
	return up, right
}

func main() {
	root := &node{}
	for _, key := range []int{20, 50, 10, 40, 30, 60, 70, 25, 35, 45, 55} {
		fmt.Println("insert", key)
		if up, right := insert(root, key); right != nil {
			root = &node{keys: []int{up}, children: []*node{root, right}}
			fmt.Println("  new root", text(root.keys))
		}
	}
}

In Go: slices.Insert and slices.Clone keep the halves apart: the new node gets its own copy instead of a view of the old node's array.

Recorded with Go 1.27.1 on macOS 26 arm64. It runs in your browser with the Go compiler in WebAssembly 1.27.1. To run it yourself: go run main.go

Swift 6.4 · main.swift

// B+ tree insertion: at most 3 keys a node; the left half keeps an extra key.
let maxKeys = 3

final class Node {
  var keys: [Int]
  var children: [Node]  // empty in a leaf

  init(_ keys: [Int], _ children: [Node] = []) {
    self.keys = keys
    self.children = children
  }
}

func insert(_ key: Int, below node: Node) -> (separator: Int, right: Node)? {
  let i = node.keys.filter { $0 <= key }.count
  if node.children.isEmpty {
    node.keys.insert(key, at: i)
  } else if let split = insert(key, below: node.children[i]) {
    node.keys.insert(split.separator, at: i)
    node.children.insert(split.right, at: i + 1)
    print("  parent now \(node.keys)")
  }
  let count = node.keys.count
  guard count > maxKeys else { return nil }
  if node.children.isEmpty {
    // Leaf split: the right half's first key is copied up.
    let cut = (count + 1) / 2
    let right = Node(Array(node.keys[cut...]))
    node.keys.removeLast(count - cut)
    print("  leaf split \(node.keys) | \(right.keys), copy \(right.keys[0]) up")
    return (right.keys[0], right)
  }
  // Internal split: the middle key moves up, into neither half.
  let cut = count / 2
  let up = node.keys[cut]
  let right = Node(Array(node.keys[(cut + 1)...]), Array(node.children[(cut + 1)...]))
  node.keys.removeLast(count - cut)
  node.children.removeLast(count - cut)
  print("  internal split \(node.keys) | \(right.keys), push \(up) up")
  return (up, right)
}

var root = Node([])
for key in [20, 50, 10, 40, 30, 60, 70, 25, 35, 45, 55] {
  print("insert \(key)")
  if let split = insert(key, below: root) {
    root = Node([split.separator], [root, split.right])
    print("  new root \(root.keys)")
  }
}

In Swift: Node is a class, so the parent and the recursive call change the same node, and removeLast(count - cut) drops the half that moved.

Recorded with Apple Swift 6.4 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: swiftc -O main.swift -o main && ./main

Ruby 4.0 · main.rb

# frozen_string_literal: true

# B+ tree insertion: at most 3 keys a node; the left half keeps an extra key.
MAX_KEYS = 3

# A node: its sorted keys and its children, none in a leaf.
Node = Struct.new(:keys, :children)

def insert(node, key)
  place(node, key)
  return if node.keys.size <= MAX_KEYS

  node.children.empty? ? split_leaf(node) : split_internal(node)
end

# Puts key into node's subtree; a split below leaves its separator in node.
def place(node, key)
  i = node.keys.count { |k| k <= key }
  return node.keys.insert(i, key) if node.children.empty?

  separator, right = insert(node.children[i], key)
  return unless right

  node.keys.insert(i, separator)
  node.children.insert(i + 1, right)
  puts "  parent now #{node.keys}"
end

# Leaf split: the right half's first key is copied up.
def split_leaf(node)
  right = Node.new(node.keys.slice!(((node.keys.size + 1) / 2)..), [])
  puts "  leaf split #{node.keys} | #{right.keys}, copy #{right.keys[0]} up"
  [right.keys[0], right]
end

# Internal split: the middle key moves up, into neither half.
def split_internal(node)
  cut = node.keys.size / 2
  right = Node.new(node.keys.slice!((cut + 1)..), node.children.slice!((cut + 1)..))
  up = node.keys.pop
  puts "  internal split #{node.keys} | #{right.keys}, push #{up} up"
  [up, right]
end

root = Node.new([], [])
[20, 50, 10, 40, 30, 60, 70, 25, 35, 45, 55].each do |key|
  puts "insert #{key}"
  separator, right = insert(root, key)
  next unless right

  root = Node.new([separator], [root, right])
  puts "  new root #{root.keys}"
end

In Ruby: RuboCop keeps a method to ten lines, so placing the key and each kind of split are methods of their own; slice! removes and returns the half that moves.

Recorded with CRuby 4.0.7 on macOS 26 arm64. It runs in your browser with ruby.wasm 2.10.1 (Ruby 4.0.0). To run it yourself: ruby main.rb

Kotlin 2.4 · Main.kt

// B+ tree insertion: at most 3 keys a node; the left half keeps an extra key.
const val MAX_KEYS = 3

class Node(
    val keys: MutableList<Int>,
    val children: MutableList<Node> = mutableListOf(), // empty in a leaf
)

fun insert(
    node: Node,
    key: Int,
): Pair<Int, Node>? {
    val i = node.keys.count { it <= key }
    if (node.children.isEmpty()) {
        node.keys.add(i, key)
    } else {
        insert(node.children[i], key)?.let { (separator, right) ->
            node.keys.add(i, separator)
            node.children.add(i + 1, right)
            println("  parent now ${node.keys}")
        }
    }
    val count = node.keys.size
    if (count <= MAX_KEYS) return null
    if (node.children.isEmpty()) {
        // Leaf split: the right half's first key is copied up.
        val cut = (count + 1) / 2
        val right = Node(node.keys.subList(cut, count).toMutableList())
        node.keys.subList(cut, count).clear()
        println("  leaf split ${node.keys} | ${right.keys}, copy ${right.keys[0]} up")
        return right.keys[0] to right
    }
    // Internal split: the middle key moves up, into neither half.
    val cut = count / 2
    val up = node.keys[cut]
    val keys = node.keys.subList(cut + 1, count).toMutableList()
    val right = Node(keys, node.children.subList(cut + 1, count + 1).toMutableList())
    node.keys.subList(cut, count).clear()
    node.children.subList(cut + 1, count + 1).clear()
    println("  internal split ${node.keys} | ${right.keys}, push $up up")
    return up to right
}

fun main() {
    var root = Node(mutableListOf())
    for (key in listOf(20, 50, 10, 40, 30, 60, 70, 25, 35, 45, 55)) {
        println("insert $key")
        insert(root, key)?.let { (separator, right) ->
            root = Node(mutableListOf(separator), mutableListOf(root, right))
            println("  new root ${root.keys}")
        }
    }
}

In Kotlin: subList(cut, count).clear() removes the moved half in place, and ?.let runs only when the child split.

Recorded with Kotlin 2.4.20 on Java 25.0.4.1 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: kotlinc Main.kt -include-runtime -d main.jar && java -jar main.jar

Dart 3.13 · main.dart

// B+ tree insertion: at most 3 keys a node; the left half keeps an extra key.
const maxKeys = 3;

class Node {
  Node(this.keys, [List<Node>? children]) : children = children ?? [];

  final List<int> keys;
  final List<Node> children; // empty in a leaf
}

(int, Node)? insert(Node node, int key) {
  final i = node.keys.where((k) => k <= key).length;
  if (node.children.isEmpty) {
    node.keys.insert(i, key);
  } else if (insert(node.children[i], key) case (final up, final right)) {
    node.keys.insert(i, up);
    node.children.insert(i + 1, right);
    print('  parent now ${node.keys}');
  }
  final count = node.keys.length;
  if (count <= maxKeys) return null;
  if (node.children.isEmpty) {
    // Leaf split: the right half's first key is copied up.
    final cut = (count + 1) ~/ 2;
    final right = Node(node.keys.sublist(cut));
    node.keys.removeRange(cut, count);
    print(
      '  leaf split ${node.keys} | ${right.keys}, copy ${right.keys[0]} up',
    );
    return (right.keys[0], right);
  }
  // Internal split: the middle key moves up, into neither half.
  final cut = count ~/ 2;
  final up = node.keys[cut];
  final right = Node(
    node.keys.sublist(cut + 1),
    node.children.sublist(cut + 1),
  );
  node.keys.removeRange(cut, count);
  node.children.removeRange(cut + 1, count + 1);
  print('  internal split ${node.keys} | ${right.keys}, push $up up');
  return (up, right);
}

void main() {
  var root = Node([]);
  for (final key in [20, 50, 10, 40, 30, 60, 70, 25, 35, 45, 55]) {
    print('insert $key');
    if (insert(root, key) case (final separator, final right)) {
      root = Node([separator], [root, right]);
      print('  new root ${root.keys}');
    }
  }
}

In Dart: if (insert(...) case (final up, final right)) matches only when a split returned a record, and binds both of its parts.

Recorded with Dart 3.13.5 on macOS 26 arm64. It runs in your browser with a WebAssembly build by dart2wasm 3.13.5. To run it yourself: dart run main.dart

What every language printed

insert 20
insert 50
insert 10
insert 40
  leaf split [10, 20] | [40, 50], copy 40 up
  new root [40]
insert 30
insert 60
insert 70
  leaf split [40, 50] | [60, 70], copy 60 up
  parent now [40, 60]
insert 25
  leaf split [10, 20] | [25, 30], copy 25 up
  parent now [25, 40, 60]
insert 35
insert 45
insert 55
  leaf split [40, 45] | [50, 55], copy 50 up
  parent now [25, 40, 50, 60]
  internal split [25, 40] | [60], push 50 up
  new root [50]

The fourth key makes the first split, and 40 goes up into a new root. The inserts of 70 and 25 split leaves and fill the root, so 55 splits a leaf and then the root, around 50: 3 levels. The tree grew only at the top, which is why every leaf is always at the same depth. A real leaf split also links the new leaf into the chain of leaves, right after the old one; the program leaves the links out to keep to the splits.

Checkpoint

Check: Leaf splits and internal splits

Question 1 of 3 A full leaf receives one more key and splits in two. What happens to the first key of the new right leaf?
Choose one answer.

It moves into the parent and leaves the right leaf It moves into the left leaf It is copied into the parent and also stays in the right leaf It stays in the right leaf, and nothing goes up

Show the answer: Question 1 of 3

Answer: It is copied into the parent and also stays in the right leaf

A leaf split copies its separator up: the key stays in its leaf and a copy goes into the parent. An internal split pushes its middle key up, and that key leaves both halves.
Question 2 of 3 Leaves hold at most 4 keys, and a split that cannot share keys evenly leaves the extra one on the left. A leaf overflows with the keys 3, 8, 13, 21 and 34. Which key is copied up into the parent?
Type a number.
Your answer

A hint

Share the five keys between the two leaves first, with the extra one on the left.

Show the answer: Question 2 of 3

Answer: 21

The left leaf keeps 3 keys, 3, 8 and 13, and the right leaf gets 21 and 34. The separator is the right leaf's first key, 21. With the extra key on the right instead, the leaves would be 3 and 8, then 13, 21 and 34, and 13 would go up.
Question 3 of 3 After any number of inserts, why are all the leaves of a B+ tree still at the same depth?
Choose one answer.

The tree is rebalanced by rotations after each insert, as in an AVL tree New keys always go into the leftmost leaf A leaf that grows too deep is moved up a level A split adds a node beside the one that split, and only a split of the root adds a level, above every leaf at once

Show the answer: Question 3 of 3

Answer: A split adds a node beside the one that split, and only a split of the root adds a level, above every leaf at once

Splits work bottom-up and stop as soon as a node has room. When even the root overflows, a new root goes above it, which lengthens every root-to-leaf path by one at the same time.

Deletion: borrow first, merge when you must

Deletion mirrors insertion. It removes the key from its leaf, and only when the leaf drops below its minimum, an underflow: A node left with fewer keys than its minimum after a delete. A B+ tree repairs it by borrowing a key from a sibling or by merging with one., does it change anything else:

Borrowing moves one key from a sibling that has more than the minimum, and updates the separator between them.
Merging joins the leaf with a sibling that is already at the minimum, and removes their separator from the parent.
Shrinking happens when merges leave the root with a single child: that child becomes the root, and the tree loses a level.

Step through all three on a tree of two leaves:

Interactive · step by step Two deletes on a tree of two leaves Step through two deletes. The first leaf borrows a key; the second time it merges, and the tree loses its root.

The drawing shows the whole scene; its 6 steps are listed below.

Every step as text

A small tree. A parent with the separator 30 sits over two leaves, 10 and 20, then 30, 40 and 50. Every leaf must keep at least 2 keys.
Delete 10. Deleting 10 leaves 20 alone. One key is below the minimum of 2, so the leaf must be repaired.
Borrow from the right. The right sibling holds 3 keys, one more than it needs, so it lends its smallest key, 30. The separator becomes 40, the right leaf's new first key.
Delete 20. Deleting 20 leaves 30 alone, short again. This time the sibling holds 40 and 50, exactly the minimum, so it cannot lend.
Merge the leaves. The two leaves merge into one, 30, 40 and 50, and their separator leaves the parent, which now has no keys and a single child.
The root shrinks. A root with one child is replaced by that child. The merged leaf becomes the root, and the tree has one level fewer.

A merge takes a key out of the parent, so the parent may now be short of keys itself, and the same choice repeats one level up. Deletion therefore also follows one path down and at most one path back up. bulk loading: Building a B+ tree from keys already in sorted order: the leaves are filled from left to right and each level above is built from the one below, with no splits. builds a tree from keys that are already sorted, with no splits at all. It fills the leaves from left to right, each to a chosen fill factor: The share of each page that a bulk load or an index build fills, leaving the rest empty for later inserts., then builds each level from the one below.

Checkpoint

Check: Borrowing, merging and shrinking

Question 1 of 2 After a delete, a leaf holds too few keys. Its left sibling, under the same parent, holds more than the minimum. What happens?
Choose one answer.

The parent's separator moves down into the leaf The left sibling's largest key moves over, and the parent's separator becomes that key Nothing; a leaf may stay below half full until the next insert The two leaves always merge

Show the answer: Question 1 of 2

Answer: The left sibling's largest key moves over, and the parent's separator becomes that key

Borrowing keeps both leaves at least half full without changing the number of children. Only the separator between the two leaves changes, to the moved key.
Question 2 of 2 A leaf holds 1 key after a delete, its only sibling holds exactly 2, and leaves need at least 2. What happens?
Choose one answer.

The leaf is deleted and its key is dropped The two leaves merge into one leaf of 3 keys, and their separator leaves the parent The tree adds a level The sibling lends one key anyway

Show the answer: Question 2 of 2

Answer: The two leaves merge into one leaf of 3 keys, and their separator leaves the parent

Borrowing needs a sibling above the minimum; when none has a key to spare, the leaves merge. The parent loses the separator between them and may in turn have to borrow or merge.

Practise: split an overfull leaf and an overfull node

The exercise writes this lesson’s two splits as functions, with the same convention: the left node keeps any extra key.

Exercise · Medium · Python

Split an overfull leaf and an overfull internal node

Write the two splits of B+ tree insertion in splits.py. In both, when the keys cannot be shared evenly, the left node keeps the extra one, as in the lesson.

split_leaf(keys) gets the sorted keys of a leaf that has just overflowed. Return (left, right, separator): the keys of the two leaves, and the key that goes up into the parent. A leaf split copies its separator up, so the separator stays in a leaf too.
split_internal(keys, children) gets the sorted keys of an internal node that has just overflowed and its children, one more than the keys. Return (left_keys, left_children, separator, right_keys, right_children). An internal split pushes its middle key up, so the separator ends up in neither half.

For example, split_leaf([10, 20, 25, 30]) returns ([10, 20], [25, 30], 25).

Starter code · splits.py

def split_leaf(keys):
    """Split an overfull leaf: (left keys, right keys, separator copied up)."""
    return [], [], None


def split_internal(keys, children):
    """Split an overfull internal node: (left keys, left children, separator pushed up, right keys, right children)."""
    return [], [], None, [], []

The sample tests · test_splits.py

from splits import split_internal, split_leaf


def test_leaf_split_even():
    """Four keys: two in each leaf, and the right leaf's first key is copied up"""
    assert split_leaf([10, 20, 25, 30]) == ([10, 20], [25, 30], 25)


def test_leaf_split_odd():
    """Five keys: the left leaf keeps the extra one"""
    assert split_leaf([3, 8, 13, 21, 34]) == ([3, 8, 13], [21, 34], 21)


def test_internal_split_pushes_the_middle_key():
    """Four keys and five children: the left node keeps two keys, the third goes up"""
    assert split_internal([25, 40, 50, 60], ["a", "b", "c", "d", "e"]) == ([25, 40], ["a", "b", "c"], 50, [60], ["d", "e"])


def test_internal_split_three_keys():
    """Three keys and four children: the middle key goes up and one key stays on each side"""
    assert split_internal([5, 9, 14], ["p", "q", "r", "s"]) == ([5], ["p", "q"], 9, [14], ["r", "s"])

A hint

For the leaf, the left part keeps (len(keys) + 1) // 2 keys and the separator is the first key of the right part. For an internal node with n keys, one key goes up, so the two halves share the other n - 1: the left half keeps n // 2 of them, and each half keeps one more child than it has keys.

The sample tests run on this device, in your browser (Pyodide): nothing is sent to mysmartcopilot.com. The first run downloads Python (about 13.5 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.

The questions below cover the rules, the splits and deletion, and start with the idea you know least.

Deletion case by case, with every rebalancing traced Pro: opens with a Pro, Premium or Ultimate pass

Deletion has more cases than insertion, because a node that runs short can be repaired in two ways and the repair can travel up the tree. This part traces each case on the tree built above and reproduces the mistake that most often breaks searches afterwards.

In this part:

Borrowing from a sibling, at the leaves and above
Merging, and how a merge travels up to the root
Four deletions traced, every case once
What a deletion costs, in pages
A failure reproduced: the separator that was not updated

1 diagram · 3 runnable examples (Python) · about 9 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

Pro pass · 1 week₹79$2.99
30 days₹179$5.99
1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a pass I have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Split conventions, bulk loading and a randomised check Pro: opens with a Pro, Premium or Ultimate pass

Two trees built from the same keys can differ, because the split rule is a convention, and the cheapest way to build a tree is not to insert into it at all. This part measures both, and then checks the simulator against 80,000 random operations.

In this part:

Left-biased and right-biased splits, side by side
Bulk loading from sorted data, with fill factors measured
80,000 random operations against the invariants

3 runnable examples (Python) · about 6 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

Pro pass · 1 week₹79$2.99
30 days₹179$5.99
1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a pass I have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Interview questions

An interviewer often checks the mechanics before the design questions. Answer each check below, and read why every choice is right or wrong:

Checkpoint

Interview round: three quick checks

Question 1 of 3 Interview check: a B+ tree has 3 levels, and every node on the path to one leaf is full. How many nodes can a single insert split, before a new root is added?
Type a number.
Your answer splits

Show the answer: Question 1 of 3

Answer: 3 splits

The leaf splits, its separator overflows the internal node above, which splits, and that separator overflows the root, which splits too: 3 splits, one per level, and then a new root makes the tree 4 levels deep.
Question 2 of 3 Interview check: why does a leaf split copy its separator while an internal split moves its middle key?
Choose one answer.

Copying is faster than moving, so leaves copy Internal nodes have no room for a copy Leaf keys belong to records, which must stay in the leaves; internal keys are only guides, so one can move up Both copy; the internal key is deleted later

Show the answer: Question 2 of 3

Answer: Leaf keys belong to records, which must stay in the leaves; internal keys are only guides, so one can move up

A B+ tree keeps every record in a leaf, so a leaf split must keep its key and send a copy up. Internal keys are separators, so the middle one can move up and separate the two halves from the level above.
Question 3 of 3 Interview check: when does a B+ tree get shorter?
Choose one answer.

Never; a B+ tree only grows After every merge Only when merges leave the root with a single child, which then becomes the root Whenever a leaf becomes empty

Show the answer: Question 3 of 3

Answer: Only when merges leave the root with a single child, which then becomes the root

A merge removes a separator from the parent. When the parent is the root and that was its last key, the root has one child left, the child becomes the root, and every leaf moves one level up at once.

Fresher

Insert 8, 3, 11, 5, 9, 14, 1, 6, 12 and 13 into an empty B+ tree whose nodes hold at most 3 keys, the left node keeping the extra key when a split is uneven. Draw the tree after each split and say which keys were copied up and which were pushed up.

Model answer, Pro. Model answers open with any pass; prices are in the notice on this page. First step and follow-ups
Fresher to mid

A delete leaves a B+ tree leaf with too few keys. Walk through how you decide between borrowing and merging, what happens to the parent in each case, and when the tree loses a level.

Model answer, Pro. First step and follow-ups
Mid to senior

You must build an index on 50 million rows of an existing table. Compare inserting the keys one at a time with sorting them and bulk-loading the tree, in pages, fill and time. When would you leave empty space in the pages?

Model answer, Pro. First step and follow-ups

Key takeaways

Insertion and deletion both start at a leaf and repair the tree bottom-up, so all leaves stay at the same depth.
A leaf split copies its separator up and keeps the key in the leaf; an internal split pushes its middle key up.
A split of the root adds a level; a merge that leaves the root with one child removes one.
Deletion borrows from a sibling with a key to spare and merges only when both siblings are at the minimum.
Which side keeps the extra key in a split is a convention: state it whenever you draw a tree.

Terms in this lesson

bulk loading: Building a B+ tree from keys already in sorted order: the leaves are filled from left to right and each level above is built from the one below, with no splits.
fill factor: The share of each page that a bulk load or an index build fills, leaving the rest empty for later inserts.
underflow: A node left with fewer keys than its minimum after a delete. A B+ tree repairs it by borrowing a key from a sibling or by merging with one.

References

R. Bayer and E. McCreight: Organization and Maintenance of Large Ordered Indexes (Acta Informatica)
D. Comer: The Ubiquitous B-Tree (ACM Computing Surveys)
PostgreSQL 18 Documentation: CREATE INDEX (fillfactor) (The PostgreSQL Global Development Group)
PostgreSQL 18 Documentation: B-Tree Indexes, Implementation (The PostgreSQL Global Development Group)
MySQL 8.4 Reference Manual: The Physical Structure of an InnoDB Index (Oracle Corporation)
MySQL 8.4 Reference Manual: Sorted Index Builds (Oracle Corporation)

Report a problem with this lesson

In this module: Indexing

Index basics: dense, sparse, primary, secondary Free lesson, Pro answers: 30 minutes
B-trees and B+ trees: structure and order Free core, Pro depth: 8 of 20 minutes free
B+ tree insertion and deletion: step by step Free core, Pro depth: 7 of 20 minutes free
B-tree indexes in practice: composite to covering Free core, Pro depth: 8 of 20 minutes free
Hashing: static, extendible and linear Free core, Pro depth: 7 of 20 minutes free

Your country

B+ tree insertion and deletion: step by step

What you will learn

Before you start

What you will learn

Before you start

Three rules hold after every change

Insertion splits full nodes and grows the tree at the root

Deletion: borrow first, merge when you must

Practise: split an overfull leaf and an overfull node

Split an overfull leaf and an overfull internal node

Results of the sample tests

Deletion case by case, with every rebalancing traced Pro: opens with a Pro, Premium or Ultimate pass

Split conventions, bulk loading and a randomised check Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Insert 8, 3, 11, 5, 9, 14, 1, 6, 12 and 13 into an empty B+ tree whose nodes hold at most 3 keys, the left node keeping the extra key when a split is uneven. Draw the tree after each split and say which keys were copied up and which were pushed up.

A delete leaves a B+ tree leaf with too few keys. Walk through how you decide between borrowing and merging, what happens to the parent in each case, and when the tree loses a level.

You must build an index on 50 million rows of an existing table. Compare inserting the keys one at a time with sorting them and bulk-loading the tree, in pages, fill and time. When would you leave empty space in the pages?

Key takeaways

References