Method set

packages/db/src/utils/btree.ts:777–836

(
    key: K,
    value: V,
    overwrite: boolean | undefined,
    tree: BTree<K, V>,
  )

  // Internal Node: set & node splitting //////////////////////////////////////

  set(
    key: K,
    value: V,
    overwrite: boolean | undefined,
    tree: BTree<K, V>,
  ): boolean | BNodeInternal<K, V> {
    const c = this.children,
      max = tree._maxNodeSize,
      cmp = tree._compare
    let i = Math.min(this.indexOf(key, 0, cmp), c.length - 1),
      child = c[i]!

    if (child.isShared) c[i] = child = child.clone()
    if (child.keys.length >= max) {
      // child is full; inserting anything else will cause a split.
      // Shifting an item to the left or right sibling may avoid a split.
      // We can do a shift if the adjacent node is not full and if the
      // current key can still be placed in the same node after the shift.
      let other: BNode<K, V> | undefined
      if (
        i > 0 &&
        (other = c[i - 1]!).keys.length < max &&
        cmp(child.keys[0]!, key) < 0
      ) {
        if (other.isShared) c[i - 1] = other = other.clone()
        other.takeFromRight(child)
        this.keys[i - 1] = other.maxKey()!
      } else if (
        (other = c[i + 1]) !== undefined &&
        other.keys.length < max &&
        cmp(child.maxKey()!, key) < 0
      ) {
        if (other.isShared) c[i + 1] = other = other.clone()
        other.takeFromLeft(child)
        this.keys[i] = c[i]!.maxKey()!
      }
    }

    const result = child.set(key, value, overwrite, tree)
    if (result === false) return false
    this.keys[i] = child.maxKey()!
    if (result === true) return true

    // The child has split and `result` is a new right child... does it fit?
    if (this.keys.length < max) {
      // yes
      this.insert(i + 1, result)
      return true
    } else {
      // no, we must split also
      const newRightSibling = this.splitOffRightSide()
      let target: BNodeInternal<K, V> = this
      if (cmp(result.maxKey()!, this.maxKey()!) > 0) {
        target = newRightSibling
        i -= this.keys.length
      }
      target.insert(i + 1, result)
      return newRightSibling