1function bTreeInsert(root, key, t = 2) {
2 if (root.keys.length === 2 * t - 1) {
3 const newRoot = { keys: [], children: [root] };
4 splitChild(newRoot, 0, t);
5 root = newRoot;
6 }
7 insertNonFull(root, key, t);
8 return root;
9}
10function splitChild(parent, i, t) {
11 const full = parent.children[i];
12 const mid = full.keys[t - 1];
13 const right = { keys: full.keys.slice(t), children: full.children.slice(t) };
14 full.keys = full.keys.slice(0, t - 1);
15 full.children = full.children.slice(0, t);
16 parent.keys.splice(i, 0, mid);
17 parent.children.splice(i + 1, 0, right);
18}
19function insertNonFull(node, key, t) {
20 if (node.children.length === 0) {
21 node.keys.push(key);
22 node.keys.sort((a, b) => a - b);
23 return;
24 }
25 let i = node.keys.findIndex((k) => key < k);
26 if (i === -1) i = node.keys.length;
27 if (node.children[i].keys.length === 2 * t - 1) {
28 splitChild(node, i, t);
29 if (key > node.keys[i]) i++;
30 }
31 insertNonFull(node.children[i], key, t);
32}