Advanced Trees

B-Tree

What is a B-Tree?

A B-Tree generalizes the Binary Search Tree by letting each node hold multiple sorted keys and have more than two children. Instead of "smaller left, larger right," a node with k keys has k+1 children, and each child's entire range of values falls between two adjacent keys in the parent (or before the first / after the last).

Why Use a B-Tree?

This wide branching factor is the entire point: B-Trees were designed for data that lives on disk, not in memory. Reading from disk is orders of magnitude slower than reading from RAM, and each disk read typically pulls in a whole block regardless of how much of it you actually need — so it makes sense to pack as many keys as possible into a single node/block and minimize the number of levels (and therefore disk reads) needed to find anything. This is exactly why B-Trees (and their variant, B+ Trees) are the standard on-disk index structure in databases like PostgreSQL and MySQL's InnoDB, and in filesystems like NTFS and ext4.

Key Properties

Every B-Tree has a minimum degree t that fixes its shape: every node (except the root) must hold at least t-1 keys and at most 2t-1 keys, giving it between t and 2t children. Crucially, every leaf sits at exactly the same depth — a B-Tree never becomes lopsided the way an unbalanced BST can, because it grows upward from the root instead of downward from the leaves.

Every node holds sorted keys

A node with k keys has exactly k+1 children — one for each gap between (and around) its keys.

Keys per node are bounded

Every non-root node holds between t-1 and 2t-1 keys, where t is the tree's minimum degree.

All leaves are at the same depth

Unlike a plain BST, a B-Tree grows in height only by splitting the root — every leaf is always exactly the same distance from the root.

Splits happen proactively

This visualizer splits a full node on the way down before inserting into it, so a single insertion never has to backtrack up the tree.

How Does a Node Split Work?

Node [10, 20, 30] is full — inserting 25 triggers a split

Median 20 moves up; 25 lands in the right half

Full node (violation)Median key, promoted upHalf that received the new key

Algorithm Steps (Insertion)

If the tree is empty, create a new leaf node holding just the new key
If the root itself is full (has 2t-1 keys), split it first — this is the only way the tree grows taller
Walk down from the root looking for the leaf where the key belongs. At each internal node:
- Find which child's range the key falls into
- If that child is full, split it before descending into it
- Move into that child and repeat
Once a non-full leaf is reached, insert the key into its sorted position

Time Complexity

Time Complexity: Height is O(log_t n) — search, insert, and delete all cost O(log_t n).
Disk I/O: Since each node is one block, height directly bounds the number of disk reads needed.

Time Complexity Analysis

Insertion needs O(1) extra space per split — no recursion stack proportional to the tree's key count, just a constant amount of bookkeeping per level the insertion touches, and the visualizer here uses t = 2 (so nodes can hold up to 3 keys) purely to keep the diagram small; real-world B-Trees typically use a t sized to match a disk block, often in the hundreds.

Daily DSA Challenge by Scale Engineer

Insert values and watch full nodes split to keep the B-tree balanced (min degree t = 2)

Tree is empty

No tree yet — insert a value or generate a random tree

Node (holds up to 3 sorted keys)RootSplit by this insert

Test Your Knowledge before moving forward!

B-Tree Quiz

How it works:

+1 point for each correct answer
0 points for wrong answers
-0.5 point penalty for viewing explanations
Earn stars based on your final score (max 5 stars)

B-Tree Insertion Implementation

// B-Tree node — t is the tree's minimum degree
// (max keys per node = 2t-1, max children = 2t)
class BTreeNode {
  constructor(leaf) {
    this.keys = [];
    this.children = [];
    this.leaf = leaf;
  }
}

const T = 3; // minimum degree, tune to taste (or to your disk block size)

// Splits the full child at index i of parent, promoting its median key up
function splitChild(parent, i) {
  const fullChild = parent.children[i];
  const newChild = new BTreeNode(fullChild.leaf);

  const midKey = fullChild.keys[T - 1];
  newChild.keys = fullChild.keys.slice(T);
  fullChild.keys = fullChild.keys.slice(0, T - 1);

  if (!fullChild.leaf) {
    newChild.children = fullChild.children.slice(T);
    fullChild.children = fullChild.children.slice(0, T);
  }

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

// Inserts into a node that is guaranteed not to be full
function insertNonFull(node, key) {
  let i = node.keys.length - 1;

  if (node.leaf) {
    while (i >= 0 && key < node.keys[i]) i--;
    node.keys.splice(i + 1, 0, key);
  } else {
    while (i >= 0 && key < node.keys[i]) i--;
    i++;
    if (node.children[i].keys.length === 2 * T - 1) {
      splitChild(node, i);
      if (key > node.keys[i]) i++;
    }
    insertNonFull(node.children[i], key);
  }
}

function insert(root, key) {
  if (root === null) {
    const node = new BTreeNode(true);
    node.keys = [key];
    return node;
  }

  if (root.keys.length === 2 * T - 1) {
    // Root is full — split it first; this is the only way the tree grows taller
    const newRoot = new BTreeNode(false);
    newRoot.children.push(root);
    splitChild(newRoot, 0);
    insertNonFull(newRoot, key);
    return newRoot;
  }

  insertNonFull(root, key);
  return root;
}

// Usage example
let root = null;
[10, 20, 5, 6, 12, 30, 7, 17].forEach((key) => {
  root = insert(root, key);
});

Done With the Learning

Mark B-Tree as done and view it on your dashboard

Explore Other Tree Topics

Red-Black Tree

Trie (Prefix Tree)

Segment Tree

Fenwick Tree

AVL Balancing

BST Insertion

In-order Traversal

Structure & Properties