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.
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.
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": [] } ] }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": [] } ] }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": [] } ] }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": [] } ] }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:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
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.
- Organization and maintenance of large ordered indexes
R. Bayer; E. M. McCreight (1972). Classic research paper.