JS如何实现B树？B树的插入和删除

class BTreeNode {
  constructor(leaf = true) {
    this.keys = []; // 存储键值
    this.children = []; // 存储子节点，仅在非叶子节点有效
    this.leaf = leaf; // 是否为叶子节点
  }
}

class BTree {
  constructor(t) {
    this.root = new BTreeNode(); // 根节点
    this.t = t; // 最小度数（每个节点至少 t-1 个键）
  }
}

BTree.prototype.insert = function(k) {
  let root = this.root;
  if (root.keys.length === (2 * this.t - 1)) {
    // 根节点已满，需要分裂
    let newNode = new BTreeNode(false); // 新根节点
    newNode.children[0] = root;
    this.splitChild(newNode, 0, root);
    this.root = newNode;
    this.insertNonFull(newNode, k);
  } else {
    this.insertNonFull(root, k);
  }
};

BTree.prototype.insertNonFull = function(x, k) {
  let i = x.keys.length - 1;
  if (x.leaf) {
    // 叶子节点，直接插入
    while (i >= 0 && k < x.keys[i]) {
      x.keys[i + 1] = x.keys[i];
      i--;
    }
    x.keys[i + 1] = k;
  } else {
    // 非叶子节点，找到合适的子节点插入
    while (i >= 0 && k < x.keys[i]) {
      i--;
    }
    i++;
    if (x.children[i].keys.length === (2 * this.t - 1)) {
      this.splitChild(x, i, x.children[i]);
      if (k > x.keys[i]) {
        i++;
      }
    }
    this.insertNonFull(x.children[i], k);
  }
};

BTree.prototype.splitChild = function(x, i, y) {
  let t = this.t;
  let z = new BTreeNode(y.leaf);
  for (let j = 0; j < t - 1; j++) {
    z.keys[j] = y.keys[j + t];
  }
  if (!y.leaf) {
    for (let j = 0; j < t; j++) {
      z.children[j] = y.children[j + t];
    }
    y.children.length = t; // 截断y的children
  }
  y.keys.length = t - 1; // 截断y的keys

  for (let j = x.keys.length; j > i; j--) {
    x.keys[j] = x.keys[j - 1];
  }
  x.keys[i] = y.keys[t - 1];

  for (let j = x.children.length; j > i + 1; j--) {
    x.children[j] = x.children[j - 1];
  }
  x.children[i + 1] = z;

  x.children.splice(i, 1, y, z); //替换x.children[i]为y和z
  x.keys.splice(i, 0, y.keys[t - 1]); // 在x.keys[i]插入y.keys[t-1]
  y.keys.length = t - 1; // 截断y的keys
};

BTree.prototype.delete = function(k) {
  this.deleteKey(this.root, k);
};

BTree.prototype.deleteKey = function(x, k) {
  let idx = x.keys.findIndex(key => key === k);

  if (idx !== -1) { // k存在于节点x中
    if (x.leaf) { // 情况1：x是叶子节点
      x.keys.splice(idx, 1); // 直接删除
    } else { // 情况2：x是非叶子节点
      let t = this.t;
      let y = x.children[idx];
      let z = x.children[idx + 1];

      if (y.keys.length >= t) { // 情况2a：前驱节点y至少有t个键
        let predecessor = this.findPredecessor(y); // 找到k的前驱
        x.keys[idx] = predecessor; // 用前驱替换k
        this.deleteKey(y, predecessor); // 递归删除前驱
      } else if (z.keys.length >= t) { // 情况2b：后继节点z至少有t个键
        let successor = this.findSuccessor(z); // 找到k的后继
        x.keys[idx] = successor; // 用后继替换k
        this.deleteKey(z, successor); // 递归删除后继
      } else { // 情况2c：y和z都只有t-1个键
        this.merge(x, idx); // 合并y和z
        this.deleteKey(y, k); // 在合并后的节点中删除k
      }
    }
  } else { // k不存在于节点x中
    if (x.leaf) { // 情况3：k不存在，且x是叶子节点
      return; // 树中没有k
    }

    let i = 0;
    while (i < x.keys.length && k > x.keys[i]) {
      i++;
    }

    let child = x.children[i];

    if (child.keys.length === this.t - 1) { // 情况4：子节点只有t-1个键
      this.fill(x, i); // 填充子节点
    }

    this.deleteKey(x.children[i], k); // 递归删除
  }
};

BTree.prototype.findPredecessor = function(x) {
    while (!x.leaf) {
        x = x.children[x.keys.length];
    }
    return x.keys[x.keys.length - 1];
};

BTree.prototype.findSuccessor = function(x) {
    while (!x.leaf) {
        x = x.children[0];
    }
    return x.keys[0];
};

BTree.prototype.merge = function(x, i) {
  let t = this.t;
  let y = x.children[i];
  let z = x.children[i + 1];

  y.keys[t - 1] = x.keys[i]; // 将x[i]放到y中

  for (let j = 0; j < t - 1; j++) { // 将z的所有键复制到y
    y.keys[t + j] = z.keys[j];
  }

  if (!y.leaf) { // 如果y不是叶子节点，复制z的子节点
    for (let j = 0; j < t; j++) {
      y.children[t + j] = z.children[j];
    }
  }

  x.keys.splice(i, 1); // 从x中移除x[i]
  x.children.splice(i + 1, 1); // 释放z

  if (x === this.root && x.keys.length === 0) { // 如果根节点为空
    this.root = y; // 让y成为新的根节点
  }
};

BTree.prototype.fill = function(x, i) {
  let t = this.t;

  if (i !== 0 && x.children[i - 1].keys.length >= t) { // 情况1：左兄弟至少有t个键
    this.borrowFromPrev(x, i);
  } else if (i !== x.children.length - 1 && x.children[i + 1].keys.length >= t) { // 情况2：右兄弟至少有t个键
    this.borrowFromNext(x, i);
  } else { // 情况3：合并
    if (i !== x.children.length - 1) {
      this.merge(x, i);
    } else {
      this.merge(x, i - 1);
    }
  }
};

BTree.prototype.borrowFromPrev = function(x, i) {
  let t = this.t;
  let child = x.children[i];
  let sibling = x.children[i - 1];

  for (let j = child.keys.length - 1; j >= 0; j--) {
    child.keys[j + 1] = child.keys[j];
  }

  if (!child.leaf) {
    for (let j = child.children.length - 1; j >= 0; j--) {
      child.children[j + 1] = child.children[j];
    }
  }

  child.keys[0] = x.keys[i - 1];

  if (!child.leaf) {
    child.children[0] = sibling.children[sibling.keys.length];
  }

  x.keys[i - 1] = sibling.keys[sibling.keys.length - 1];

  child.keys.length++;
  sibling.keys.length--;
};

BTree.prototype.borrowFromNext = function(x, i) {
  let t = this.t;
  let child = x.children[i];
  let sibling = x.children[i + 1];

  child.keys[child.keys.length] = x.keys[i];

  if (!child.leaf) {
    child.children[child.children.length] = sibling.children[0];
  }

  x.keys[i] = sibling.keys[0];

  for (let j = 0; j < sibling.keys.length - 1; j++) {
    sibling.keys[j] = sibling.keys[j + 1];
  }

  if (!sibling.leaf) {
    for (let j = 0; j < sibling.children.length - 1; j++) {
      sibling.children[j] = sibling.children[j + 1];
    }
  }

  child.keys.length++;
  sibling.keys.length--;
};