Source: bplustree.js

  1. // @flow
  3. type Tree = { t: string; k: number[]; v: any[]; n?: ?number };
  4. type CmpFn = ((a: any, b: any) => number);
  6. /** Class representing a B+ Tree. */
  7. class BPlusTree {
  8.   order: number;
  9.   debug: boolean;
  10.   cmpFn: CmpFn;
  11.   minKeys: number;
  12.   maxKeys: number;
  13.   numKeys: number;
  14.   numVals: number;
  15.   tree: Tree;
  17.   /**
  18.    * @param {Object} options
  19.    * @param {number} [options.order=6] - The tree order (or branching factor or node capacity)
  20.    * @param {boolean} [options.debug=false] - Check tree invariants after each insert / remove
  21.    * @param {string} [options.cmpFn=numericComparison] - Comparison function to use
  22.    */
  23.   constructor({
  24.       order = 6,
  25.       debug = false,
  26.       cmpFn = ((a: any, b: any): number => ((a < b) ? -1 : ((a > b) ? 1 : 0))) // eslint-disable-line
  27.     }: { order?: number; debug?: boolean; cmpFn?: CmpFn } = {}) {
  28.     this.order = order;
  29.     this.debug = debug;
  30.     this.cmpFn = cmpFn;
  32.     if (this.order % 2 !== 0 || this.order < 4) {
  33.       throw new Error('order must be even and greater than 4');
  34.     }
  35.     this.minKeys = Math.ceil(this.order / 2);
  36.     this.maxKeys = this.order - 1;
  37.     this.numKeys = 0;
  38.     this.numVals = 0;
  40.     this.tree = { t: 'leaf', k: [], v: [], n: null };
  41.   }
  43.   /**
  44.    * Get a {k1: v1, k2: v2, ...} object representing the stored data
  45.    * @param {Object} options
  46.    * @param {BPTree.tree} [options.root=this.tree] - Tree to check
  47.    * @param {boolean} [options.getKeys=false] - Instead of an object, get a list of all keys
  48.    * @param {boolean} [options.getValues=false] - Instead of an object, get a list of all values
  49.    * @param {boolean} [options.descending=false] - Get it reversed (only works if options.getKeys or options.getValues)
  50.    * @return {{keys: values}|Keys[]|Values[]}
  51.    */
  52.   repr({ root, getKeys = false, getValues = false, descending = false }:
  53.        { root?: Tree; getKeys?: boolean; getValues?: boolean; descending?: boolean } = {}): Object | any[] {
  54.     const tree = root || this.tree;
  55.     let resultArray = [];
  56.     const resultObject = {};
  58.     function walk(node: Tree) {
  59.       if (node.t === 'branch') {
  60.         const kids = node.v;
  61.         for (let i = 0, kl = kids.length; i < kl; i++) {
  62.           walk(kids[i]);
  63.         }
  64.       } else if (node.t === 'leaf') {
  65.         for (let i = 0, nkl = node.k.length; i < nkl; i++) {
  66.           if (getKeys) {
  67.             resultArray.push(node.k[i]);
  68.           } else if (getValues) {
  69.             resultArray.push(node.v[i]);
  70.           } else {
  71.             resultObject[node.k[i]] = node.v[i];
  72.           }
  73.         }
  74.       }
  75.     }
  76.     walk(tree);
  77.     // if (Array.isArra)
  78.     if (resultArray.length && resultArray[0].length) {
  79.       resultArray = Array.prototype.concat.apply([], resultArray);
  80.     }
  82.     if (resultArray.length && descending) {
  83.       return resultArray.reverse();
  84.     }
  85.     if (resultArray.length) {
  86.       return resultArray;
  87.     }
  88.     return resultObject;
  89.   }
  91.   /**
  92.    * Get all values between keys `lowerBound` and `upperBound`
  93.    * @param {number} lowerBound
  94.    * @param {number} upperBound
  95.    * @param {Object} options
  96.    * @param {boolean} [options.descending=false] - Get it reversed (only works if options.keys or options.values)
  97.    * @return {Values[]} A flat array of values, or empty array.
  98.    */
  99.   fetchRange(lowerBound: number, upperBound: number, { descending = false }: { descending: boolean } = {}): any[] {
  100.     const hi = upperBound;
  101.     let lo = lowerBound;
  103.     let result = [];
  105.     let leaf = this.fetch(lo, { getLeaf: true });
  106.     if (!leaf) { // look for a new lower bound, which is quite slow
  107.       // check if lo is bigger than highest key in tree
  108.       leaf = this.tree;
  109.       while (leaf.t === 'branch') {
  110.         leaf = leaf.v[leaf.v.length - 1];
  111.       }
  112.       if (this.cmpFn(lo, leaf.k[leaf.k.length - 1]) === 1) {
  113.         return [];
  114.       }
  115.       // ok, now this is REALLY suboptimal (and ugly)
  116.       const keys = this.repr({ getKeys: true });
  117.       for (let i = 0; i < this.numKeys; i++) {
  118.         if (this.cmpFn(keys[i], lo) === 1) {
  119.           lo = keys[i];
  120.           leaf = this.fetch(lo, { getLeaf: true });
  121.           break;
  122.         }
  123.       }
  124.     }
  126.     let index = leaf.k.indexOf(lo);
  128.     while (leaf.k[index] <= hi) {
  129.       if (this.cmpFn(leaf.k[index], hi) === 0) {
  130.         // if key at current index is upper bound, concat all vals and stop
  131.         result.push(leaf.v[index]);
  132.         break;
  133.       }
  134.       if (this.cmpFn(leaf.k[leaf.k.length - 1], hi) === 0) {
  135.         // if last key is upper bound, concat all vals and stop
  136.         result.push(leaf.v.slice(index));
  137.         break;
  138.       } else if (this.cmpFn(leaf.k[leaf.k.length - 1], hi) === -1) {
  139.         // if last key is smaller than upper bound, fetch next leaf and iterate
  140.         result.push(leaf.v.slice(index));
  141.         if (leaf.n !== null) {
  142.           leaf = this.fetch(leaf.n, { getLeaf: true });
  143.           index = 0;
  144.         } else {
  145.           break;
  146.         }
  147.       } else {
  148.         // if last key is bigger than upper bound, concat until upper bound
  149.         let i = index;
  150.         for (; leaf.k[i] <= hi; i++);
  151.         result.push(leaf.v.slice(0, i));
  152.         break;
  153.       }
  154.     }
  156.     if (Array.isArray(result[0])) {
  157.       result = Array.prototype.concat.apply([], Array.prototype.concat.apply([], result));
  158.     } else {
  159.       result = Array.prototype.concat.apply([], result);
  160.     }
  162.     if (descending) {
  163.       result.reverse();
  164.     }
  166.     return result;
  167.   }
  169.   /**
  170.    * Tree values generator. It will start generating values from a certain key
  171.    * until the end of the tree OR until `target` is found OR until `limit`
  172.    * is reached OR until there are no elements anymore.
  173.    *
  174.    * In other words:
  175.    *
  176.    * - if `target` is found before `limit`, it'll stop
  177.    * - if `limit` is reached before `target` was found, it'll stop
  178.    * - `target` and `limit` are both optional: use none of them, one of them, or both
  179.    * - `keyNotFound` is optional, it lets you decide which key to prefer when the key is not found
  180.    *
  181.    * @param {Object} options
  182.    * @param {Key} [options.key] - Key at which to start generating.
  183.    * @param {boolean} [options.target] - Stop generating when this value is found.
  184.    * @param {number} [options.limit] - Generate at max this number of values.
  185.    * @param {string} [options.keyNotFound] - See `notFound` of `BPlusTree.fetch`
  186.    * @return {Generator} - e.g. `{ value: { k: 6, v: ['f', 'g'] }, done: false }`
  187.    */
  188.   * values({ key, target, limit = Infinity, keyNotFound }:
  189.            { key: any; target: any; limit: number; keyNotFound: ?string } = {}): Generator<any, ?Object, void> {
  190.     let returned = 0;
  191.     let leaf;
  192.     let _key = key;
  193.     let _keyNotFound = keyNotFound;
  194.     if (typeof _key === 'undefined') {
  195.       _key = -Infinity;
  196.       _keyNotFound = 'right';
  197.     }
  198.     leaf = this.fetch(_key, { getLeaf: true, notFound: _keyNotFound });
  200.     if (!leaf) {
  201.       return undefined;
  202.     }
  204.     while (true) { // eslint-disable-line no-constant-condition
  205.       let index = leaf.k.indexOf(_key);
  206.       if (index === -1) {
  207.         index = 0;
  208.       }
  209.       for (let i = index; i < leaf.v.length; i++) {
  210.         const length = leaf.v[i].length;
  211.         returned += length;
  212.         if (returned >= limit) {
  213.           const remainder = length - (returned - limit);
  214.           if (remainder >= 0) {
  215.             return { k: leaf.k[i], v: leaf.v[i].slice(0, remainder) };
  216.           }
  217.         }
  218.         if (target === leaf.v[i][0]) {
  219.           return { k: leaf.k[i], v: leaf.v[i] };
  220.         }
  221.         if (leaf.n === null && i + 1 === leaf.v.length) {
  222.           return { k: leaf.k[i], v: leaf.v[i] };
  223.         }
  224.         yield { k: leaf.k[i], v: leaf.v[i] };
  225.       }
  226.       if (leaf.n !== null) {
  227.         leaf = this.fetch(leaf.n, { getLeaf: true, notFound: _keyNotFound });
  228.       } else {
  229.         break;
  230.       }
  231.     }
  232.     return undefined;
  233.   }
  235.   /**
  236.    * Get tree depth (or height)
  237.    * @param {Object} options
  238.    * @param {BPTree.tree} [options.root=this.tree] - Tree to use
  239.    * @return {number} Computed depth
  240.    */
  241.   depth({ root }: { root: Tree } = {}): number {
  242.     let tree = root || this.tree;
  243.     let d = 0;
  244.     while (tree.t === 'branch') {
  245.       tree = tree.v[0];
  246.       d += 1;
  247.     }
  248.     return d;
  249.   }
  251.   /**
  252.    * Check tree invariants
  253.    * @param {Object} options
  254.    * @param {BPTree.tree} [options.root=this.tree] - Tree to check
  255.    * @return {boolean} Returns `true` or throws an `Error()`
  256.    */
  257.   check({ root }: { root: Tree } = {}): boolean {
  258.     const _root = root || this.tree;
  259.     const depth = this.depth({ root: _root });
  261.     function assert(expr: boolean, msg: string) {
  262.       if (!expr) {
  263.         throw new Error(msg);
  264.       }
  265.     }
  267.     function checking(self: BPlusTree, currentNode: Tree, currentDepth: number, lo: any[], hi: any[]): boolean {
  268.       const node = currentNode;
  269.       const keysLength = node.k.length;
  271.       assert(keysLength <= self.maxKeys, 'Overflowed node');
  273.       for (let i = 0, kl = keysLength - 1; i < kl; i++) {
  274.         assert(self.cmpFn(node.k[i], node.k[i + 1]) === -1, 'Disordered or duplicate key');
  275.       }
  277.       assert(lo.length === 0 || self.cmpFn(lo[0], node.k[0]) < 1, 'lo error');
  278.       assert(hi.length === 0 || self.cmpFn(node.k[keysLength - 1], hi[0]) === -1, 'hi error');
  280.       if (node.t === 'branch') {
  281.         const kids = node.v;
  282.         const kidsLength = kids.length;
  284.         if (currentDepth === 0) {
  285.           assert(kidsLength >= 2, 'Underpopulated root');
  286.         } else {
  287.           assert(kidsLength >= self.minKeys, 'Underpopulated branch');
  288.         }
  290.         assert(keysLength === kidsLength - 1, 'keys and kids don\'t correspond');
  292.         for (let i = 0; i < kidsLength; i++) {
  293.           const newLo = (i === 0 ? lo : [node.k[i - 1]]);
  294.           const newHi = (i === keysLength ? hi : [node.k[i]]);
  295.           checking(self, kids[i], currentDepth + 1, newLo, newHi);
  296.         }
  297.       } else if (node.t === 'leaf') {
  298.         const v = node.v;
  299.         assert(currentDepth === depth, 'Leaves at different depths');
  300.         assert(keysLength === v.length, 'keys and values don\'t correspond');
  301.         if (currentDepth > 0) {
  302.           assert(v.length >= self.minKeys, 'Underpopulated leaf');
  303.         }
  304.       } else {
  305.         assert(false, 'Bad type');
  306.       }
  307.       return true;
  308.     }
  310.     return checking(this, _root, 0, [], []);
  311.   }
  313.   /**
  314.    * Fetch the value(s) stored at `key`.
  315.    *
  316.    * - `getLeaf` returns the whole leaf
  317.    * - `getPath` returns the path from the root to this leaf
  318.    * - when defined, `notFound` can be either 'left' or 'right', it controls which key to return when it wasn't found
  319.    *
  320.    * @param {Key} key
  321.    * @param {Object} options
  322.    * @param {BPTree.tree} [options.root=this.tree] - Tree to search in
  323.    * @param {boolean} [options.getLeaf=false] - Return the leaf containing the value(s)
  324.    * @param {boolean} [options.getPath=false] - Return {val: value(s), leaf: leaf, path: pathFromRootToLeaf}
  325.    * @param {string} [options.notFound] - either 'left' or 'right' - Return what was found left or right from key which doesn't exist
  326.    * @return {Value|Value[]|Leaf|Object|Boolean}
  327.    */
  328.   fetch(key: any, { root, getLeaf = false, getPath = false, notFound }:
  329.                   { root?: Tree; getLeaf?: boolean; getPath?: boolean; notFound?: ?string } = {}): any {
  330.     let node = root || this.tree;
  332.     let index;
  333.     const path = [];
  334.     while (node.t === 'branch') {
  335.       index = 0;
  336.       let found = false;
  337.       for (let kl = node.k.length; index < kl; index++) {
  338.         if (this.cmpFn(node.k[index], key) === 1) {
  339.           found = true;
  340.           break;
  341.         }
  342.       }
  343.       if (!found) {
  344.         index = node.v.length - 1;
  345.       }
  346.       node = node.v[index];
  347.       path.push(index);
  348.     }
  350.     for (let j = 0, kl = node.k.length; j < kl; j++) {
  351.       const cmp = this.cmpFn(key, node.k[j]);
  352.       if (cmp === 0) {
  353.         const val = node.v[j];
  354.         if (getPath) {
  355.           return { val, leaf: node, path };
  356.         }
  357.         if (getLeaf) {
  358.           return node;
  359.         }
  360.         return val;
  361.       } else if (notFound) {
  362.         if (notFound === 'right' && !(cmp < 0)) {
  363.           return this.fetch(node.n, { root, getLeaf, getPath });
  364.         }
  365.         node = this._get(path);
  366.         let val;
  367.         if (notFound === 'left' && !(cmp < 0)) {
  368.           val = node.v[node.v.length - 1];
  369.         } else if (notFound === 'right') {
  370.           val = node.v[0];
  371.         }
  372.         if (val) {
  373.           if (getPath) {
  374.             return { val, leaf: node, path };
  375.           }
  376.           if (getLeaf) {
  377.             return node;
  378.           }
  379.           return val;
  380.         }
  381.       } else if (this.cmpFn(node.k[j], key) === 1) {
  382.         break; // just to finish quicker; not needed for correctness
  383.       }
  384.     }
  385.     return false;
  386.   }
  388.   _doStore(key: any, value: any) {
  389.     const path = [];
  390.     let node = this.tree;
  392.     // Find the leaf node for key, and the path down to it.
  393.     while (node.t === 'branch') {
  394.       let i = 0;
  395.       let found = false;
  396.       for (let nkl = node.k.length; i < nkl; i++) {
  397.         if (this.cmpFn(key, node.k[i]) === -1) {
  398.           found = true;
  399.           break;
  400.         }
  401.       }
  402.       if (!found) {
  403.         i = node.k.length;
  404.       }
  405.       path.push({ t: node.t, k: node.k, v: node.v, i });
  406.       node = node.v[i];
  407.     }
  409.     // Find the index for key in the leaf node.
  410.     let i = 0;
  411.     let found = false;
  412.     const nkl = node.k.length;
  413.     for (; i < nkl; i++) {
  414.       if (this.cmpFn(key, node.k[i]) === 0) {
  415.         // key isn't actually new, so the structure goes unchanged.
  416.         node.v[i].push(value);
  417.         return;
  418.       } else if (this.cmpFn(key, node.k[i]) === -1) {
  419.         found = true;
  420.         break;
  421.       }
  422.     }
  423.     if (!found) {
  424.       i = nkl;
  425.     }
  427.     // We'll have to insert it in the leaf at i. If there's room, just do it:
  428.     node.k.splice(i, 0, key);
  429.     node.v.splice(i, 0, [value]);
  430.     this.numKeys += 1;
  431.     this.numVals += 1;
  433.     if (node.k.length < this.order) {
  434.       return;
  435.     }
  437.     // Otherwise split the now-overpacked leaf...
  438.     const mid = Math.floor(this.order / 2);
  439.     let tween = node.k[mid];
  440.     let left = { t: 'leaf', k: node.k.slice(0, mid), v: node.v.slice(0, mid), n: node.k[mid] };
  441.     let right = { t: 'leaf', k: node.k.slice(mid), v: node.v.slice(mid), n: node.n };
  443.     // ...and propagate the split back up the path.
  444.     while (path.length) {
  445.       node = path.pop();
  446.       node.k.splice(node.i, 0, tween);
  447.       node.v[node.i] = left;
  448.       node.v.splice(node.i + 1, 0, right);
  449.       if (node.k.length < this.maxKeys) {
  450.         return;
  451.       }
  452.       tween = node.k[mid - 1];
  453.       left = { t: 'branch', k: node.k.slice(0, mid - 1), v: node.v.slice(0, mid), n: node.k[mid] };
  454.       right = { t: 'branch', k: node.k.slice(mid), v: node.v.slice(mid), n: null };
  455.     }
  457.     // If we got here, we need a new root.
  458.     this.tree = { t: 'branch', k: [tween], v: [left, right], n: null };
  459.   }
  461.   /**
  462.    * Insert value at key key
  463.    * @param {Key} key
  464.    * @param {Value} value
  465.    * @return {boolean} true
  466.    */
  467.   store(key: any, value: any): boolean {
  468.     this._doStore(key, value);
  469.     if (this.debug) {
  470.       this.check();
  471.     }
  472.     return true;
  473.   }
  475.   _get(path: number[], node?: Tree): Object {
  476.     let object = node || this.tree;
  477.     let index = 0;
  478.     const length = path.length;
  480.     while (object && index < length) {
  481.       object = object.v[path[index++]];
  482.     }
  483.     return object;
  484.   }
  486.   _genGetKeyFn(driller: (tree: Tree) => any, depth: number): (tree: Tree) => any {
  487.     if (depth === 0) {
  488.       return (o: Tree): any => driller(o).k[0];
  489.     }
  490.     return this._genGetKeyFn((o: Tree): any => driller(o).v[0], depth - 1);
  491.   }
  493.   _getFirstKeyFn(depth: number): (tree: Tree) => any {
  494.     const fn = [
  495.       (o: Tree): any => o,
  496.       (o: Tree): any => o.v[0],
  497.       (o: Tree): any => o.v[0].v[0],
  498.       (o: Tree): any => o.v[0].v[0].v[0],
  499.       (o: Tree): any => o.v[0].v[0].v[0].v[0],
  500.       (o: Tree): any => o.v[0].v[0].v[0].v[0].v[0],
  501.       (o: Tree): any => o.v[0].v[0].v[0].v[0].v[0].v[0],
  502.       (o: Tree): any => o.v[0].v[0].v[0].v[0].v[0].v[0].v[0],
  503.       (o: Tree): any => o.v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0],
  504.       (o: Tree): any => o.v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0],
  505.       (o: Tree): any => o.v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0],
  506.       (o: Tree): any => o.v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0],
  507.       (o: Tree): any => o.v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0],
  508.       (o: Tree): any => o.v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0],
  509.       (o: Tree): any => o.v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0],
  510.       (o: Tree): any => o.v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0],
  511.       (o: Tree): any => o.v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0],
  512.     ];
  513.     const length = fn.length;
  514.     return (depth < length - 1 && ((o: Tree): any => fn[depth](o).k[0])) || this._genGetKeyFn(fn[length - 1], (depth - length) + 1);
  515.   }
  517.   _fixKeys(): any {
  518.     const result = [];
  519.     function walk(node: Tree, depth: number, path: any) {
  520.       if (node.t === 'branch') {
  521.         const kids = node.v;
  522.         for (let i = 0, kl = kids.length; i < kl; i++) {
  523.           if (kids[i].t === 'branch') {
  524.             const newPath = path.slice(0, depth).concat([i]);
  525.             result.push(newPath);
  526.             walk(kids[i], depth + 1, newPath);
  527.           }
  528.         }
  529.       }
  530.     }
  531.     walk(this.tree, 0, []);
  532.     result.sort((a, b) => (a.length > b.length) ? -1 : ((a.length < b.length) ? 1 : 0)); // eslint-disable-line
  534.     result.forEach((path: any) => {
  535.       const sub = this._get(path);
  536.       sub.k = sub.v.slice(1).map(this._getFirstKeyFn(result[0].length - path.length));
  537.     });
  539.     if (this.tree.t !== 'leaf') {
  540.       this.tree.k = this.tree.v.slice(1).map(this._getFirstKeyFn(result.length ? result[0].length : 0));
  541.     }
  543.     return result;
  544.   }
  546.   _removeKey(key: any, val: any): boolean | Object {
  547.     const fetched = this.fetch(key, { getPath: true });
  549.     if (!fetched) {
  550.       return false;
  551.     }
  553.     const keyIndex = fetched.leaf.k.indexOf(key);
  554.     const valIndex = fetched.leaf.v[keyIndex].indexOf(val);
  556.     // key does not contain val
  557.     if (val !== undefined && valIndex === -1) {
  558.       return false;
  559.     }
  561.     const valCount = fetched.leaf.v[keyIndex].length;
  562.     let removed;
  564.     // we only have one val, remove it together with its key
  565.     if (valCount === 1 && keyIndex !== -1) {
  566.       fetched.leaf.k.splice(keyIndex, 1);
  567.       removed = fetched.leaf.v[keyIndex][0];
  568.       fetched.leaf.v.splice(keyIndex, 1);
  569.       this.numKeys--;
  570.     } else if (val !== undefined) {
  571.       // key contains val, but we have other vals, only remove this val
  572.       removed = fetched.leaf.v[keyIndex][valIndex];
  573.       fetched.leaf.v[keyIndex].splice(valIndex, 1);
  574.     } else {
  575.       // key has several vals, we don't remove anything
  576.       return false;
  577.     }
  579.     // we lost one val
  580.     this.numVals--;
  581.     return { val: removed, leaf: fetched.leaf, path: fetched.path };
  582.   }
  584.   _doRemove(key: any, val: any): boolean | any {
  585.     // get leaf for key, remove key from leaf
  586.     const removed = this._removeKey(key, val);
  587.     if (typeof removed === 'boolean') {
  588.       return false;
  589.     }
  590.     const leaf = removed.leaf;
  591.     const path = removed.path;
  593.     // if key in branch.k, replace it with new smallest key in leaf
  594.     const parentPath = path.slice(0, path.length - 1);
  595.     let parent = this._get(parentPath);
  596.     let index = parent.k.indexOf(key);
  598.     // if leaf is at least half full, terminate
  599.     if (leaf.v.length >= this.minKeys) {
  600.       return removed.val;
  601.     }
  603.     const leafIndex = path[path.length - 1];
  604.     // else borrow
  606.     // if rightSibling is more than half full, borrow leftmost value
  607.     let canBorrowRight = false;
  608.     if (leafIndex < parent.v.length - 1) {
  609.       const rightSibling = parent.v[leafIndex + 1];
  610.       if (rightSibling && rightSibling.k.length > this.minKeys) {
  611.         // can borrow from right because it is more than half full
  612.         canBorrowRight = true;
  613.         const keyToBorrow = rightSibling.k.shift();
  614.         const valBorrowed = rightSibling.v.shift();
  615.         leaf.k.push(keyToBorrow);
  616.         leaf.v.push(valBorrowed);
  617.         leaf.n = rightSibling.k[0];
  618.         parent.k = parent.v.slice(1).map((o: Object): any => o.k[0]);
  619.         parent.v[leafIndex] = leaf;
  620.         parent.v[leafIndex + 1] = rightSibling;
  621.       }
  622.     }
  624.     // if leftSibling is more than half full, borrow rightmost value
  625.     let canBorrowLeft = false;
  626.     if (leafIndex > 0) {
  627.       const leftSibling = parent.v[leafIndex - 1];
  628.       if (leftSibling && leftSibling.k.length > this.minKeys) {
  629.         // can borrow from left because it is more than half full
  630.         canBorrowLeft = true;
  631.         const keyToBorrow = leftSibling.k.pop();
  632.         const valBorrowed = leftSibling.v.pop();
  633.         leaf.k.unshift(keyToBorrow);
  634.         leaf.v.unshift(valBorrowed);
  635.         parent.k = parent.v.slice(1).map((o: Object): any => o.k[0]);
  636.         parent.v[leafIndex] = leaf;
  637.         parent.v[leafIndex - 1] = leftSibling;
  638.       }
  639.     }
  641.     if (!canBorrowRight && !canBorrowLeft) {
  642.       let again = true;
  643.       let lastIndex = -1;
  644.       while (again) {
  645.         parent = this._get(path);
  646.         lastIndex = index;
  647.         if (path.length) {
  648.           index = path.pop();
  649.         } else {
  650.           index = 0;
  651.           again = false;
  652.         }
  654.         const mergeNeeded = parent.t !== 'leaf' && parent.v[lastIndex].k.length < this.minKeys;
  656.         if (mergeNeeded) {
  657.           const leftExists = parent.v[lastIndex - 1];
  658.           let leftSum = leftExists && parent.v[lastIndex - 1].k.length + parent.v[lastIndex].k.length;
  659.           leftSum += parent.v[lastIndex].t === 'leaf' ? 0 : 1;
  660.           const roomOnLeft = leftExists && leftSum && leftSum <= this.maxKeys;
  662.           const rightExists = parent.v[lastIndex + 1];
  663.           let rightSum = rightExists && parent.v[lastIndex + 1].k.length + parent.v[lastIndex].k.length;
  664.           rightSum += parent.v[lastIndex].t === 'leaf' ? 0 : 1;
  665.           const roomOnRight = rightExists && rightSum && rightSum <= this.maxKeys;
  667.           let splitIndex = false;
  669.           if ((leftExists && roomOnLeft) || (leftExists && !roomOnRight)) {
  670.             if (!roomOnLeft) {
  671.               splitIndex = lastIndex - 1;
  672.             }
  673.             // merging with left, deleting sibling
  674.             // node becomes (sibling merged with node)
  675.             parent.v[lastIndex] = BPlusTree._mergeLeft(parent.v[lastIndex - 1], parent.v[lastIndex]);
  676.             parent.v.splice(lastIndex, 1); // delete now merged sibling
  677.           } else if (rightExists) {
  678.             if (!roomOnRight) {
  679.               splitIndex = lastIndex;
  680.             }
  681.             // merging with right, deleting sibling
  682.             // node becomes (node merged with sibling)
  683.             parent.v[lastIndex] = BPlusTree._mergeRight(parent.v[lastIndex + 1], parent.v[lastIndex]);
  684.             parent.v.splice(lastIndex + 1, 1); // delete now merged sibling
  685.           }
  686.           if (splitIndex !== false) {
  687.             const branchToSplit = parent.v[splitIndex];
  688.             const mid = this.minKeys;
  689.             const leftContent = branchToSplit.v.slice(0, mid);
  690.             const rightContent = branchToSplit.v.slice(mid);
  691.             const childType = parent.t;
  692.             const left = { t: childType, k: leftContent.slice(1).map((o: Object): any => o.k[0]), v: leftContent };
  693.             const right = { t: childType, k: rightContent.slice(1).map((o: Object): any => o.k[0]), v: rightContent };
  694.             parent.v.splice(splitIndex, 1, left, right);
  695.           }
  696.         }
  697.       }
  699.       if (this.tree.v.length < 2 && this.tree.t !== 'leaf') {
  700.         // underpopulated root
  701.         if (this.tree.v[index].v.length > this.maxKeys) {
  702.           // need to split
  703.           const mid = this.minKeys;
  704.           const leftContent = this.tree.v[index].v.slice(0, mid);
  705.           const rightContent = this.tree.v[index].v.slice(mid);
  706.           const left = { t: 'branch', k: [leftContent[leftContent.length - 1].k[0]], v: leftContent };
  707.           const right = { t: 'branch', k: [rightContent[rightContent.length - 1].k[0]], v: rightContent };
  708.           this.tree.t = 'branch';
  709.           this.tree.n = null;
  710.           this.tree.k = [right.v[0].k[0]];
  711.           this.tree.v = [left, right];
  712.         } else {
  713.           // need to hoist
  714.           this.tree.t = 'leaf';
  715.           this.tree = this.tree.v[index];
  716.           const slice = this.tree.v.slice(1);
  717.           if (slice.length && slice[0].t) {
  718.             this.tree.k = slice.map((o: Object): any => o.k[0]);
  719.           }
  720.         }
  721.       }
  723.       this._fixKeys();
  724.     }
  725.     return removed.val;
  726.   }
  728.   /**
  729.    * Remove value from key key, or remove key and its value if key only has one value
  730.    * @param {Key} key
  731.    * @param {Value?} value
  732.    * @return {Value} The removed value
  733.    */
  734.   remove(key: any, value: any): any {
  735.     const removed = this._doRemove(key, value);
  736.     if (this.debug) {
  737.       this.check();
  738.     }
  739.     return removed;
  740.   }
  742.   static _mergeLeft(dest: Tree, src: Tree): Tree {
  743.     const node = dest;
  744.     node.k = node.k.concat(src.k);
  745.     node.v = node.v.concat(src.v);
  746.     node.n = src.n;
  747.     return node;
  748.   }
  750.   static _mergeRight(dest: Tree, _src: Tree): Tree {
  751.     const node = dest;
  752.     const src = _src;
  753.     if (src.t !== 'leaf') {
  754.       src.v[src.v.length - 1].n = node.v[0].k[0];
  755.     }
  756.     node.k = src.k.concat(node.k);
  757.     node.v = src.v.concat(node.v);
  758.     return node;
  759.   }
  760. }
  762. module.exports = BPlusTree;