Back to Technology

B-Trees & B+ Trees: Multiway Search Trees for Disk

September 9, 2026 Wasil Zafar 28 min read

Binary search trees are height-optimal in RAM, but every real database index and filesystem uses a B-Tree instead. This lesson builds the multiway search tree that turns disk seeks into the scarce resource worth minimizing, then implements search, insert with splitting, and delete with borrowing and merging.

Table of Contents

  1. Introduction & Motivation
  2. Prerequisites
  3. A Concrete Example
  4. Core Insight
  5. B-Tree Search
  6. B-Tree Insert & Splitting
  7. B-Tree Delete
  8. B+ Tree: What’s Different
  9. B+ Tree Search & Range Scan
  10. Complexity Analysis
  11. Applications & Alternatives
  12. Exercises
  13. Summary

1. Introduction & Motivation

A balanced binary search tree such as an AVL or Red-Black tree keeps its height at $O(\log_2 n)$, and a lookup or insert touches roughly that many nodes. On a machine where every node lives in RAM next to every other node, that is an excellent bound. But indexes for databases and filesystems do not live purely in RAM — they live on disk, or are backed by disk and only partially cached, and each node visited during a search is a candidate disk seek or page fetch. A tree with height 30 can mean up to 30 seeks per lookup, and a single disk seek is roughly five to six orders of magnitude slower than a comparison already sitting in a CPU register.

The B-Tree fixes this by trading depth for breadth. Instead of two children per node, a B-Tree node holds many sorted keys and fans out into many children at once — its branching factor, called the order $m$ (or parameterized by a minimum degree $t$, where $m = 2t$), is chosen so that one node fills exactly one disk page, often hundreds of keys wide. With branching factor $m$, the height of a B-Tree over $n$ keys is $O(\log_m n)$ instead of $O(\log_2 n)$. For $n = 10^9$ and $m = 200$, a binary tree needs roughly 30 levels; a B-Tree needs about 4. Four disk seeks instead of thirty is the entire reason every production relational database index, and most filesystem directory structures, are built on B-Trees or their close cousin the B+ Tree, and not on binary search trees.

A B-Tree is best understood as the disk-aware, multiway generalization of the balanced binary search tree you already know: same ordering discipline, same $\log n$ height guarantee, but rebalanced by splitting and merging whole nodes instead of by single rotations, and tuned so that “one node” means “one page transfer” rather than “one pointer chase.”

2. Prerequisites

This lesson assumes you are comfortable with general binary search trees and the idea of keeping one height-balanced through rotations or recoloring, covered in Part 10: BST, AVL & Red-Black Trees. A B-Tree keeps the same ordering discipline a BST does — find a value by comparing it against keys stored in a node and descending into the child whose range must contain it — but it generalizes the balance invariant from “at most two children, rebalanced by rotation” to “between $t$ and $2t$ children, rebalanced by splitting and merging nodes.” If self-balancing search trees are still unfamiliar, read that lesson first; everything below assumes its vocabulary of keys, ordering invariants, height, and $\log n$ operations.

Additional vocabulary specific to this lesson:

  • Minimum degree $t$: every node except the root must hold at least $t-1$ keys and at most $2t-1$ keys; an internal node with $k$ keys has exactly $k+1$ children.
  • Order $m$: an equivalent parameterization, $m = 2t$, describing the maximum number of children a node may have.
  • Full node: a node already holding the maximum $2t-1$ keys; it must be split before another key can be inserted into it.
  • Leaf depth uniformity: every leaf in a B-Tree sits at exactly the same depth, unlike a general BST where leaves can be at different depths.

3. A Concrete Example

Worked Example

Inserting into a B-Tree of minimum degree t = 2

With $t=2$, every node may hold at most $2t-1=3$ keys and at least $t-1=1$ key (except the root). Insert the keys 10, 20, 5, 6, 12, 30, 7, 17 one at a time, always splitting a full node on the way down rather than after the insert fails.

InsertWhat happensRoot after
10, 20Both fit in the empty root leaf.[10, 20]
5Still fits; the root leaf now holds the maximum of 3 keys.[5, 10, 20]
6The root is full (3 keys), so before descending it is split: the median key 10 moves up into a brand-new root, leaving two children [5] and [20]. Then 6 is inserted into the left child.[10] over [5, 6] and [20]
12, 30, 7Each descends into a non-full leaf and is inserted directly.[10] over [5, 6, 7], [12, 20, 30]
17The target leaf [12, 20, 30] is full, so it is split first: median 20 moves up beside 10 in the root, leaving children [12] and [30]. Then 17 is inserted into [12].[10, 20] over [5, 6, 7], [12, 17], [30]

The final tree has a root [10, 20] with three leaf children [5, 6, 7], [12, 17], and [30]. Every leaf sits at depth 1, and two splits happened along the way — one that grew the tree’s height by creating a new root, and one that stayed at the existing height. Section 6 below reproduces this exact trace in runnable code.

4. Core Insight

Core insight: Every B-Tree node except the root holds between $t-1$ and $2t-1$ keys; an internal node with $k$ keys has $k+1$ children, and those children partition the key space into the $k+1$ ranges the keys separate; all keys inside a node are sorted; and every leaf sits at the same depth. Splitting a full node during the downward pass — instead of inserting first and fixing an overflow afterward — guarantees that by the time a key reaches the node it will be inserted into, that node already has room. That single discipline keeps every root-to-leaf path the same length in one pass, with no separate rebalancing phase.

Contrast this with a naive approach: insert the key first, then check whether the node overflowed and, if so, split it and propagate the split upward. That works, but it requires either a second upward pass or storing a full recursive call stack of “parent” nodes to revisit. Splitting proactively — check whether the child about to be descended into is full, and if so split it before descending — means a single top-down pass suffices, and the recursive insert code never needs to look back upward.

Search starts at the root and, in each node, scans the sorted keys to find the first key not smaller than the target. If that key matches, the search is done. Otherwise the search descends into the child that must contain the target’s range. A node with $k$ keys costs $O(k)$ per level (or $O(\log k)$ with binary search inside the node), and the tree has $O(\log_m n)$ levels.

class BTreeNode:
    def __init__(self, leaf=True):
        self.leaf = leaf
        self.keys = []
        self.children = []


def search(node, k):
    i = 0
    while i < len(node.keys) and k > node.keys[i]:
        i += 1
    if i < len(node.keys) and k == node.keys[i]:
        return (node, i)
    if node.leaf:
        return None
    return search(node.children[i], k)


# Build the tiny tree by hand: root [30] -> left [10, 20], right [40, 50]
left = BTreeNode(leaf=True)
left.keys = [10, 20]
right = BTreeNode(leaf=True)
right.keys = [40, 50]
root = BTreeNode(leaf=False)
root.keys = [30]
root.children = [left, right]

print("Found 40:", search(root, 40) is not None)  # Found 40: True
print("Found 25:", search(root, 25) is not None)  # Found 25: False

#include <iostream>
#include <vector>

struct BTreeNode {
    bool leaf;
    std::vector<int> keys;
    std::vector<BTreeNode*> children;
    explicit BTreeNode(bool isLeaf) : leaf(isLeaf) {}
};

BTreeNode* search(BTreeNode* node, int k) {
    std::size_t i = 0;
    while (i < node->keys.size() && k > node->keys[i]) {
        ++i;
    }
    if (i < node->keys.size() && k == node->keys[i]) {
        return node;
    }
    if (node->leaf) {
        return nullptr;
    }
    return search(node->children[i], k);
}

int main() {
    // Build the same tiny tree by hand: root [30] -> left [10, 20], right [40, 50]
    auto* left = new BTreeNode(true);
    left->keys = {10, 20};
    auto* right = new BTreeNode(true);
    right->keys = {40, 50};
    auto* root = new BTreeNode(false);
    root->keys = {30};
    root->children = {left, right};

    std::cout << "Found 40: " << (search(root, 40) != nullptr ? "true" : "false") << '\n';
    std::cout << "Found 25: " << (search(root, 25) != nullptr ? "true" : "false") << '\n';
}

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

class BTreeNode {
    boolean leaf;
    List<Integer> keys = new ArrayList<>();
    List<BTreeNode> children = new ArrayList<>();
    BTreeNode(boolean leaf) { this.leaf = leaf; }
}

public class BTreeSearch {
    static BTreeNode search(BTreeNode node, int k) {
        int i = 0;
        while (i < node.keys.size() && k > node.keys.get(i)) {
            i++;
        }
        if (i < node.keys.size() && k == node.keys.get(i)) {
            return node;
        }
        if (node.leaf) {
            return null;
        }
        return search(node.children.get(i), k);
    }

    public static void main(String[] args) {
        BTreeNode left = new BTreeNode(true);
        left.keys.add(10); left.keys.add(20);
        BTreeNode right = new BTreeNode(true);
        right.keys.add(40); right.keys.add(50);
        BTreeNode root = new BTreeNode(false);
        root.keys.add(30);
        root.children.add(left); root.children.add(right);

        System.out.println("Found 40: " + (search(root, 40) != null));
        System.out.println("Found 25: " + (search(root, 25) != null));
    }
}

6. B-Tree Insert (With Node Splitting)

Insert descends from the root exactly like search, but first checks whether the root itself is full, and while descending checks whether the child about to be entered is full — splitting it first if so. This reproduces the worked trace from Section 3.

class BTreeNode:
    def __init__(self, leaf=True):
        self.leaf = leaf
        self.keys = []
        self.children = []


class BTree:
    def __init__(self, t):
        if t < 2:
            raise ValueError("minimum degree t must be >= 2")
        self.t = t
        self.root = BTreeNode(leaf=True)

    def insert(self, k):
        root = self.root
        if len(root.keys) == 2 * self.t - 1:
            new_root = BTreeNode(leaf=False)
            new_root.children.append(root)
            self._split_child(new_root, 0)
            self.root = new_root
            self._insert_non_full(new_root, k)
        else:
            self._insert_non_full(root, k)

    def _split_child(self, parent, i):
        t = self.t
        full_child = parent.children[i]
        new_child = BTreeNode(leaf=full_child.leaf)

        mid_key = full_child.keys[t - 1]
        new_child.keys = full_child.keys[t:]
        full_child.keys = full_child.keys[:t - 1]

        if not full_child.leaf:
            new_child.children = full_child.children[t:]
            full_child.children = full_child.children[:t]

        parent.keys.insert(i, mid_key)
        parent.children.insert(i + 1, new_child)

    def _insert_non_full(self, node, k):
        i = len(node.keys) - 1
        if node.leaf:
            node.keys.append(None)
            while i >= 0 and k < node.keys[i]:
                node.keys[i + 1] = node.keys[i]
                i -= 1
            node.keys[i + 1] = k
        else:
            while i >= 0 and k < node.keys[i]:
                i -= 1
            i += 1
            if len(node.children[i].keys) == 2 * self.t - 1:
                self._split_child(node, i)
                if k > node.keys[i]:
                    i += 1
            self._insert_non_full(node.children[i], k)


def level_order(tree):
    levels = []
    frontier = [tree.root]
    while frontier:
        levels.append([list(node.keys) for node in frontier])
        frontier = [child for node in frontier for child in node.children]
    return levels


tree = BTree(t=2)
for key in [10, 20, 5, 6, 12, 30, 7, 17]:
    tree.insert(key)

for depth, level in enumerate(level_order(tree)):
    print(f"Level {depth}: {level}")
# Level 0: [[10, 20]]
# Level 1: [[5, 6, 7], [12, 17], [30]]

#include <iostream>
#include <vector>

struct BTreeNode {
    bool leaf;
    std::vector<int> keys;
    std::vector<BTreeNode*> children;
    explicit BTreeNode(bool isLeaf) : leaf(isLeaf) {}
};

class BTree {
public:
    explicit BTree(int t) : t(t) {
        root = new BTreeNode(true);
    }

    void insert(int k) {
        if ((int)root->keys.size() == 2 * t - 1) {
            BTreeNode* newRoot = new BTreeNode(false);
            newRoot->children.push_back(root);
            splitChild(newRoot, 0);
            root = newRoot;
        }
        insertNonFull(root, k);
    }

    BTreeNode* getRoot() const { return root; }

private:
    int t;
    BTreeNode* root;

    void splitChild(BTreeNode* parent, int i) {
        BTreeNode* fullChild = parent->children[i];
        BTreeNode* newChild = new BTreeNode(fullChild->leaf);

        int midKey = fullChild->keys[t - 1];
        newChild->keys.assign(fullChild->keys.begin() + t, fullChild->keys.end());
        fullChild->keys.resize(t - 1);

        if (!fullChild->leaf) {
            newChild->children.assign(fullChild->children.begin() + t, fullChild->children.end());
            fullChild->children.resize(t);
        }

        parent->keys.insert(parent->keys.begin() + i, midKey);
        parent->children.insert(parent->children.begin() + i + 1, newChild);
    }

    void insertNonFull(BTreeNode* node, int k) {
        int i = (int)node->keys.size() - 1;
        if (node->leaf) {
            node->keys.push_back(0);
            while (i >= 0 && k < node->keys[i]) {
                node->keys[i + 1] = node->keys[i];
                --i;
            }
            node->keys[i + 1] = k;
        } else {
            while (i >= 0 && k < node->keys[i]) {
                --i;
            }
            ++i;
            if ((int)node->children[i]->keys.size() == 2 * t - 1) {
                splitChild(node, i);
                if (k > node->keys[i]) {
                    ++i;
                }
            }
            insertNonFull(node->children[i], k);
        }
    }
};

void printLevels(BTreeNode* root) {
    std::vector<BTreeNode*> frontier{root};
    int depth = 0;
    while (!frontier.empty()) {
        std::cout << "Level " << depth << ": ";
        std::vector<BTreeNode*> next;
        for (BTreeNode* node : frontier) {
            std::cout << "[";
            for (std::size_t j = 0; j < node->keys.size(); ++j) {
                std::cout << node->keys[j] << (j + 1 < node->keys.size() ? " " : "");
            }
            std::cout << "] ";
            for (BTreeNode* child : node->children) next.push_back(child);
        }
        std::cout << '\n';
        frontier = next;
        ++depth;
    }
}

int main() {
    BTree tree(2);
    for (int key : {10, 20, 5, 6, 12, 30, 7, 17}) {
        tree.insert(key);
    }
    printLevels(tree.getRoot());
    // Level 0: [10 20]
    // Level 1: [5 6 7] [12 17] [30]
}

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

class BTreeNode {
    boolean leaf;
    List<Integer> keys = new ArrayList<>();
    List<BTreeNode> children = new ArrayList<>();
    BTreeNode(boolean leaf) { this.leaf = leaf; }
}

class BTree {
    private final int t;
    private BTreeNode root;

    BTree(int t) {
        this.t = t;
        root = new BTreeNode(true);
    }

    BTreeNode getRoot() { return root; }

    void insert(int k) {
        if (root.keys.size() == 2 * t - 1) {
            BTreeNode newRoot = new BTreeNode(false);
            newRoot.children.add(root);
            splitChild(newRoot, 0);
            root = newRoot;
        }
        insertNonFull(root, k);
    }

    private void splitChild(BTreeNode parent, int i) {
        BTreeNode fullChild = parent.children.get(i);
        BTreeNode newChild = new BTreeNode(fullChild.leaf);

        int midKey = fullChild.keys.get(t - 1);
        newChild.keys.addAll(fullChild.keys.subList(t, fullChild.keys.size()));
        fullChild.keys.subList(t - 1, fullChild.keys.size()).clear();

        if (!fullChild.leaf) {
            newChild.children.addAll(fullChild.children.subList(t, fullChild.children.size()));
            fullChild.children.subList(t, fullChild.children.size()).clear();
        }

        parent.keys.add(i, midKey);
        parent.children.add(i + 1, newChild);
    }

    private void insertNonFull(BTreeNode node, int k) {
        int i = node.keys.size() - 1;
        if (node.leaf) {
            node.keys.add(0);
            while (i >= 0 && k < node.keys.get(i)) {
                node.keys.set(i + 1, node.keys.get(i));
                i--;
            }
            node.keys.set(i + 1, k);
        } else {
            while (i >= 0 && k < node.keys.get(i)) {
                i--;
            }
            i++;
            if (node.children.get(i).keys.size() == 2 * t - 1) {
                splitChild(node, i);
                if (k > node.keys.get(i)) {
                    i++;
                }
            }
            insertNonFull(node.children.get(i), k);
        }
    }
}

public class BTreeInsertDemo {
    static void printLevels(BTreeNode root) {
        List<BTreeNode> frontier = new ArrayList<>();
        frontier.add(root);
        int depth = 0;
        while (!frontier.isEmpty()) {
            StringBuilder sb = new StringBuilder("Level " + depth + ": ");
            List<BTreeNode> next = new ArrayList<>();
            for (BTreeNode node : frontier) {
                sb.append(node.keys).append(" ");
                next.addAll(node.children);
            }
            System.out.println(sb.toString());
            frontier = next;
            depth++;
        }
    }

    public static void main(String[] args) {
        BTree tree = new BTree(2);
        for (int key : new int[]{10, 20, 5, 6, 12, 30, 7, 17}) {
            tree.insert(key);
        }
        printLevels(tree.getRoot());
        // Level 0: [10, 20]
        // Level 1: [5, 6, 7] [12, 17] [30]
    }
}

7. B-Tree Delete

Delete is the trickiest B-Tree operation because removing a key must never leave a non-root node with fewer than $t-1$ keys. Before descending into a child, the algorithm guarantees that child has at least $t$ keys, by borrowing one key from a sibling that can spare it, or by merging with a sibling when neither can. Three cases in total:

  • Key is in a leaf: remove it directly — the leaf was already guaranteed to have at least $t$ keys before descending, so it stays legal.
  • Key is in an internal node: replace it with its predecessor (largest key in the left subtree) or successor (smallest key in the right subtree) if that child has at least $t$ keys, then recursively delete the replacement from that child; otherwise merge the two children around the key and recurse into the merged node.
  • Key is not in this node: before descending into the child that must contain it, if that child has only $t-1$ keys, either borrow a key from an adjacent sibling (rotating a key through the parent) or merge it with a sibling (pulling a key down from the parent).
class BTreeNode:
    def __init__(self, leaf=True):
        self.leaf = leaf
        self.keys = []
        self.children = []


class BTree:
    def __init__(self, t):
        self.t = t
        self.root = BTreeNode(leaf=True)

    # --- insertion (unchanged from Section 6) ---
    def insert(self, k):
        root = self.root
        if len(root.keys) == 2 * self.t - 1:
            new_root = BTreeNode(leaf=False)
            new_root.children.append(root)
            self._split_child(new_root, 0)
            self.root = new_root
            self._insert_non_full(new_root, k)
        else:
            self._insert_non_full(root, k)

    def _split_child(self, parent, i):
        t = self.t
        full_child = parent.children[i]
        new_child = BTreeNode(leaf=full_child.leaf)
        mid_key = full_child.keys[t - 1]
        new_child.keys = full_child.keys[t:]
        full_child.keys = full_child.keys[:t - 1]
        if not full_child.leaf:
            new_child.children = full_child.children[t:]
            full_child.children = full_child.children[:t]
        parent.keys.insert(i, mid_key)
        parent.children.insert(i + 1, new_child)

    def _insert_non_full(self, node, k):
        i = len(node.keys) - 1
        if node.leaf:
            node.keys.append(None)
            while i >= 0 and k < node.keys[i]:
                node.keys[i + 1] = node.keys[i]
                i -= 1
            node.keys[i + 1] = k
        else:
            while i >= 0 and k < node.keys[i]:
                i -= 1
            i += 1
            if len(node.children[i].keys) == 2 * self.t - 1:
                self._split_child(node, i)
                if k > node.keys[i]:
                    i += 1
            self._insert_non_full(node.children[i], k)

    # --- deletion ---
    def delete(self, k):
        self._delete(self.root, k)
        if len(self.root.keys) == 0 and not self.root.leaf:
            self.root = self.root.children[0]

    def _find_key(self, node, k):
        idx = 0
        while idx < len(node.keys) and node.keys[idx] < k:
            idx += 1
        return idx

    def _delete(self, node, k):
        t = self.t
        idx = self._find_key(node, k)

        if idx < len(node.keys) and node.keys[idx] == k:
            if node.leaf:
                node.keys.pop(idx)
            else:
                self._remove_from_internal(node, idx)
        else:
            if node.leaf:
                return  # key not present, nothing to do

            is_last = (idx == len(node.keys))
            if len(node.children[idx].keys) < t:
                self._fill(node, idx)
            # if the deficient child got merged into its left sibling,
            # the child we must recurse into shifted one slot to the left
            if is_last and idx > len(node.keys):
                self._delete(node.children[idx - 1], k)
            else:
                self._delete(node.children[idx], k)

    def _remove_from_internal(self, node, idx):
        k = node.keys[idx]
        t = self.t
        left, right = node.children[idx], node.children[idx + 1]

        if len(left.keys) >= t:
            pred = self._get_predecessor(left)
            node.keys[idx] = pred
            self._delete(left, pred)
        elif len(right.keys) >= t:
            succ = self._get_successor(right)
            node.keys[idx] = succ
            self._delete(right, succ)
        else:
            self._merge(node, idx)
            self._delete(node.children[idx], k)

    def _get_predecessor(self, node):
        while not node.leaf:
            node = node.children[-1]
        return node.keys[-1]

    def _get_successor(self, node):
        while not node.leaf:
            node = node.children[0]
        return node.keys[0]

    def _fill(self, node, idx):
        t = self.t
        if idx != 0 and len(node.children[idx - 1].keys) >= t:
            self._borrow_from_prev(node, idx)
        elif idx != len(node.keys) and len(node.children[idx + 1].keys) >= t:
            self._borrow_from_next(node, idx)
        else:
            if idx != len(node.keys):
                self._merge(node, idx)
            else:
                self._merge(node, idx - 1)

    def _borrow_from_prev(self, node, idx):
        child, sibling = node.children[idx], node.children[idx - 1]
        child.keys.insert(0, node.keys[idx - 1])
        node.keys[idx - 1] = sibling.keys.pop()
        if not child.leaf:
            child.children.insert(0, sibling.children.pop())

    def _borrow_from_next(self, node, idx):
        child, sibling = node.children[idx], node.children[idx + 1]
        child.keys.append(node.keys[idx])
        node.keys[idx] = sibling.keys.pop(0)
        if not child.leaf:
            child.children.append(sibling.children.pop(0))

    def _merge(self, node, idx):
        left, right = node.children[idx], node.children[idx + 1]
        left.keys.append(node.keys.pop(idx))
        left.keys.extend(right.keys)
        if not left.leaf:
            left.children.extend(right.children)
        node.children.pop(idx + 1)


def level_order(tree):
    levels = []
    frontier = [tree.root]
    while frontier:
        levels.append([list(node.keys) for node in frontier])
        frontier = [child for node in frontier for child in node.children]
    return levels


tree = BTree(t=2)
for key in [10, 20, 5, 6, 12, 30, 7, 17]:
    tree.insert(key)
print("After inserts:", level_order(tree))
# After inserts: [[[10, 20]], [[5, 6, 7], [12, 17], [30]]]

for key in [5, 6, 7, 10]:
    tree.delete(key)
    print(f"After deleting {key}:", level_order(tree))
# After deleting 5:  [[[10, 20]], [[6, 7], [12, 17], [30]]]
# After deleting 6:  [[[10, 20]], [[7], [12, 17], [30]]]
# After deleting 7:  [[[12, 20]], [[10], [17], [30]]]      -- borrow-from-next: 12 rotates up, 10 rotates down
# After deleting 10: [[[20]], [[12, 17], [30]]]            -- merge: deficient [10] merges with sibling [17]

#include <iostream>
#include <vector>

struct BTreeNode {
    bool leaf;
    std::vector<int> keys;
    std::vector<BTreeNode*> children;
    explicit BTreeNode(bool leaf) : leaf(leaf) {}
};

class BTree {
public:
    explicit BTree(int t) : t(t) {
        root = new BTreeNode(true);
    }

    void insert(int k) {
        if ((int)root->keys.size() == 2 * t - 1) {
            BTreeNode* newRoot = new BTreeNode(false);
            newRoot->children.push_back(root);
            splitChild(newRoot, 0);
            root = newRoot;
        }
        insertNonFull(root, k);
    }

    void remove(int k) {
        deleteKey(root, k);
        if (root->keys.empty() && !root->leaf) {
            root = root->children[0];
        }
    }

    BTreeNode* getRoot() const { return root; }

private:
    int t;
    BTreeNode* root;

    void splitChild(BTreeNode* parent, int i) {
        BTreeNode* fullChild = parent->children[i];
        BTreeNode* newChild = new BTreeNode(fullChild->leaf);
        int midKey = fullChild->keys[t - 1];
        newChild->keys.assign(fullChild->keys.begin() + t, fullChild->keys.end());
        fullChild->keys.resize(t - 1);
        if (!fullChild->leaf) {
            newChild->children.assign(fullChild->children.begin() + t, fullChild->children.end());
            fullChild->children.resize(t);
        }
        parent->keys.insert(parent->keys.begin() + i, midKey);
        parent->children.insert(parent->children.begin() + i + 1, newChild);
    }

    void insertNonFull(BTreeNode* node, int k) {
        int i = (int)node->keys.size() - 1;
        if (node->leaf) {
            node->keys.push_back(0);
            while (i >= 0 && k < node->keys[i]) {
                node->keys[i + 1] = node->keys[i];
                --i;
            }
            node->keys[i + 1] = k;
        } else {
            while (i >= 0 && k < node->keys[i]) --i;
            ++i;
            if ((int)node->children[i]->keys.size() == 2 * t - 1) {
                splitChild(node, i);
                if (k > node->keys[i]) ++i;
            }
            insertNonFull(node->children[i], k);
        }
    }

    int findKey(BTreeNode* node, int k) {
        int idx = 0;
        while (idx < (int)node->keys.size() && node->keys[idx] < k) ++idx;
        return idx;
    }

    int getPredecessor(BTreeNode* node) {
        while (!node->leaf) node = node->children.back();
        return node->keys.back();
    }

    int getSuccessor(BTreeNode* node) {
        while (!node->leaf) node = node->children.front();
        return node->keys.front();
    }

    void borrowFromPrev(BTreeNode* node, int idx) {
        BTreeNode* child = node->children[idx];
        BTreeNode* sibling = node->children[idx - 1];
        child->keys.insert(child->keys.begin(), node->keys[idx - 1]);
        node->keys[idx - 1] = sibling->keys.back();
        sibling->keys.pop_back();
        if (!child->leaf) {
            child->children.insert(child->children.begin(), sibling->children.back());
            sibling->children.pop_back();
        }
    }

    void borrowFromNext(BTreeNode* node, int idx) {
        BTreeNode* child = node->children[idx];
        BTreeNode* sibling = node->children[idx + 1];
        child->keys.push_back(node->keys[idx]);
        node->keys[idx] = sibling->keys.front();
        sibling->keys.erase(sibling->keys.begin());
        if (!child->leaf) {
            child->children.push_back(sibling->children.front());
            sibling->children.erase(sibling->children.begin());
        }
    }

    void merge(BTreeNode* node, int idx) {
        BTreeNode* left = node->children[idx];
        BTreeNode* right = node->children[idx + 1];
        left->keys.push_back(node->keys[idx]);
        left->keys.insert(left->keys.end(), right->keys.begin(), right->keys.end());
        if (!left->leaf) {
            left->children.insert(left->children.end(), right->children.begin(), right->children.end());
        }
        node->keys.erase(node->keys.begin() + idx);
        node->children.erase(node->children.begin() + idx + 1);
    }

    void fill(BTreeNode* node, int idx) {
        if (idx != 0 && (int)node->children[idx - 1]->keys.size() >= t) {
            borrowFromPrev(node, idx);
        } else if (idx != (int)node->keys.size() && (int)node->children[idx + 1]->keys.size() >= t) {
            borrowFromNext(node, idx);
        } else if (idx != (int)node->keys.size()) {
            merge(node, idx);
        } else {
            merge(node, idx - 1);
        }
    }

    void removeFromInternal(BTreeNode* node, int idx) {
        int k = node->keys[idx];
        BTreeNode* left = node->children[idx];
        BTreeNode* right = node->children[idx + 1];
        if ((int)left->keys.size() >= t) {
            int pred = getPredecessor(left);
            node->keys[idx] = pred;
            deleteKey(left, pred);
        } else if ((int)right->keys.size() >= t) {
            int succ = getSuccessor(right);
            node->keys[idx] = succ;
            deleteKey(right, succ);
        } else {
            merge(node, idx);
            deleteKey(node->children[idx], k);
        }
    }

    void deleteKey(BTreeNode* node, int k) {
        int idx = findKey(node, k);
        if (idx < (int)node->keys.size() && node->keys[idx] == k) {
            if (node->leaf) {
                node->keys.erase(node->keys.begin() + idx);
            } else {
                removeFromInternal(node, idx);
            }
        } else {
            if (node->leaf) return; // key not present
            bool isLast = (idx == (int)node->keys.size());
            if ((int)node->children[idx]->keys.size() < t) {
                fill(node, idx);
            }
            if (isLast && idx > (int)node->keys.size()) {
                deleteKey(node->children[idx - 1], k);
            } else {
                deleteKey(node->children[idx], k);
            }
        }
    }
};

void printLevels(BTreeNode* root) {
    std::vector<BTreeNode*> frontier{root};
    int depth = 0;
    while (!frontier.empty()) {
        std::cout << "Level " << depth << ": ";
        std::vector<BTreeNode*> next;
        for (BTreeNode* node : frontier) {
            std::cout << "[";
            for (std::size_t j = 0; j < node->keys.size(); ++j) {
                std::cout << node->keys[j] << (j + 1 < node->keys.size() ? " " : "");
            }
            std::cout << "] ";
            for (BTreeNode* child : node->children) next.push_back(child);
        }
        std::cout << '\n';
        frontier = next;
        ++depth;
    }
}

int main() {
    BTree tree(2);
    for (int key : {10, 20, 5, 6, 12, 30, 7, 17}) {
        tree.insert(key);
    }
    std::cout << "After inserts:\n";
    printLevels(tree.getRoot());

    for (int key : {5, 6, 7, 10}) {
        tree.remove(key);
        std::cout << "After deleting " << key << ":\n";
        printLevels(tree.getRoot());
    }
}

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

class BTreeNode {
    boolean leaf;
    List<Integer> keys = new ArrayList<>();
    List<BTreeNode> children = new ArrayList<>();
    BTreeNode(boolean leaf) { this.leaf = leaf; }
}

class BTree {
    private final int t;
    private BTreeNode root;

    BTree(int t) {
        this.t = t;
        root = new BTreeNode(true);
    }

    BTreeNode getRoot() { return root; }

    void insert(int k) {
        if (root.keys.size() == 2 * t - 1) {
            BTreeNode newRoot = new BTreeNode(false);
            newRoot.children.add(root);
            splitChild(newRoot, 0);
            root = newRoot;
        }
        insertNonFull(root, k);
    }

    void remove(int k) {
        deleteKey(root, k);
        if (root.keys.isEmpty() && !root.leaf) {
            root = root.children.get(0);
        }
    }

    private void splitChild(BTreeNode parent, int i) {
        BTreeNode fullChild = parent.children.get(i);
        BTreeNode newChild = new BTreeNode(fullChild.leaf);
        int midKey = fullChild.keys.get(t - 1);
        newChild.keys.addAll(fullChild.keys.subList(t, fullChild.keys.size()));
        fullChild.keys.subList(t - 1, fullChild.keys.size()).clear();
        if (!fullChild.leaf) {
            newChild.children.addAll(fullChild.children.subList(t, fullChild.children.size()));
            fullChild.children.subList(t, fullChild.children.size()).clear();
        }
        parent.keys.add(i, midKey);
        parent.children.add(i + 1, newChild);
    }

    private void insertNonFull(BTreeNode node, int k) {
        int i = node.keys.size() - 1;
        if (node.leaf) {
            node.keys.add(0);
            while (i >= 0 && k < node.keys.get(i)) {
                node.keys.set(i + 1, node.keys.get(i));
                i--;
            }
            node.keys.set(i + 1, k);
        } else {
            while (i >= 0 && k < node.keys.get(i)) i--;
            i++;
            if (node.children.get(i).keys.size() == 2 * t - 1) {
                splitChild(node, i);
                if (k > node.keys.get(i)) i++;
            }
            insertNonFull(node.children.get(i), k);
        }
    }

    private int findKey(BTreeNode node, int k) {
        int idx = 0;
        while (idx < node.keys.size() && node.keys.get(idx) < k) idx++;
        return idx;
    }

    private int getPredecessor(BTreeNode node) {
        while (!node.leaf) node = node.children.get(node.children.size() - 1);
        return node.keys.get(node.keys.size() - 1);
    }

    private int getSuccessor(BTreeNode node) {
        while (!node.leaf) node = node.children.get(0);
        return node.keys.get(0);
    }

    private void borrowFromPrev(BTreeNode node, int idx) {
        BTreeNode child = node.children.get(idx);
        BTreeNode sibling = node.children.get(idx - 1);
        child.keys.add(0, node.keys.get(idx - 1));
        node.keys.set(idx - 1, sibling.keys.remove(sibling.keys.size() - 1));
        if (!child.leaf) {
            child.children.add(0, sibling.children.remove(sibling.children.size() - 1));
        }
    }

    private void borrowFromNext(BTreeNode node, int idx) {
        BTreeNode child = node.children.get(idx);
        BTreeNode sibling = node.children.get(idx + 1);
        child.keys.add(node.keys.get(idx));
        node.keys.set(idx, sibling.keys.remove(0));
        if (!child.leaf) {
            child.children.add(sibling.children.remove(0));
        }
    }

    private void merge(BTreeNode node, int idx) {
        BTreeNode left = node.children.get(idx);
        BTreeNode right = node.children.get(idx + 1);
        left.keys.add(node.keys.get(idx));
        left.keys.addAll(right.keys);
        if (!left.leaf) {
            left.children.addAll(right.children);
        }
        node.keys.remove(idx);
        node.children.remove(idx + 1);
    }

    private void fill(BTreeNode node, int idx) {
        if (idx != 0 && node.children.get(idx - 1).keys.size() >= t) {
            borrowFromPrev(node, idx);
        } else if (idx != node.keys.size() && node.children.get(idx + 1).keys.size() >= t) {
            borrowFromNext(node, idx);
        } else if (idx != node.keys.size()) {
            merge(node, idx);
        } else {
            merge(node, idx - 1);
        }
    }

    private void removeFromInternal(BTreeNode node, int idx) {
        int k = node.keys.get(idx);
        BTreeNode left = node.children.get(idx);
        BTreeNode right = node.children.get(idx + 1);
        if (left.keys.size() >= t) {
            int pred = getPredecessor(left);
            node.keys.set(idx, pred);
            deleteKey(left, pred);
        } else if (right.keys.size() >= t) {
            int succ = getSuccessor(right);
            node.keys.set(idx, succ);
            deleteKey(right, succ);
        } else {
            merge(node, idx);
            deleteKey(node.children.get(idx), k);
        }
    }

    private void deleteKey(BTreeNode node, int k) {
        int idx = findKey(node, k);
        if (idx < node.keys.size() && node.keys.get(idx) == k) {
            if (node.leaf) {
                node.keys.remove(idx);
            } else {
                removeFromInternal(node, idx);
            }
        } else {
            if (node.leaf) return; // key not present
            boolean isLast = (idx == node.keys.size());
            if (node.children.get(idx).keys.size() < t) {
                fill(node, idx);
            }
            if (isLast && idx > node.keys.size()) {
                deleteKey(node.children.get(idx - 1), k);
            } else {
                deleteKey(node.children.get(idx), k);
            }
        }
    }
}

public class BTreeDeleteDemo {
    static void printLevels(BTreeNode root) {
        List<BTreeNode> frontier = new ArrayList<>();
        frontier.add(root);
        int depth = 0;
        while (!frontier.isEmpty()) {
            StringBuilder sb = new StringBuilder("Level " + depth + ": ");
            List<BTreeNode> next = new ArrayList<>();
            for (BTreeNode node : frontier) {
                sb.append(node.keys).append(" ");
                next.addAll(node.children);
            }
            System.out.println(sb.toString());
            frontier = next;
            depth++;
        }
    }

    public static void main(String[] args) {
        BTree tree = new BTree(2);
        for (int key : new int[]{10, 20, 5, 6, 12, 30, 7, 17}) {
            tree.insert(key);
        }
        System.out.println("After inserts:");
        printLevels(tree.getRoot());

        for (int key : new int[]{5, 6, 7, 10}) {
            tree.remove(key);
            System.out.println("After deleting " + key + ":");
            printLevels(tree.getRoot());
        }
    }
}

8. B+ Tree: What’s Different

Core insight: In a B+ Tree, only the leaves store real data (or pointers to records); internal nodes hold nothing but routing keys used to steer a search toward the right leaf. Every leaf is additionally linked to its neighbor in key order, forming a sorted singly-linked chain across the bottom of the tree.

That single structural change has an outsized payoff for range queries. In a plain B-Tree, keys can live at internal nodes, so a range scan such as SQL’s WHERE age BETWEEN 20 AND 30 must repeatedly re-descend the tree (or do an in-order traversal juggling a stack) to visit keys scattered across internal and leaf nodes in sorted order. In a B+ Tree, every key lives in a leaf, and leaves are already threaded together in sorted order, so a range scan is: search once for the starting key to find the first leaf, then walk the next pointers, reading off keys until the upper bound is passed. No re-descent, no stack — just a linked-list walk. That is precisely why B+ Trees, not plain B-Trees, are the standard structure behind relational database indexes: point lookups are $O(\log_m n)$ exactly like a B-Tree, and range scans are $O(\log_m n)$ to find the start plus $O(k)$ to stream $k$ matching rows, with no extra tree traversal cost per row.

Descending to a leaf works like a B-Tree search, except the comparison rule only needs to pick the correct child — the actual key match, if any, is confirmed once the leaf is reached. A range scan finds the starting leaf the same way, then walks next pointers, collecting keys until one exceeds the upper bound.

class BPlusLeaf:
    def __init__(self):
        self.leaf = True
        self.keys = []
        self.next = None  # link to the next leaf in key order


class BPlusInternal:
    def __init__(self):
        self.leaf = False
        self.keys = []      # routing keys only -- no data lives here
        self.children = []


def find_leaf(root, k):
    node = root
    while not node.leaf:
        i = 0
        while i < len(node.keys) and k >= node.keys[i]:
            i += 1
        node = node.children[i]
    return node


def bplus_search(root, k):
    leaf = find_leaf(root, k)
    return k in leaf.keys


def range_scan(root, lo, hi):
    result = []
    leaf = find_leaf(root, lo)
    while leaf is not None:
        for key in leaf.keys:
            if key > hi:
                return result
            if key >= lo:
                result.append(key)
        leaf = leaf.next
    return result


# Build a tiny B+ Tree by hand: four linked leaves under one routing level.
leaf0, leaf1, leaf2, leaf3 = BPlusLeaf(), BPlusLeaf(), BPlusLeaf(), BPlusLeaf()
leaf0.keys, leaf1.keys, leaf2.keys, leaf3.keys = [5, 10], [15, 20], [25, 30], [35, 40]
leaf0.next, leaf1.next, leaf2.next = leaf1, leaf2, leaf3

root = BPlusInternal()
root.keys = [15, 25, 35]
root.children = [leaf0, leaf1, leaf2, leaf3]

print("Search 20:", bplus_search(root, 20))          # Search 20: True
print("Search 22:", bplus_search(root, 22))          # Search 22: False
print("Range [12, 27]:", range_scan(root, 12, 27))   # Range [12, 27]: [15, 20, 25]

#include <iostream>
#include <vector>

struct BPlusNode {
    bool leaf;
    std::vector<int> keys;
    std::vector<BPlusNode*> children; // internal nodes only
    BPlusNode* next = nullptr;         // leaf nodes only
    explicit BPlusNode(bool isLeaf) : leaf(isLeaf) {}
};

BPlusNode* findLeaf(BPlusNode* root, int k) {
    BPlusNode* node = root;
    while (!node->leaf) {
        std::size_t i = 0;
        while (i < node->keys.size() && k >= node->keys[i]) {
            ++i;
        }
        node = node->children[i];
    }
    return node;
}

bool bplusSearch(BPlusNode* root, int k) {
    BPlusNode* leaf = findLeaf(root, k);
    for (int key : leaf->keys) {
        if (key == k) return true;
    }
    return false;
}

std::vector<int> rangeScan(BPlusNode* root, int lo, int hi) {
    std::vector<int> result;
    BPlusNode* leaf = findLeaf(root, lo);
    while (leaf != nullptr) {
        for (int key : leaf->keys) {
            if (key > hi) return result;
            if (key >= lo) result.push_back(key);
        }
        leaf = leaf->next;
    }
    return result;
}

int main() {
    auto* leaf0 = new BPlusNode(true); leaf0->keys = {5, 10};
    auto* leaf1 = new BPlusNode(true); leaf1->keys = {15, 20};
    auto* leaf2 = new BPlusNode(true); leaf2->keys = {25, 30};
    auto* leaf3 = new BPlusNode(true); leaf3->keys = {35, 40};
    leaf0->next = leaf1; leaf1->next = leaf2; leaf2->next = leaf3;

    auto* root = new BPlusNode(false);
    root->keys = {15, 25, 35};
    root->children = {leaf0, leaf1, leaf2, leaf3};

    std::cout << "Search 20: " << (bplusSearch(root, 20) ? "true" : "false") << '\n';
    std::cout << "Search 22: " << (bplusSearch(root, 22) ? "true" : "false") << '\n';

    std::vector<int> hits = rangeScan(root, 12, 27);
    std::cout << "Range [12, 27]: ";
    for (std::size_t i = 0; i < hits.size(); ++i) {
        std::cout << hits[i] << (i + 1 < hits.size() ? ", " : "\n");
    }
}

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

class BPlusNode {
    boolean leaf;
    List<Integer> keys = new ArrayList<>();
    List<BPlusNode> children = new ArrayList<>(); // internal only
    BPlusNode next = null;                          // leaf only
    BPlusNode(boolean leaf) { this.leaf = leaf; }
}

public class BPlusTreeDemo {
    static BPlusNode findLeaf(BPlusNode root, int k) {
        BPlusNode node = root;
        while (!node.leaf) {
            int i = 0;
            while (i < node.keys.size() && k >= node.keys.get(i)) {
                i++;
            }
            node = node.children.get(i);
        }
        return node;
    }

    static boolean search(BPlusNode root, int k) {
        BPlusNode leaf = findLeaf(root, k);
        return leaf.keys.contains(k);
    }

    static List<Integer> rangeScan(BPlusNode root, int lo, int hi) {
        List<Integer> result = new ArrayList<>();
        BPlusNode leaf = findLeaf(root, lo);
        while (leaf != null) {
            for (int key : leaf.keys) {
                if (key > hi) return result;
                if (key >= lo) result.add(key);
            }
            leaf = leaf.next;
        }
        return result;
    }

    public static void main(String[] args) {
        BPlusNode leaf0 = new BPlusNode(true); leaf0.keys.add(5); leaf0.keys.add(10);
        BPlusNode leaf1 = new BPlusNode(true); leaf1.keys.add(15); leaf1.keys.add(20);
        BPlusNode leaf2 = new BPlusNode(true); leaf2.keys.add(25); leaf2.keys.add(30);
        BPlusNode leaf3 = new BPlusNode(true); leaf3.keys.add(35); leaf3.keys.add(40);
        leaf0.next = leaf1; leaf1.next = leaf2; leaf2.next = leaf3;

        BPlusNode root = new BPlusNode(false);
        root.keys.add(15); root.keys.add(25); root.keys.add(35);
        root.children.add(leaf0); root.children.add(leaf1); root.children.add(leaf2); root.children.add(leaf3);

        System.out.println("Search 20: " + search(root, 20));
        System.out.println("Search 22: " + search(root, 22));
        System.out.println("Range [12, 27]: " + rangeScan(root, 12, 27));
    }
}

10. Complexity Analysis

Search, insert, and delete: all $O(\log_m n)$ for a B-Tree or B+ Tree of order $m$ over $n$ keys, since the height is $O(\log_m n)$ and each level does $O(m)$ or $O(\log m)$ work depending on whether the in-node scan is linear or binary. B+ Tree range scan: $O(\log_m n + k)$ to retrieve $k$ matching keys, since after the initial descent the walk is a linear pass over the leaf chain. Space: $\Theta(n)$ keys distributed across $\Theta(n / m)$ nodes.

The Big-O class, $O(\log n)$, is the same family as a balanced BST’s. What changes is the constant hidden inside $\log_m$ versus $\log_2$, and that constant is the entire point in a disk-backed setting: minimizing tree height, not just achieving a logarithmic order, is what matters, because height is measured in disk seeks, and a disk seek costs roughly $10^5$ to $10^6$ times what an in-memory comparison costs. A binary tree and a B-Tree can both be “$O(\log n)$,” yet one needs 30 seeks per query and the other needs 4 — a difference that dwarfs any constant-factor optimization done inside a single node. This is also why B-Trees choose $m$ to match the page size of the storage medium: the goal is not the smallest possible tree in the abstract, but the fewest possible page transfers in practice.

11. Applications & Alternatives

Where B-Trees and B+ Trees show up

  • Relational database indexes: PostgreSQL’s default B-tree index type and MySQL/InnoDB’s clustered and secondary indexes are both B+ Trees, chosen specifically for efficient range queries and ordered scans.
  • Filesystem directory structures: NTFS directories are B+ Trees keyed on filename; ext4 uses an HTree (a specialized hashed B-tree variant) for large directories, for the same reason — fast lookup and ordered traversal on disk.
  • In-memory hash indexes, by contrast: a hash index gives $O(1)$ average point lookups but has no notion of key order, so it cannot answer WHERE age BETWEEN 20 AND 30 without scanning every entry; a B+ Tree answers the same query in $O(\log_m n + k)$ by walking a contiguous run of the leaf chain.
  • LSM-trees: write-heavy engines (LevelDB, RocksDB, Cassandra) favor log-structured merge trees over B-Trees for their better write throughput, trading some read amplification for it — a reminder that B-Trees are not universally optimal, only optimal for read-heavy, seek-sensitive, range-query workloads.

The decision is always about the dominant operation. If the workload is point lookups only, with no interest in ordering, a hash index is simpler and asymptotically just as fast. The moment range queries, ordered iteration, or disk locality matter, a B+ Tree’s combination of low height and a linked leaf layer becomes hard to beat.

12. Exercises

Easy

  1. Given a B-Tree with root [20, 40] and leaf children [10, 15], [25, 30, 35], [45, 50], trace the search for 35 and for 18 by hand, listing every node visited and every comparison made.

Medium

  1. Using the B-Tree insert implementation from Section 6 as given, implement search(tree, k) as a method on the same BTree class (rather than the free function from Section 5), and verify it finds every key the insert trace placed into the tree from Section 3.

Hard

  1. Implement a B+ Tree range query range_query(root, lo, hi) that returns all keys $k$ with $lo \le k \le hi$, using only the leaf-linked-list walk shown in Section 9 — no re-descending into the tree once the starting leaf is found. Test it against a brute-force scan over the same keys to confirm the results match for several random $(lo, hi)$ pairs.
Mastery challenge: Design the on-disk index for a table with a billion rows, where the dominant query pattern is WHERE timestamp BETWEEN t1 AND t2. Choose B-Tree versus B+ Tree, justify the order $m$ in terms of a realistic disk page size, estimate the resulting tree height, and explain precisely why a hash index or a plain binary search tree would perform worse on this workload.

Review rhythm: tomorrow, redraw the invariants from memory and re-derive why splitting happens on the way down rather than after an overflow; next week, implement B-Tree delete from scratch without looking at this page, then check it against the borrow and merge traces here; several weeks later, explain to someone else why a database index is a B+ Tree and not a binary search tree, using disk seeks (not Big-O alone) as the argument.

13. Summary Cheat Sheet

  • Binary search trees are $O(\log_2 n)$ tall; B-Trees of order $m$ are $O(\log_m n)$ tall — far fewer disk seeks for the same $n$.
  • Every non-root node holds between $t-1$ and $2t-1$ keys; every leaf sits at the same depth.
  • Insert splits a full node before descending into it, so one downward pass suffices with no separate rebalancing phase.
  • Delete guarantees the child about to be entered has at least $t$ keys, by borrowing from a sibling or merging with one.
  • B+ Trees keep all data in the leaves, with internal nodes storing routing keys only, and leaves linked in sorted order.
  • That leaf-linked-list is what makes range scans $O(\log_m n + k)$ instead of requiring repeated tree traversal.
  • Databases and filesystems use B+ Trees because minimizing height directly minimizes disk seeks, and range queries are common.

Continue the DSA Curriculum

Data Structures & Algorithms Hub

Browse the complete 18-level algorithm curriculum and practical project sequence.

Open the DSA Hub
Part 10: BST, AVL & Red-Black Trees

The general self-balancing search tree background this lesson generalizes into a disk-aware, multiway structure.

Read the BST & Balanced Trees Guide
Union-Find, Trie, Fenwick Tree & Segment Tree Decision Guide

Compare more specialized tree and structure choices for indexing, range queries, and disjoint-set problems.

Read the Advanced Structures Guide