B-tree insertion, splitting and search: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Build a minimum-degree-two B-tree by splitting full nodes before descending. Each node holds one to three keys, and all leaves stay at the same depth.

Before descending, split a full three-key child and promote its median into the non-full parent. Insert into a non-full leaf. Splitting a full root grows the tree by one level while all leaves retain equal depth.

Open the 3D visualization

B-tree insertion, splitting and search example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

When to use B-tree insertion, splitting and search

Teaching multiway ordered indexes and page-oriented balanced search.

Choosing an alternative

A minimum-degree-two B-tree stores one to three keys per node. Red-black trees encode related multiway balance inside a binary tree.

Worked example: input and state changes

Example input

10,20,5,6,12,30,7,17,2,8,1,9 | 17

These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.

  1. Step 0: Start with an empty leaf root.

    State at this checkpoint
    {
      "values": [
        0,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1
      ],
      "active": [],
      "kind": "matrix",
      "columns": 8,
      "nodes": [
        {
          "keys": [],
          "children": []
        }
      ]
    }
  2. Step 5: Insert 6 into a non-full leaf.

    State at this checkpoint
    {
      "values": [
        1,
        10,
        -1,
        -1,
        1,
        2,
        -1,
        -1,
        2,
        5,
        6,
        -1,
        -1,
        -1,
        -1,
        -1,
        1,
        20,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1
      ],
      "active": [
        8
      ],
      "kind": "matrix",
      "columns": 8,
      "nodes": [
        {
          "keys": [
            10
          ],
          "children": [
            1,
            2
          ]
        },
        {
          "keys": [
            5,
            6
          ],
          "children": []
        },
        {
          "keys": [
            20
          ],
          "children": []
        }
      ]
    }
  3. Step 10: Insert 17 into a non-full leaf.

    State at this checkpoint
    {
      "values": [
        2,
        10,
        20,
        -1,
        1,
        2,
        3,
        -1,
        3,
        5,
        6,
        7,
        -1,
        -1,
        -1,
        -1,
        2,
        12,
        17,
        -1,
        -1,
        -1,
        -1,
        -1,
        1,
        30,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1
      ],
      "active": [
        16
      ],
      "kind": "matrix",
      "columns": 8,
      "nodes": [
        {
          "keys": [
            10,
            20
          ],
          "children": [
            1,
            2,
            3
          ]
        },
        {
          "keys": [
            5,
            6,
            7
          ],
          "children": []
        },
        {
          "keys": [
            12,
            17
          ],
          "children": []
        },
        {
          "keys": [
            30
          ],
          "children": []
        }
      ]
    }
  4. Step 15: Insert 1 into a non-full leaf.

    State at this checkpoint
    {
      "values": [
        1,
        10,
        -1,
        -1,
        1,
        2,
        -1,
        -1,
        1,
        6,
        -1,
        -1,
        3,
        4,
        -1,
        -1,
        1,
        20,
        -1,
        -1,
        5,
        6,
        -1,
        -1,
        3,
        1,
        2,
        5,
        -1,
        -1,
        -1,
        -1,
        2,
        7,
        8,
        -1,
        -1,
        -1,
        -1,
        -1,
        2,
        12,
        17,
        -1,
        -1,
        -1,
        -1,
        -1,
        1,
        30,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1
      ],
      "active": [
        24
      ],
      "kind": "matrix",
      "columns": 8,
      "nodes": [
        {
          "keys": [
            10
          ],
          "children": [
            1,
            2
          ]
        },
        {
          "keys": [
            6
          ],
          "children": [
            3,
            4
          ]
        },
        {
          "keys": [
            20
          ],
          "children": [
            5,
            6
          ]
        },
        {
          "keys": [
            1,
            2,
            5
          ],
          "children": []
        },
        {
          "keys": [
            7,
            8
          ],
          "children": []
        },
        {
          "keys": [
            12,
            17
          ],
          "children": []
        },
        {
          "keys": [
            30
          ],
          "children": []
        }
      ]
    }
  5. Step 20: 17 found; every leaf has the same depth.

    State at this checkpoint
    {
      "values": [
        1,
        10,
        -1,
        -1,
        1,
        2,
        -1,
        -1,
        1,
        6,
        -1,
        -1,
        3,
        4,
        -1,
        -1,
        1,
        20,
        -1,
        -1,
        5,
        6,
        -1,
        -1,
        3,
        1,
        2,
        5,
        -1,
        -1,
        -1,
        -1,
        3,
        7,
        8,
        9,
        -1,
        -1,
        -1,
        -1,
        2,
        12,
        17,
        -1,
        -1,
        -1,
        -1,
        -1,
        1,
        30,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1
      ],
      "active": [],
      "kind": "matrix",
      "columns": 8,
      "nodes": [
        {
          "keys": [
            10
          ],
          "children": [
            1,
            2
          ]
        },
        {
          "keys": [
            6
          ],
          "children": [
            3,
            4
          ]
        },
        {
          "keys": [
            20
          ],
          "children": [
            5,
            6
          ]
        },
        {
          "keys": [
            1,
            2,
            5
          ],
          "children": []
        },
        {
          "keys": [
            7,
            8,
            9
          ],
          "children": []
        },
        {
          "keys": [
            12,
            17
          ],
          "children": []
        },
        {
          "keys": [
            30
          ],
          "children": []
        }
      ],
      "result": 1
    }

Expected final state

17 found; every leaf has the same depth.

Complexity and input bounds

Family: Trees. Time complexity: O(log n) per operation (fixed degree).

Implementation detail: This view implements insertion, splitting and search, not deletion. Matrix rows show key count, three key slots and four child-row indices; -1 means absent. Downloads use BFS node numbering and additionally report inorder keys, node count and height for structural tests.

Space complexity: O(n) auxiliary node and traversal storage, plus recorded visualization frames.

Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.

1..12 keys (0..99) | search key. Matrix rows are nodes: count, three key slots, then four child-row indices; -1 means absent.

The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.

Common mistakes and limitations

A node with k keys has either no children or k+1 children. Move the upper child pointers when splitting an internal node. Duplicate keys are ignored.

Further reading

For background on algorithm analysis and the JavaScript function interface:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// Minimum-degree-two B-tree insertion/search, n 0..12 keys and target 0..99. Duplicate keys ignored. Returns target membership. Output capacity at least 112: [0] unique count, [1] node count, [2] height (empty=0), [3..14] inorder keys. From [16], each BFS node has eight fields: key count, three key slots, four child BFS indices; absent keys/children -1. Remaining output cells zero. Empty tree retains one empty leaf node. Full nodes split before descent; all leaves have equal depth. O(log n) per operation at fixed degree, O(n log n) build and O(n) serialization/storage. Deletion is outside this view. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation.
function algorithm(a, n, target, output) {
    let keys = Array(256).fill(0); let counts = Array(256).fill(0); let children = Array(256).fill(0); let leaf = Array(256).fill(0); let queue = Array(256).fill(0); let mapping = Array(256).fill(0); let depth = Array(256).fill(0); let stack = Array(256).fill(0); let stage = Array(256).fill(0);
    let root = 0; let nodes = 1; let u = 0; let value = 0; let index = 0; let found = 0; let old = 0; let w = 0; let z = 0; let middle = 0; let j = 0; let top = 0; let step = 0; let length = 0; let head = 0; let tail = 1; let base = 0; let height = 0;
    for (let i = 0; i < 16; i++) { leaf[i] = 1; mapping[i] = -1; }
    for (let i = 0; i < 64; i++) { children[i] = -1; }
    for (let k = 0; k < n; k++) {
        value = a[k]; u = root; found = 0;
        while (1 == 1) {
            index = 0; while (index < counts[u] && value > keys[3 * u + index]) { index++; }
            if (index < counts[u] && keys[3 * u + index] == value) { found = 1; break; }
            if (leaf[u] != 0) { break; } u = children[4 * u + index];
        }
        if (found != 0) { continue; }
        if (counts[root] == 3) { old = root; root = nodes++; leaf[root] = 0; children[4 * root] = old; u = root; index = 0; w = children[4 * u + index]; z = nodes++; leaf[z] = leaf[w]; counts[z] = 1; keys[3 * z] = keys[3 * w + 2]; middle = keys[3 * w + 1];
    if (leaf[w] == 0) { children[4 * z] = children[4 * w + 2]; children[4 * z + 1] = children[4 * w + 3]; }
    counts[w] = 1;
    for (j = counts[u]; j > index; j--) { children[4 * u + j + 1] = children[4 * u + j]; }
    children[4 * u + index + 1] = z;
    for (j = counts[u] - 1; j >= index; j--) { keys[3 * u + j + 1] = keys[3 * u + j]; }
    keys[3 * u + index] = middle; counts[u]++; }
        u = root;
        while (leaf[u] == 0) {
            index = 0; while (index < counts[u] && value > keys[3 * u + index]) { index++; }
            if (counts[children[4 * u + index]] == 3) { w = children[4 * u + index]; z = nodes++; leaf[z] = leaf[w]; counts[z] = 1; keys[3 * z] = keys[3 * w + 2]; middle = keys[3 * w + 1];
    if (leaf[w] == 0) { children[4 * z] = children[4 * w + 2]; children[4 * z + 1] = children[4 * w + 3]; }
    counts[w] = 1;
    for (j = counts[u]; j > index; j--) { children[4 * u + j + 1] = children[4 * u + j]; }
    children[4 * u + index + 1] = z;
    for (j = counts[u] - 1; j >= index; j--) { keys[3 * u + j + 1] = keys[3 * u + j]; }
    keys[3 * u + index] = middle; counts[u]++; if (value > keys[3 * u + index]) { index++; } }
            u = children[4 * u + index];
        }
        index = counts[u]; while (index > 0 && keys[3 * u + index - 1] > value) { keys[3 * u + index] = keys[3 * u + index - 1]; index--; }
        keys[3 * u + index] = value; counts[u]++;
    }
    found = 0; u = root;
    while (1 == 1) {
        index = 0; while (index < counts[u] && target > keys[3 * u + index]) { index++; }
        if (index < counts[u] && keys[3 * u + index] == target) { found = 1; break; }
        if (leaf[u] != 0) { break; } u = children[4 * u + index];
    }
    for (let i = 0; i < 112; i++) { output[i] = 0; }
    stack[0] = root; stage[0] = 0; top = 1;
    while (top > 0) {
        u = stack[top - 1]; step = stage[top - 1]++;
        if (leaf[u] != 0) { if (step < counts[u]) { output[3 + length++] = keys[3 * u + step]; } else { top--; } }
        else if (step > 2 * counts[u]) { top--; }
        else if ((step & 1) == 0) { stack[top] = children[4 * u + (step >> 1)]; stage[top++] = 0; }
        else { output[3 + length++] = keys[3 * u + (step >> 1)]; }
    }
    queue[0] = root; mapping[root] = 0; depth[0] = 1;
    while (head < tail) {
        u = queue[head]; base = 16 + head * 8; if (depth[head] > height) { height = depth[head]; }
        output[base] = counts[u];
        for (let i = 0; i < 3; i++) { output[base + 1 + i] = -1; if (i < counts[u]) { output[base + 1 + i] = keys[3 * u + i]; } }
        for (let i = 0; i < 4; i++) {
            output[base + 4 + i] = -1;
            if (leaf[u] == 0 && i <= counts[u]) { w = children[4 * u + i]; mapping[w] = tail; queue[tail] = w; depth[tail++] = depth[head] + 1; output[base + 4 + i] = mapping[w]; }
        }
        head++;
    }
    if (length == 0) { height = 0; }
    output[0] = length; output[1] = tail; output[2] = height;
    return found;
}

Source

Foundational published B-tree research. The playground uses minimum degree two and demonstrates insertion/search only, rather than a full disk-based indexing system.