		@@ -1,11 +0,3 @@
		'use strict';

		var _createClass = function () { function defineProperties(target, props) { for (var i = 0; i < props.length; i++) { var descriptor = props[i]; descriptor.enumerable = descriptor.enumerable \|\| false; descriptor.configurable = true; if ("value" in descriptor) descriptor.writable = true; Object.defineProperty(target, descriptor.key, descriptor); } } return function (Constructor, protoProps, staticProps) { if (protoProps) defineProperties(Constructor.prototype, protoProps); if (staticProps) defineProperties(Constructor, staticProps); return Constructor; }; }();

		require('regenerator-runtime/runtime');

		function _classCallCheck(instance, Constructor) { if (!(instance instanceof Constructor)) { throw new TypeError("Cannot call a class as a function"); } }

		/** Class representing a B+ Tree. */
		var BPlusTree = function () {
		class BPlusTree {
		/**
		@@ -17,16 +9,8 @@ * @param {Object} options
		*/
		function BPlusTree() {
		var _ref = arguments.length > 0 && arguments[0] !== undefined ? arguments[0] : {},
		_ref$order = _ref.order,
		order = _ref$order === undefined ? 6 : _ref$order,
		_ref$debug = _ref.debug,
		debug = _ref$debug === undefined ? false : _ref$debug,
		_ref$cmpFn = _ref.cmpFn,
		cmpFn = _ref$cmpFn === undefined ? function (a, b) {
		return a < b ? -1 : a > b ? 1 : 0;
		} : _ref$cmpFn;
		constructor({
		order = 6,
		debug = false,
		cmpFn = (a, b) => a < b ? -1 : a > b ? 1 : 0 // eslint-disable-line

		_classCallCheck(this, BPlusTree);

		// eslint-disable-line
		} = {}) {
		this.order = order;
		@@ -39,2 +23,3 @@ this.debug = debug;
		}

		this.minKeys = Math.ceil(this.order / 2);
		@@ -44,6 +29,9 @@ this.maxKeys = this.order - 1;
		this.numVals = 0;

		this.tree = { t: 'leaf', k: [], v: [], n: null };
		this.tree = {
		t: 'leaf',
		k: [],
		v: [],
		n: null
		};
		}

		/**
		@@ -60,477 +48,452 @@ * Get a {k1: v1, k2: v2, ...} object representing the stored data

		_createClass(BPlusTree, [{
		key: 'repr',
		value: function repr() {
		var _ref2 = arguments.length > 0 && arguments[0] !== undefined ? arguments[0] : {},
		_ref2$root = _ref2.root,
		root = _ref2$root === undefined ? this.tree : _ref2$root,
		_ref2$getKeys = _ref2.getKeys,
		getKeys = _ref2$getKeys === undefined ? false : _ref2$getKeys,
		_ref2$getValues = _ref2.getValues,
		getValues = _ref2$getValues === undefined ? false : _ref2$getValues,
		_ref2$descending = _ref2.descending,
		descending = _ref2$descending === undefined ? false : _ref2$descending;
		repr({
		root,
		getKeys = false,
		getValues = false,
		descending = false
		} = {}) {
		const tree = root \|\| this.tree;
		let resultArray = [];
		const resultObject = {};

		var tree = root;
		var result = getKeys \|\| getValues ? [] : {};
		function walk(node) {
		if (node.t === 'branch') {
		var kids = node.v;
		for (var i = 0, kl = kids.length; i < kl; i++) {
		walk(kids[i]);
		function walk(node) {
		if (node.t === 'branch') {
		const kids = node.v;

		for (let i = 0, kl = kids.length; i < kl; i++) {
		walk(kids[i]);
		}
		} else if (node.t === 'leaf') {
		for (let i = 0, nkl = node.k.length; i < nkl; i++) {
		if (getKeys) {
		resultArray.push(node.k[i]);
		} else if (getValues) {
		resultArray.push(node.v[i]);
		} else {
		resultObject[node.k[i]] = node.v[i];
		}
		} else if (node.t === 'leaf') {
		for (var _i = 0, nkl = node.k.length; _i < nkl; _i++) {
		if (getKeys) {
		result.push(node.k[_i]);
		} else if (getValues) {
		result.push(node.v[_i]);
		} else {
		result[node.k[_i]] = node.v[_i];
		}
		}
		}
		}
		walk(tree);
		var out = result.length && Array.isArray(result[0]) ? Array.prototype.concat.apply([], result) : result;
		}

		if ((getKeys \|\| getValues) && descending) {
		return out.reverse();
		}
		return out;
		walk(tree); // if (Array.isArra)

		if (resultArray.length && resultArray[0].length) {
		resultArray = Array.prototype.concat.apply([], resultArray);
		}

		/**
		* Get all values between keys `lowerBound` and `upperBound`
		* @param {number} lowerBound
		* @param {number} upperBound
		* @param {Object} options
		* @param {boolean} [options.descending=false] - Get it reversed (only works if options.keys or options.values)
		* @return {Values[]} A flat array of values, or empty array.
		*/
		if (resultArray.length && descending) {
		return resultArray.reverse();
		}

		}, {
		key: 'fetchRange',
		value: function fetchRange(lowerBound, upperBound) {
		var _ref3 = arguments.length > 2 && arguments[2] !== undefined ? arguments[2] : {},
		_ref3$descending = _ref3.descending,
		descending = _ref3$descending === undefined ? false : _ref3$descending;
		if (resultArray.length) {
		return resultArray;
		}

		var hi = upperBound;
		var lo = lowerBound;
		return resultObject;
		}
		/**
		* Get all values between keys `lowerBound` and `upperBound`
		* @param {number} lowerBound
		* @param {number} upperBound
		* @param {Object} options
		* @param {boolean} [options.descending=false] - Get it reversed (only works if options.keys or options.values)
		* @return {Values[]} A flat array of values, or empty array.
		*/

		var result = [];

		var leaf = this.fetch(lo, { getLeaf: true });
		if (!leaf) {
		// look for a new lower bound, which is quite slow
		// check if lo is bigger than highest key in tree
		leaf = this.tree;
		while (leaf.t === 'branch') {
		leaf = leaf.v[leaf.v.length - 1];
		}
		if (this.cmpFn(lo, leaf.k[leaf.k.length - 1]) === 1) {
		return [];
		}
		// ok, now this is REALLY suboptimal (and ugly)
		var keys = this.repr({ getKeys: true });
		for (var i = 0; i < this.numKeys; i++) {
		if (this.cmpFn(keys[i], lo) === 1) {
		lo = keys[i];
		leaf = this.fetch(lo, { getLeaf: true });
		break;
		}
		}
		fetchRange(lowerBound, upperBound, {
		descending = false
		} = {}) {
		const hi = upperBound;
		let lo = lowerBound;
		let result = [];
		let leaf = this.fetch(lo, {
		getLeaf: true
		});

		if (!leaf) {
		// look for a new lower bound, which is quite slow
		// check if lo is bigger than highest key in tree
		leaf = this.tree;

		while (leaf.t === 'branch') {
		leaf = leaf.v[leaf.v.length - 1];
		}

		var index = leaf.k.indexOf(lo);
		if (this.cmpFn(lo, leaf.k[leaf.k.length - 1]) === 1) {
		return [];
		} // ok, now this is REALLY suboptimal (and ugly)

		while (leaf.k[index] <= hi) {
		if (this.cmpFn(leaf.k[index], hi) === 0) {
		// if key at current index is upper bound, concat all vals and stop
		result.push(leaf.v[index]);

		const keys = this.repr({
		getKeys: true
		});

		for (let i = 0; i < this.numKeys; i++) {
		if (this.cmpFn(keys[i], lo) === 1) {
		lo = keys[i];
		leaf = this.fetch(lo, {
		getLeaf: true
		});
		break;
		}
		if (this.cmpFn(leaf.k[leaf.k.length - 1], hi) === 0) {
		// if last key is upper bound, concat all vals and stop
		result.push(leaf.v.slice(index));
		break;
		} else if (this.cmpFn(leaf.k[leaf.k.length - 1], hi) === -1) {
		// if last key is smaller than upper bound, fetch next leaf and iterate
		result.push(leaf.v.slice(index));
		if (leaf.n !== null) {
		leaf = this.fetch(leaf.n, { getLeaf: true });
		index = 0;
		} else {
		break;
		}
		} else {
		// if last key is bigger than upper bound, concat until upper bound
		var _i2 = index;
		for (; leaf.k[_i2] <= hi; _i2++) {}
		result.push(leaf.v.slice(0, _i2));
		break;
		}
		}
		}

		if (Array.isArray(result[0])) {
		result = Array.prototype.concat.apply([], Array.prototype.concat.apply([], result));
		} else {
		result = Array.prototype.concat.apply([], result);
		}
		let index = leaf.k.indexOf(lo);

		if (descending) {
		result.reverse();
		while (leaf.k[index] <= hi) {
		if (this.cmpFn(leaf.k[index], hi) === 0) {
		// if key at current index is upper bound, concat all vals and stop
		result.push(leaf.v[index]);
		break;
		}

		return result;
		}
		if (this.cmpFn(leaf.k[leaf.k.length - 1], hi) === 0) {
		// if last key is upper bound, concat all vals and stop
		result.push(leaf.v.slice(index));
		break;
		} else if (this.cmpFn(leaf.k[leaf.k.length - 1], hi) === -1) {
		// if last key is smaller than upper bound, fetch next leaf and iterate
		result.push(leaf.v.slice(index));

		/**
		* Tree values generator. It will start generating values from a certain key
		* until the end of the tree OR until `target` is found OR until `limit`
		* is reached OR until there are no elements anymore.
		*
		* In other words:
		*
		* - if `target` is found before `limit`, it'll stop
		* - if `limit` is reached before `target` was found, it'll stop
		* - `target` and `limit` are both optional: use none of them, one of them, or both
		* - `keyNotFound` is optional, it lets you decide which key to prefer when the key is not found
		*
		* @param {Object} options
		* @param {Key} [options.key] - Key at which to start generating.
		* @param {boolean} [options.target] - Stop generating when this value is found.
		* @param {number} [options.limit] - Generate at max this number of values.
		* @param {string} [options.keyNotFound] - See `notFound` of `BPlusTree.fetch`
		* @return {Generator} - e.g. `{ value: { k: 6, v: ['f', 'g'] }, done: false }`
		*/
		if (leaf.n !== null) {
		leaf = this.fetch(leaf.n, {
		getLeaf: true
		});
		index = 0;
		} else {
		break;
		}
		} else {
		// if last key is bigger than upper bound, concat until upper bound
		let i = index;

		}, {
		key: 'values',
		value: regeneratorRuntime.mark(function values() {
		var _ref4 = arguments.length > 0 && arguments[0] !== undefined ? arguments[0] : {},
		key = _ref4.key,
		target = _ref4.target,
		_ref4$limit = _ref4.limit,
		limit = _ref4$limit === undefined ? Infinity : _ref4$limit,
		keyNotFound = _ref4.keyNotFound;
		for (; leaf.k[i] <= hi; i++);

		var returned, leaf, index, i, length, remainder;
		return regeneratorRuntime.wrap(function values$(_context) {
		while (1) {
		switch (_context.prev = _context.next) {
		case 0:
		returned = 0;
		leaf = void 0;
		result.push(leaf.v.slice(0, i));
		break;
		}
		}

		if (typeof key === 'undefined') {
		key = -Infinity;
		keyNotFound = 'right';
		}
		leaf = this.fetch(key, { getLeaf: true, notFound: keyNotFound });
		if (Array.isArray(result[0])) {
		result = Array.prototype.concat.apply([], Array.prototype.concat.apply([], result));
		} else {
		result = Array.prototype.concat.apply([], result);
		}

		if (leaf) {
		_context.next = 6;
		break;
		}
		if (descending) {
		result.reverse();
		}

		return _context.abrupt('return', false);
		return result;
		}
		/**
		* Tree values generator. It will start generating values from a certain key
		* until the end of the tree OR until `target` is found OR until `limit`
		* is reached OR until there are no elements anymore.
		*
		* In other words:
		*
		* - if `target` is found before `limit`, it'll stop
		* - if `limit` is reached before `target` was found, it'll stop
		* - `target` and `limit` are both optional: use none of them, one of them, or both
		* - `keyNotFound` is optional, it lets you decide which key to prefer when the key is not found
		*
		* @param {Object} options
		* @param {Key} [options.key] - Key at which to start generating.
		* @param {boolean} [options.target] - Stop generating when this value is found.
		* @param {number} [options.limit] - Generate at max this number of values.
		* @param {string} [options.keyNotFound] - See `notFound` of `BPlusTree.fetch`
		* @return {Generator} - e.g. `{ value: { k: 6, v: ['f', 'g'] }, done: false }`
		*/

		case 6:
		if (!true) {
		_context.next = 33;
		break;
		}

		index = leaf.k.indexOf(key);
		*values({
		key,
		target,
		limit = Infinity,
		keyNotFound
		} = {}) {
		let returned = 0;
		let leaf;
		let _key = key;
		let _keyNotFound = keyNotFound;

		if (index === -1) {
		index = 0;
		}
		i = index;
		if (typeof _key === 'undefined') {
		_key = -Infinity;
		_keyNotFound = 'right';
		}

		case 10:
		if (!(i < leaf.v.length)) {
		_context.next = 26;
		break;
		}
		leaf = this.fetch(_key, {
		getLeaf: true,
		notFound: _keyNotFound
		});

		length = leaf.v[i].length;
		if (!leaf) {
		return undefined;
		}

		returned += length;
		while (true) {
		// eslint-disable-line no-constant-condition
		let index = leaf.k.indexOf(_key);

		if (!(returned >= limit)) {
		_context.next = 17;
		break;
		}
		if (index === -1) {
		index = 0;
		}

		remainder = length - (returned - limit);
		for (let i = index; i < leaf.v.length; i++) {
		const length = leaf.v[i].length;
		returned += length;

		if (!(remainder >= 0)) {
		_context.next = 17;
		break;
		}
		if (returned >= limit) {
		const remainder = length - (returned - limit);

		return _context.abrupt('return', { k: leaf.k[i], v: leaf.v[i].slice(0, remainder) });
		if (remainder >= 0) {
		return {
		k: leaf.k[i],
		v: leaf.v[i].slice(0, remainder)
		};
		}
		}

		case 17:
		if (!(target === leaf.v[i][0])) {
		_context.next = 19;
		break;
		}
		if (target === leaf.v[i][0]) {
		return {
		k: leaf.k[i],
		v: leaf.v[i]
		};
		}

		return _context.abrupt('return', { k: leaf.k[i], v: leaf.v[i] });
		if (leaf.n === null && i + 1 === leaf.v.length) {
		return {
		k: leaf.k[i],
		v: leaf.v[i]
		};
		}

		case 19:
		if (!(leaf.n === null && i + 1 === leaf.v.length)) {
		_context.next = 21;
		break;
		}
		yield {
		k: leaf.k[i],
		v: leaf.v[i]
		};
		}

		return _context.abrupt('return', { k: leaf.k[i], v: leaf.v[i] });
		if (leaf.n !== null) {
		leaf = this.fetch(leaf.n, {
		getLeaf: true,
		notFound: _keyNotFound
		});
		} else {
		break;
		}
		}

		case 21:
		_context.next = 23;
		return { k: leaf.k[i], v: leaf.v[i] };
		return undefined;
		}
		/**
		* Get tree depth (or height)
		* @param {Object} options
		* @param {BPTree.tree} [options.root=this.tree] - Tree to use
		* @return {number} Computed depth
		*/

		case 23:
		i++;
		_context.next = 10;
		break;

		case 26:
		if (!(leaf.n !== null)) {
		_context.next = 30;
		break;
		}
		depth({
		root = this.tree
		} = {}) {
		let tree = root;
		let d = 0;

		leaf = this.fetch(leaf.n, { getLeaf: true, notFound: keyNotFound });
		_context.next = 31;
		break;
		while (tree.t === 'branch') {
		tree = tree.v[0];
		d += 1;
		}

		case 30:
		return _context.abrupt('break', 33);
		return d;
		}
		/**
		* Check tree invariants
		* @param {Object} options
		* @param {BPTree.tree} [options.root=this.tree] - Tree to check
		* @return {boolean} Returns `true` or throws an `Error()`
		*/

		case 31:
		_context.next = 6;
		break;

		case 33:
		case 'end':
		return _context.stop();
		}
		}
		}, values, this);
		})
		check({
		root = this.tree
		} = {}) {
		const depth = this.depth({
		root
		});

		/**
		* Get tree depth (or height)
		* @param {Object} options
		* @param {BPTree.tree} [options.root=this.tree] - Tree to use
		* @return {number} Computed depth
		*/
		function assert(expr, msg) {
		if (!expr) {
		throw new Error(msg);
		}
		}

		}, {
		key: 'depth',
		value: function depth() {
		var _ref5 = arguments.length > 0 && arguments[0] !== undefined ? arguments[0] : {},
		_ref5$root = _ref5.root,
		root = _ref5$root === undefined ? this.tree : _ref5$root;
		function checking(self, currentNode, currentDepth, lo, hi) {
		const node = currentNode;
		const keysLength = node.k.length;
		assert(keysLength <= self.maxKeys, 'Overflowed node');

		var tree = root;
		var d = 0;
		while (tree.t === 'branch') {
		tree = tree.v[0];
		d += 1;
		for (let i = 0, kl = keysLength - 1; i < kl; i++) {
		assert(self.cmpFn(node.k[i], node.k[i + 1]) === -1, 'Disordered or duplicate key');
		}
		return d;
		}

		/**
		* Check tree invariants
		* @param {Object} options
		* @param {BPTree.tree} [options.root=this.tree] - Tree to check
		* @return {boolean} Returns `true` or throws an `Error()`
		*/
		assert(lo.length === 0 \|\| self.cmpFn(lo[0], node.k[0]) < 1, 'lo error');
		assert(hi.length === 0 \|\| self.cmpFn(node.k[keysLength - 1], hi[0]) === -1, 'hi error');

		}, {
		key: 'check',
		value: function check() {
		var _ref6 = arguments.length > 0 && arguments[0] !== undefined ? arguments[0] : {},
		_ref6$root = _ref6.root,
		root = _ref6$root === undefined ? this.tree : _ref6$root;
		if (node.t === 'branch') {
		const kids = node.v;
		const kidsLength = kids.length;

		var depth = this.depth({ root: root });

		function assert(expr, msg) {
		if (!expr) {
		throw new Error(msg);
		if (currentDepth === 0) {
		assert(kidsLength >= 2, 'Underpopulated root');
		} else {
		assert(kidsLength >= self.minKeys, 'Underpopulated branch');
		}
		}

		function checking(self, currentNode, currentDepth, lo, hi) {
		var node = currentNode;
		var keysLength = node.k.length;
		assert(keysLength === kidsLength - 1, 'keys and kids don\'t correspond');

		assert(keysLength <= self.maxKeys, 'Overflowed node');
		for (let i = 0; i < kidsLength; i++) {
		const newLo = i === 0 ? lo : [node.k[i - 1]];
		const newHi = i === keysLength ? hi : [node.k[i]];
		checking(self, kids[i], currentDepth + 1, newLo, newHi);
		}
		} else if (node.t === 'leaf') {
		const v = node.v;
		assert(currentDepth === depth, 'Leaves at different depths');
		assert(keysLength === v.length, 'keys and values don\'t correspond');

		for (var i = 0, kl = keysLength - 1; i < kl; i++) {
		assert(self.cmpFn(node.k[i], node.k[i + 1]) === -1, 'Disordered or duplicate key');
		if (currentDepth > 0) {
		assert(v.length >= self.minKeys, 'Underpopulated leaf');
		}
		} else {
		assert(false, 'Bad type');
		}

		assert(lo.length === 0 \|\| self.cmpFn(lo[0], node.k[0]) < 1, 'lo error');
		assert(hi.length === 0 \|\| self.cmpFn(node.k[keysLength - 1], hi[0]) === -1, 'hi error');
		return true;
		}

		if (node.t === 'branch') {
		var kids = node.v;
		var kidsLength = kids.length;
		return checking(this, root, 0, [], []);
		}
		/**
		* Fetch the value(s) stored at `key`.
		*
		* - `getLeaf` returns the whole leaf
		* - `getPath` returns the path from the root to this leaf
		* - when defined, `notFound` can be either 'left' or 'right', it controls which key to return when it wasn't found
		*
		* @param {Key} key
		* @param {Object} options
		* @param {BPTree.tree} [options.root=this.tree] - Tree to search in
		* @param {boolean} [options.getLeaf=false] - Return the leaf containing the value(s)
		* @param {boolean} [options.getPath=false] - Return {val: value(s), leaf: leaf, path: pathFromRootToLeaf}
		* @param {string} [options.notFound] - either 'left' or 'right' - Return what was found left or right from key which doesn't exist
		* @return {Value\|Value[]\|Leaf\|Object\|Boolean}
		*/

		if (currentDepth === 0) {
		assert(kidsLength >= 2, 'Underpopulated root');
		} else {
		assert(kidsLength >= self.minKeys, 'Underpopulated branch');
		}

		assert(keysLength === kidsLength - 1, 'keys and kids don\'t correspond');
		fetch(key, {
		root = this.tree,
		getLeaf = false,
		getPath = false,
		notFound
		} = {}) {
		let node = root;
		let index;
		const path = [];

		for (var _i3 = 0; _i3 < kidsLength; _i3++) {
		var newLo = _i3 === 0 ? lo : [node.k[_i3 - 1]];
		var newHi = _i3 === keysLength ? hi : [node.k[_i3]];
		checking(self, kids[_i3], currentDepth + 1, newLo, newHi);
		}
		} else if (node.t === 'leaf') {
		var v = node.v;
		assert(currentDepth === depth, 'Leaves at different depths');
		assert(keysLength === v.length, 'keys and values don\'t correspond');
		if (currentDepth > 0) {
		assert(v.length >= self.minKeys, 'Underpopulated leaf');
		}
		} else {
		assert(false, 'Bad type');
		while (node.t === 'branch') {
		index = 0;
		let found = false;

		for (let kl = node.k.length; index < kl; index++) {
		if (this.cmpFn(node.k[index], key) === 1) {
		found = true;
		break;
		}
		return true;
		}

		return checking(this, root, 0, [], []);
		if (!found) {
		index = node.v.length - 1;
		}

		node = node.v[index];
		path.push(index);
		}

		/**
		* Fetch the value(s) stored at `key`.
		*
		* - `getLeaf` returns the whole leaf
		* - `getPath` returns the path from the root to this leaf
		* - when defined, `notFound` can be either 'left' or 'right', it controls which key to return when it wasn't found
		*
		* @param {Key} key
		* @param {Object} options
		* @param {BPTree.tree} [options.root=this.tree] - Tree to search in
		* @param {boolean} [options.getLeaf=false] - Return the leaf containing the value(s)
		* @param {boolean} [options.getPath=false] - Return {val: value(s), leaf: leaf, path: pathFromRootToLeaf}
		* @param {string} [options.notFound] - either 'left' or 'right' - Return what was found left or right from key which doesn't exist
		* @return {Value\|Value[]\|Leaf\|Object\|Boolean}
		*/
		for (let j = 0, kl = node.k.length; j < kl; j++) {
		const cmp = this.cmpFn(key, node.k[j]);

		}, {
		key: 'fetch',
		value: function fetch(key) {
		var _ref7 = arguments.length > 1 && arguments[1] !== undefined ? arguments[1] : {},
		_ref7$root = _ref7.root,
		root = _ref7$root === undefined ? this.tree : _ref7$root,
		_ref7$getLeaf = _ref7.getLeaf,
		getLeaf = _ref7$getLeaf === undefined ? false : _ref7$getLeaf,
		_ref7$getPath = _ref7.getPath,
		getPath = _ref7$getPath === undefined ? false : _ref7$getPath,
		notFound = _ref7.notFound;
		if (cmp === 0) {
		const val = node.v[j];

		var node = root;
		if (getPath) {
		return {
		val,
		leaf: node,
		path
		};
		}

		var index = void 0;
		var path = [];
		while (node.t === 'branch') {
		index = 0;
		var found = false;
		for (var kl = node.k.length; index < kl; index++) {
		if (this.cmpFn(node.k[index], key) === 1) {
		found = true;
		break;
		}
		if (getLeaf) {
		return node;
		}
		if (!found) {
		index = node.v.length - 1;
		}
		node = node.v[index];
		path.push(index);

		return val;
		}

		for (var j = 0, _kl = node.k.length; j < _kl; j++) {
		var cmp = this.cmpFn(key, node.k[j]);
		if (cmp === 0) {
		var val = node.v[j];
		if (notFound) {
		if (notFound === 'right' && !(cmp < 0)) {
		return this.fetch(node.n, {
		root,
		getLeaf,
		getPath
		});
		}

		node = this._get(path);
		let val;

		if (notFound === 'left' && !(cmp < 0)) {
		val = node.v[node.v.length - 1];
		} else if (notFound === 'right') {
		val = node.v[0];
		}

		if (val) {
		if (getPath) {
		return { val: val, leaf: node, path: path };
		return {
		val,
		leaf: node,
		path
		};
		}

		if (getLeaf) {
		return node;
		}

		return val;
		} else if (notFound) {
		if (notFound === 'right' && !(cmp < 0)) {
		return this.fetch(node.n, { root: root, getLeaf: getLeaf, getPath: getPath });
		}
		node = this._get(path);
		var _val = void 0;
		if (notFound === 'left' && !(cmp < 0)) {
		_val = node.v[node.v.length - 1];
		} else if (notFound === 'right') {
		_val = node.v[0];
		}
		if (_val) {
		if (getPath) {
		return { val: _val, leaf: node, path: path };
		}
		if (getLeaf) {
		return node;
		}
		return _val;
		}
		} else if (this.cmpFn(node.k[j], key) === 1) {
		break; // just to finish quicker; not needed for correctness
		}
		} else if (this.cmpFn(node.k[j], key) === 1) {
		break; // just to finish quicker; not needed for correctness
		}
		return false;
		}
		}, {
		key: '_doStore',
		value: function _doStore(key, value) {
		var path = [];
		var node = this.tree;

		// Find the leaf node for key, and the path down to it.
		while (node.t === 'branch') {
		var _i4 = 0;
		var _found = false;
		for (var _nkl = node.k.length; _i4 < _nkl; _i4++) {
		if (this.cmpFn(key, node.k[_i4]) === -1) {
		_found = true;
		break;
		}
		}
		if (!_found) {
		_i4 = node.k.length;
		}
		path.push({ t: node.t, k: node.k, v: node.v, i: _i4 });
		node = node.v[_i4];
		}
		return false;
		}

		// Find the index for key in the leaf node.
		var i = 0;
		var found = false;
		var nkl = node.k.length;
		for (; i < nkl; i++) {
		if (this.cmpFn(key, node.k[i]) === 0) {
		// key isn't actually new, so the structure goes unchanged.
		node.v[i].push(value);
		return;
		} else if (this.cmpFn(key, node.k[i]) === -1) {
		_doStore(key, value) {
		const path = [];
		let node = this.tree; // Find the leaf node for key, and the path down to it.

		while (node.t === 'branch') {
		let i = 0;
		let found = false;

		for (let nkl = node.k.length; i < nkl; i++) {
		if (this.cmpFn(key, node.k[i]) === -1) {
		found = true;
		@@ -540,394 +503,426 @@ break;
		}

		if (!found) {
		i = nkl;
		i = node.k.length;
		}

		// We'll have to insert it in the leaf at i. If there's room, just do it:
		node.k.splice(i, 0, key);
		node.v.splice(i, 0, [value]);
		this.numKeys += 1;
		this.numVals += 1;
		path.push({
		t: node.t,
		k: node.k,
		v: node.v,
		i
		});
		node = node.v[i];
		} // Find the index for key in the leaf node.

		if (node.k.length < this.order) {

		let i = 0;
		let found = false;
		const nkl = node.k.length;

		for (; i < nkl; i++) {
		if (this.cmpFn(key, node.k[i]) === 0) {
		// key isn't actually new, so the structure goes unchanged.
		node.v[i].push(value);
		return;
		}

		// Otherwise split the now-overpacked leaf...
		var mid = Math.floor(this.order / 2);
		var tween = node.k[mid];
		var left = { t: 'leaf', k: node.k.slice(0, mid), v: node.v.slice(0, mid), n: node.k[mid] };
		var right = { t: 'leaf', k: node.k.slice(mid), v: node.v.slice(mid), n: node.n };
		if (this.cmpFn(key, node.k[i]) === -1) {
		found = true;
		break;
		}
		}

		// ...and propagate the split back up the path.
		while (path.length) {
		node = path.pop();
		node.k.splice(node.i, 0, tween);
		node.v[node.i] = left;
		node.v.splice(node.i + 1, 0, right);
		if (node.k.length < this.maxKeys) {
		return;
		}
		tween = node.k[mid - 1];
		left = { t: 'branch', k: node.k.slice(0, mid - 1), v: node.v.slice(0, mid), n: node.k[mid] };
		right = { t: 'branch', k: node.k.slice(mid), v: node.v.slice(mid), n: null };
		if (!found) {
		i = nkl;
		} // We'll have to insert it in the leaf at i. If there's room, just do it:


		node.k.splice(i, 0, key);
		node.v.splice(i, 0, [value]);
		this.numKeys += 1;
		this.numVals += 1;

		if (node.k.length < this.order) {
		return;
		} // Otherwise split the now-overpacked leaf...


		const mid = Math.floor(this.order / 2);
		let tween = node.k[mid];
		let left = {
		t: 'leaf',
		k: node.k.slice(0, mid),
		v: node.v.slice(0, mid),
		n: node.k[mid]
		};
		let right = {
		t: 'leaf',
		k: node.k.slice(mid),
		v: node.v.slice(mid),
		n: node.n
		}; // ...and propagate the split back up the path.

		while (path.length) {
		node = path.pop();
		node.k.splice(node.i, 0, tween);
		node.v[node.i] = left;
		node.v.splice(node.i + 1, 0, right);

		if (node.k.length < this.maxKeys) {
		return;
		}

		// If we got here, we need a new root.
		this.tree = { t: 'branch', k: [tween], v: [left, right], n: null };
		tween = node.k[mid - 1];
		left = {
		t: 'branch',
		k: node.k.slice(0, mid - 1),
		v: node.v.slice(0, mid),
		n: node.k[mid]
		};
		right = {
		t: 'branch',
		k: node.k.slice(mid),
		v: node.v.slice(mid),
		n: null
		};
		} // If we got here, we need a new root.


		this.tree = {
		t: 'branch',
		k: [tween],
		v: [left, right],
		n: null
		};
		}
		/**
		* Insert value at key key
		* @param {Key} key
		* @param {Value} value
		* @return {boolean} true
		*/


		store(key, value) {
		this._doStore(key, value);

		if (this.debug) {
		this.check();
		}

		/**
		* Insert value at key key
		* @param {Key} key
		* @param {Value} value
		* @return {boolean} true
		*/
		return true;
		}

		}, {
		key: 'store',
		value: function store(key, value) {
		this._doStore(key, value);
		if (this.debug) {
		this.check();
		}
		return true;
		_get(path, node = this.tree) {
		let object = node;
		let index = 0;
		const length = path.length;

		while (object && index < length) {
		object = object.v[path[index++]];
		}
		}, {
		key: '_get',
		value: function _get(path) {
		var node = arguments.length > 1 && arguments[1] !== undefined ? arguments[1] : this.tree;

		var object = node;
		var index = 0;
		var length = path.length;
		return object;
		}

		while (object && index < length) {
		object = object.v[path[index++]];
		}
		return object;
		_genGetKeyFn(driller, depth) {
		if (depth === 0) {
		return o => driller(o).k[0];
		}
		}, {
		key: '_genGetKeyFn',
		value: function _genGetKeyFn(driller, depth) {
		if (depth === 0) {
		return function (o) {
		return driller(o).k[0];
		};
		}
		return this._genGetKeyFn(function (o) {
		return driller(o).v[0];
		}, depth - 1);
		}
		}, {
		key: '_getFirstKeyFn',
		value: function _getFirstKeyFn(depth) {
		var fn = [function (o) {
		return o;
		}, function (o) {
		return o.v[0];
		}, function (o) {
		return o.v[0].v[0];
		}, function (o) {
		return o.v[0].v[0].v[0];
		}, function (o) {
		return o.v[0].v[0].v[0].v[0];
		}, function (o) {
		return o.v[0].v[0].v[0].v[0].v[0];
		}, function (o) {
		return o.v[0].v[0].v[0].v[0].v[0].v[0];
		}, function (o) {
		return o.v[0].v[0].v[0].v[0].v[0].v[0].v[0];
		}, function (o) {
		return o.v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0];
		}, function (o) {
		return o.v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0];
		}, function (o) {
		return o.v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0];
		}, function (o) {
		return o.v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0];
		}, function (o) {
		return 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];
		}, function (o) {
		return 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];
		}, function (o) {
		return 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];
		}, function (o) {
		return 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];
		}, function (o) {
		return 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];
		}];
		var length = fn.length;
		return depth < length - 1 && function (o) {
		return fn[depth](o).k[0];
		} \|\| this._genGetKeyFn(fn[length - 1], depth - length + 1);
		}
		}, {
		key: '_fixKeys',
		value: function _fixKeys() {
		var _this = this;

		var result = [];
		function walk(node, depth, path) {
		if (node.t === 'branch') {
		var kids = node.v;
		for (var i = 0, kl = kids.length; i < kl; i++) {
		if (kids[i].t === 'branch') {
		var newPath = path.slice(0, depth).concat([i]);
		result.push(newPath);
		walk(kids[i], depth + 1, newPath);
		}
		return this._genGetKeyFn(o => driller(o).v[0], depth - 1);
		}

		_getFirstKeyFn(depth) {
		const fn = [o => o, o => o.v[0], o => o.v[0].v[0], o => o.v[0].v[0].v[0], o => o.v[0].v[0].v[0].v[0], o => o.v[0].v[0].v[0].v[0].v[0], o => o.v[0].v[0].v[0].v[0].v[0].v[0], o => o.v[0].v[0].v[0].v[0].v[0].v[0].v[0], o => o.v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0], o => o.v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0], o => o.v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0], o => o.v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0], o => 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], o => 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], o => 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], o => 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], o => 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]];
		const length = fn.length;
		return depth < length - 1 && (o => fn[depth](o).k[0]) \|\| this._genGetKeyFn(fn[length - 1], depth - length + 1);
		}

		_fixKeys() {
		const result = [];

		function walk(node, depth, path) {
		if (node.t === 'branch') {
		const kids = node.v;

		for (let i = 0, kl = kids.length; i < kl; i++) {
		if (kids[i].t === 'branch') {
		const newPath = path.slice(0, depth).concat([i]);
		result.push(newPath);
		walk(kids[i], depth + 1, newPath);
		}
		}
		}
		walk(this.tree, 0, []);
		result.sort(function (a, b) {
		return a.length > b.length ? -1 : a.length < b.length ? 1 : 0;
		}); // eslint-disable-line
		}

		result.forEach(function (path) {
		var sub = _this._get(path);
		sub.k = sub.v.slice(1).map(_this._getFirstKeyFn(result[0].length - path.length));
		});
		walk(this.tree, 0, []);
		result.sort((a, b) => a.length > b.length ? -1 : a.length < b.length ? 1 : 0); // eslint-disable-line

		if (this.tree.t !== 'leaf') {
		this.tree.k = this.tree.v.slice(1).map(this._getFirstKeyFn(result.length ? result[0].length : 0));
		}
		result.forEach(path => {
		const sub = this._get(path);

		return result;
		sub.k = sub.v.slice(1).map(this._getFirstKeyFn(result[0].length - path.length));
		});

		if (this.tree.t !== 'leaf') {
		this.tree.k = this.tree.v.slice(1).map(this._getFirstKeyFn(result.length ? result[0].length : 0));
		}
		}, {
		key: '_removeKey',
		value: function _removeKey(key, val) {
		var fetched = this.fetch(key, { getPath: true });

		if (!fetched) {
		return false;
		}
		return result;
		}

		var keyIndex = fetched.leaf.k.indexOf(key);
		var valIndex = fetched.leaf.v[keyIndex].indexOf(val);
		_removeKey(key, val) {
		const fetched = this.fetch(key, {
		getPath: true
		});

		// key does not contain val
		if (val !== undefined && valIndex === -1) {
		return false;
		}
		if (!fetched) {
		return false;
		}

		var valCount = fetched.leaf.v[keyIndex].length;
		var removed = void 0;
		const keyIndex = fetched.leaf.k.indexOf(key);
		const valIndex = fetched.leaf.v[keyIndex].indexOf(val); // key does not contain val

		// we only have one val, remove it together with its key
		if (valCount === 1 && keyIndex !== -1) {
		fetched.leaf.k.splice(keyIndex, 1);
		removed = fetched.leaf.v[keyIndex][0];
		fetched.leaf.v.splice(keyIndex, 1);
		this.numKeys--;
		} else if (val !== undefined) {
		// key contains val, but we have other vals, only remove this val
		removed = fetched.leaf.v[keyIndex][valIndex];
		fetched.leaf.v[keyIndex].splice(valIndex, 1);
		} else {
		// key has several vals, we don't remove anything
		return false;
		}
		if (val !== undefined && valIndex === -1) {
		return false;
		}

		// we lost one val
		this.numvals--;
		return { val: removed, leaf: fetched.leaf, path: fetched.path };
		const valCount = fetched.leaf.v[keyIndex].length;
		let removed; // we only have one val, remove it together with its key

		if (valCount === 1 && keyIndex !== -1) {
		fetched.leaf.k.splice(keyIndex, 1);
		removed = fetched.leaf.v[keyIndex][0];
		fetched.leaf.v.splice(keyIndex, 1);
		this.numKeys--;
		} else if (val !== undefined) {
		// key contains val, but we have other vals, only remove this val
		removed = fetched.leaf.v[keyIndex][valIndex];
		fetched.leaf.v[keyIndex].splice(valIndex, 1);
		} else {
		// key has several vals, we don't remove anything
		return false;
		} // we lost one val


		this.numVals--;
		return {
		val: removed,
		leaf: fetched.leaf,
		path: fetched.path
		};
		}

		_doRemove(key, val) {
		// get leaf for key, remove key from leaf
		const removed = this._removeKey(key, val);

		if (typeof removed === 'boolean') {
		return false;
		}
		}, {
		key: '_doRemove',
		value: function _doRemove(key, val) {
		// get leaf for key, remove key from leaf
		var removed = this._removeKey(key, val);
		if (!removed) {
		return false;
		}
		var leaf = removed.leaf;
		var path = removed.path;

		// if key in branch.k, replace it with new smallest key in leaf
		var parentPath = path.slice(0, path.length - 1);
		var parent = this._get(parentPath);
		var index = parent.k.indexOf(key);
		const leaf = removed.leaf;
		const path = removed.path; // if key in branch.k, replace it with new smallest key in leaf

		// if leaf is at least half full, terminate
		if (leaf.v.length >= this.minKeys) {
		return removed.val;
		const parentPath = path.slice(0, path.length - 1);

		let parent = this._get(parentPath);

		let index = parent.k.indexOf(key); // if leaf is at least half full, terminate

		if (leaf.v.length >= this.minKeys) {
		return removed.val;
		}

		const leafIndex = path[path.length - 1]; // else borrow
		// if rightSibling is more than half full, borrow leftmost value

		let canBorrowRight = false;

		if (leafIndex < parent.v.length - 1) {
		const rightSibling = parent.v[leafIndex + 1];

		if (rightSibling && rightSibling.k.length > this.minKeys) {
		// can borrow from right because it is more than half full
		canBorrowRight = true;
		const keyToBorrow = rightSibling.k.shift();
		const valBorrowed = rightSibling.v.shift();
		leaf.k.push(keyToBorrow);
		leaf.v.push(valBorrowed);
		leaf.n = rightSibling.k[0];
		parent.k = parent.v.slice(1).map(o => o.k[0]);
		parent.v[leafIndex] = leaf;
		parent.v[leafIndex + 1] = rightSibling;
		}
		} // if leftSibling is more than half full, borrow rightmost value

		var leafIndex = path[path.length - 1];

		// else borrow
		let canBorrowLeft = false;

		// if rightSibling is more than half full, borrow leftmost value
		var canBorrowRight = false;
		if (leafIndex < parent.v.length - 1) {
		var rightSibling = parent.v[leafIndex + 1];
		if (rightSibling && rightSibling.k.length > this.minKeys) {
		// can borrow from right because it is more than half full
		canBorrowRight = true;
		var keyToBorrow = rightSibling.k.shift();
		var valBorrowed = rightSibling.v.shift();
		leaf.k.push(keyToBorrow);
		leaf.v.push(valBorrowed);
		leaf.n = rightSibling.k[0];
		parent.k = parent.v.slice(1).map(function (o) {
		return o.k[0];
		});
		parent.v[leafIndex] = leaf;
		parent.v[leafIndex + 1] = rightSibling;
		}
		if (leafIndex > 0) {
		const leftSibling = parent.v[leafIndex - 1];

		if (leftSibling && leftSibling.k.length > this.minKeys) {
		// can borrow from left because it is more than half full
		canBorrowLeft = true;
		const keyToBorrow = leftSibling.k.pop();
		const valBorrowed = leftSibling.v.pop();
		leaf.k.unshift(keyToBorrow);
		leaf.v.unshift(valBorrowed);
		parent.k = parent.v.slice(1).map(o => o.k[0]);
		parent.v[leafIndex] = leaf;
		parent.v[leafIndex - 1] = leftSibling;
		}
		}

		// if leftSibling is more than half full, borrow rightmost value
		var canBorrowLeft = false;
		if (leafIndex > 0) {
		var leftSibling = parent.v[leafIndex - 1];
		if (leftSibling && leftSibling.k.length > this.minKeys) {
		// can borrow from left because it is more than half full
		canBorrowLeft = true;
		var _keyToBorrow = leftSibling.k.pop();
		var _valBorrowed = leftSibling.v.pop();
		leaf.k.unshift(_keyToBorrow);
		leaf.v.unshift(_valBorrowed);
		parent.k = parent.v.slice(1).map(function (o) {
		return o.k[0];
		});
		parent.v[leafIndex] = leaf;
		parent.v[leafIndex - 1] = leftSibling;
		if (!canBorrowRight && !canBorrowLeft) {
		let again = true;
		let lastIndex = -1;

		while (again) {
		parent = this._get(path);
		lastIndex = index;

		if (path.length) {
		index = path.pop();
		} else {
		index = 0;
		again = false;
		}
		}

		if (!canBorrowRight && !canBorrowLeft) {
		var again = true;
		var lastIndex = void 0;
		while (again) {
		parent = this._get(path);
		lastIndex = index;
		if (path.length) {
		index = path.pop();
		} else {
		index = 0;
		again = false;
		}
		const mergeNeeded = parent.t !== 'leaf' && parent.v[lastIndex].k.length < this.minKeys;

		var mergeNeeded = parent.t !== 'leaf' && parent.v[lastIndex].k.length < this.minKeys;
		if (mergeNeeded) {
		const leftExists = parent.v[lastIndex - 1];
		let leftSum = leftExists && parent.v[lastIndex - 1].k.length + parent.v[lastIndex].k.length;
		leftSum += parent.v[lastIndex].t === 'leaf' ? 0 : 1;
		const roomOnLeft = leftExists && leftSum && leftSum <= this.maxKeys;
		const rightExists = parent.v[lastIndex + 1];
		let rightSum = rightExists && parent.v[lastIndex + 1].k.length + parent.v[lastIndex].k.length;
		rightSum += parent.v[lastIndex].t === 'leaf' ? 0 : 1;
		const roomOnRight = rightExists && rightSum && rightSum <= this.maxKeys;
		let splitIndex = false;

		if (mergeNeeded) {
		var leftExists = parent.v[lastIndex - 1];
		var leftSum = leftExists && parent.v[lastIndex - 1].k.length + parent.v[lastIndex].k.length;
		leftSum += parent.v[lastIndex].t === 'leaf' ? 0 : 1;
		var roomOnLeft = leftExists && leftSum && leftSum <= this.maxKeys;
		if (leftExists && roomOnLeft \|\| leftExists && !roomOnRight) {
		if (!roomOnLeft) {
		splitIndex = lastIndex - 1;
		} // merging with left, deleting sibling
		// node becomes (sibling merged with node)

		var rightExists = parent.v[lastIndex + 1];
		var rightSum = rightExists && parent.v[lastIndex + 1].k.length + parent.v[lastIndex].k.length;
		rightSum += parent.v[lastIndex].t === 'leaf' ? 0 : 1;
		var roomOnRight = rightExists && rightSum && rightSum <= this.maxKeys;

		var splitIndex = false;
		parent.v[lastIndex] = BPlusTree._mergeLeft(parent.v[lastIndex - 1], parent.v[lastIndex]);
		parent.v.splice(lastIndex, 1); // delete now merged sibling
		} else if (rightExists) {
		if (!roomOnRight) {
		splitIndex = lastIndex;
		} // merging with right, deleting sibling
		// node becomes (node merged with sibling)

		if (leftExists && roomOnLeft \|\| leftExists && !roomOnRight) {
		if (!roomOnLeft) {
		splitIndex = lastIndex - 1;
		}
		// merging with left, deleting sibling
		// node becomes (sibling merged with node)
		parent.v[lastIndex] = this._mergeLeft(parent.v[lastIndex - 1], parent.v[lastIndex]);
		parent.v.splice(lastIndex, 1); // delete now merged sibling
		} else if (rightExists) {
		if (!roomOnRight) {
		splitIndex = lastIndex;
		}
		// merging with right, deleting sibling
		// node becomes (node merged with sibling)
		parent.v[lastIndex] = this._mergeRight(parent.v[lastIndex + 1], parent.v[lastIndex]);
		parent.v.splice(lastIndex + 1, 1); // delete now merged sibling
		}
		if (splitIndex !== false) {
		var branchToSplit = parent.v[splitIndex];
		var mid = this.minKeys;
		var leftContent = branchToSplit.v.slice(0, mid);
		var rightContent = branchToSplit.v.slice(mid);
		var childType = parent.t;
		var left = { t: childType, k: leftContent.slice(1).map(function (o) {
		return o.k[0];
		}), v: leftContent };
		var right = { t: childType, k: rightContent.slice(1).map(function (o) {
		return o.k[0];
		}), v: rightContent };
		parent.v.splice.apply(parent.v, [splitIndex, 1].concat([left, right]));
		}

		parent.v[lastIndex] = BPlusTree._mergeRight(parent.v[lastIndex + 1], parent.v[lastIndex]);
		parent.v.splice(lastIndex + 1, 1); // delete now merged sibling
		}

		if (splitIndex !== false) {
		const branchToSplit = parent.v[splitIndex];
		const mid = this.minKeys;
		const leftContent = branchToSplit.v.slice(0, mid);
		const rightContent = branchToSplit.v.slice(mid);
		const childType = parent.t;
		const left = {
		t: childType,
		k: leftContent.slice(1).map(o => o.k[0]),
		v: leftContent
		};
		const right = {
		t: childType,
		k: rightContent.slice(1).map(o => o.k[0]),
		v: rightContent
		};
		parent.v.splice(splitIndex, 1, left, right);
		}
		}
		}

		if (this.tree.v.length < 2 && this.tree.t !== 'leaf') {
		// underpopulated root
		if (this.tree.v[index].v.length > this.maxKeys) {
		// need to split
		var _mid = this.minKeys;
		var _leftContent = this.tree.v[index].v.slice(0, _mid);
		var _rightContent = this.tree.v[index].v.slice(_mid);
		var _left = { t: 'branch', k: [_leftContent[_leftContent.length - 1].k[0]], v: _leftContent };
		var _right = { t: 'branch', k: [_rightContent[_rightContent.length - 1].k[0]], v: _rightContent };
		this.tree.t = 'branch';
		this.tree.n = null;
		this.tree.k = [_right.v[0].k[0]];
		this.tree.v = [_left, _right];
		} else {
		// need to hoist
		this.tree.t = 'leaf';
		this.tree = this.tree.v[index];
		var slice = this.tree.v.slice(1);
		if (slice.length && slice[0].t) {
		this.tree.k = slice.map(function (n) {
		return n.k[0];
		});
		}
		if (this.tree.v.length < 2 && this.tree.t !== 'leaf') {
		// underpopulated root
		if (this.tree.v[index].v.length > this.maxKeys) {
		// need to split
		const mid = this.minKeys;
		const leftContent = this.tree.v[index].v.slice(0, mid);
		const rightContent = this.tree.v[index].v.slice(mid);
		const left = {
		t: 'branch',
		k: [leftContent[leftContent.length - 1].k[0]],
		v: leftContent
		};
		const right = {
		t: 'branch',
		k: [rightContent[rightContent.length - 1].k[0]],
		v: rightContent
		};
		this.tree.t = 'branch';
		this.tree.n = null;
		this.tree.k = [right.v[0].k[0]];
		this.tree.v = [left, right];
		} else {
		// need to hoist
		this.tree.t = 'leaf';
		this.tree = this.tree.v[index];
		const slice = this.tree.v.slice(1);

		if (slice.length && slice[0].t) {
		this.tree.k = slice.map(o => o.k[0]);
		}
		}
		}

		this._fixKeys();
		}
		return removed.val;
		this._fixKeys();
		}

		/**
		* Remove value from key key, or remove key and its value if key only has one value
		* @param {Key} key
		* @param {Value?} value
		* @return {Value} The removed value
		*/
		return removed.val;
		}
		/**
		* Remove value from key key, or remove key and its value if key only has one value
		* @param {Key} key
		* @param {Value?} value
		* @return {Value} The removed value
		*/

		}, {
		key: 'remove',
		value: function remove(key, value) {
		var removed = this._doRemove(key, value);
		if (this.debug) {
		this.check();
		}
		return removed;

		remove(key, value) {
		const removed = this._doRemove(key, value);

		if (this.debug) {
		this.check();
		}
		}, {
		key: '_mergeLeft',
		value: function _mergeLeft(dest, src) {
		dest.k = dest.k.concat(src.k);
		dest.v = dest.v.concat(src.v);
		dest.n = src.n;
		return dest;

		return removed;
		}

		static _mergeLeft(dest, src) {
		const node = dest;
		node.k = node.k.concat(src.k);
		node.v = node.v.concat(src.v);
		node.n = src.n;
		return node;
		}

		static _mergeRight(dest, _src) {
		const node = dest;
		const src = _src;

		if (src.t !== 'leaf') {
		src.v[src.v.length - 1].n = node.v[0].k[0];
		}
		}, {
		key: '_mergeRight',
		value: function _mergeRight(dest, src) {
		if (src.t !== 'leaf') {
		src.v[src.v.length - 1].n = dest.v[0].k[0];
		}
		dest.k = src.k.concat(dest.k);
		dest.v = src.v.concat(dest.v);
		return dest;
		}
		}]);

		return BPlusTree;
		}();
		node.k = src.k.concat(node.k);
		node.v = src.v.concat(node.v);
		return node;
		}

		}

		module.exports = BPlusTree;

254

lib/bplustree.js

		@@ -1,5 +0,17 @@
		import 'regenerator-runtime/runtime';
		// @flow

		type Tree = { t: string; k: number[]; v: any[]; n?: ?number };
		type CmpFn = ((a: any, b: any) => number);

		/** Class representing a B+ Tree. */
		class BPlusTree {
		order: number;
		debug: boolean;
		cmpFn: CmpFn;
		minKeys: number;
		maxKeys: number;
		numKeys: number;
		numVals: number;
		tree: Tree;

		/**
		@@ -11,3 +23,11 @@ * @param {Object} options
		*/
		constructor({ order = 6, debug = false, cmpFn = ((a, b) => (a < b) ? -1 : ((a > b) ? 1 : 0)) } = {}) { // eslint-disable-line
		constructor({
		order = 6,
		debug = false,
		cmpFn = ((a: any, b: any): number => ((a < b) ? -1 : ((a > b) ? 1 : 0))) // eslint-disable-line
		}: {
		order?: number;
		debug?: boolean;
		cmpFn?: CmpFn
		} = {}) {
		this.order = order;
		@@ -25,3 +45,8 @@ this.debug = debug;

		this.tree = { t: 'leaf', k: [], v: [], n: null };
		this.tree = {
		t: 'leaf',
		k: [],
		v: [],
		n: null,
		};
		}
		@@ -38,6 +63,10 @@
		*/
		repr({ root = this.tree, getKeys = false, getValues = false, descending = false } = {}) {
		const tree = root;
		const result = (getKeys \|\| getValues) ? [] : {};
		function walk(node) {
		repr({
		root, getKeys = false, getValues = false, descending = false,
		}: { root?: Tree; getKeys?: boolean; getValues?: boolean; descending?: boolean } = {}): Object \| any[] {
		const tree = root \|\| this.tree;
		let resultArray = [];
		const resultObject = {};

		function walk(node: Tree) {
		if (node.t === 'branch') {
		@@ -51,7 +80,7 @@ const kids = node.v;
		if (getKeys) {
		result.push(node.k[i]);
		resultArray.push(node.k[i]);
		} else if (getValues) {
		result.push(node.v[i]);
		resultArray.push(node.v[i]);
		} else {
		result[node.k[i]] = node.v[i];
		resultObject[node.k[i]] = node.v[i];
		}
		@@ -62,9 +91,14 @@ }
		walk(tree);
		const out = (result.length && Array.isArray(result[0])) ?
		Array.prototype.concat.apply([], result) : result;
		// if (Array.isArra)
		if (resultArray.length && resultArray[0].length) {
		resultArray = Array.prototype.concat.apply([], resultArray);
		}

		if ((getKeys \|\| getValues) && descending) {
		return out.reverse();
		if (resultArray.length && descending) {
		return resultArray.reverse();
		}
		return out;
		if (resultArray.length) {
		return resultArray;
		}
		return resultObject;
		}
		@@ -80,3 +114,3 @@
		*/
		fetchRange(lowerBound, upperBound, { descending = false } = {}) {
		fetchRange(lowerBound: number, upperBound: number, { descending = false }: { descending: boolean } = {}): any[] {
		const hi = upperBound;
		@@ -170,17 +204,21 @@ let lo = lowerBound;
		*/
		* values({ key, target, limit = Infinity, keyNotFound } = {}) {
		* values({
		key, target, limit = Infinity, keyNotFound,
		}: { key: any; target: any; limit: number; keyNotFound: ?string } = {}): Generator<any, ?Object, void> {
		let returned = 0;
		let leaf;
		if (typeof key === 'undefined') {
		key = -Infinity;
		keyNotFound = 'right';
		let _key = key;
		let _keyNotFound = keyNotFound;
		if (typeof _key === 'undefined') {
		_key = -Infinity;
		_keyNotFound = 'right';
		}
		leaf = this.fetch(key, { getLeaf: true, notFound: keyNotFound });
		leaf = this.fetch(_key, { getLeaf: true, notFound: _keyNotFound });

		if (!leaf) {
		return false;
		return undefined;
		}

		while (true) {
		let index = leaf.k.indexOf(key);
		while (true) { // eslint-disable-line no-constant-condition
		let index = leaf.k.indexOf(_key);
		if (index === -1) {
		@@ -207,3 +245,3 @@ index = 0;
		if (leaf.n !== null) {
		leaf = this.fetch(leaf.n, { getLeaf: true, notFound: keyNotFound });
		leaf = this.fetch(leaf.n, { getLeaf: true, notFound: _keyNotFound });
		} else {
		@@ -213,2 +251,3 @@ break;
		}
		return undefined;
		}
		@@ -222,3 +261,3 @@
		*/
		depth({ root = this.tree } = {}) {
		depth({ root = this.tree }: { root: Tree } = {}): number {
		let tree = root;
		@@ -239,6 +278,6 @@ let d = 0;
		*/
		check({ root = this.tree } = {}) {
		check({ root = this.tree }: { root: Tree } = {}): boolean {
		const depth = this.depth({ root });

		function assert(expr, msg) {
		function assert(expr: boolean, msg: string) {
		if (!expr) {
		@@ -249,3 +288,3 @@ throw new Error(msg);

		function checking(self, currentNode, currentDepth, lo, hi) {
		function checking(self: BPlusTree, currentNode: Tree, currentDepth: number, lo: any[], hi: any[]): boolean {
		const node = currentNode;
		@@ -311,3 +350,5 @@ const keysLength = node.k.length;
		*/
		fetch(key, { root = this.tree, getLeaf = false, getPath = false, notFound } = {}) {
		fetch(key: any, {
		root = this.tree, getLeaf = false, getPath = false, notFound,
		}: { root?: Tree; getLeaf?: boolean; getPath?: boolean; notFound?: ?string } = {}): any {
		let node = root;
		@@ -344,3 +385,4 @@
		return val;
		} else if (notFound) {
		}
		if (notFound) {
		if (notFound === 'right' && !(cmp < 0)) {
		@@ -372,3 +414,3 @@ return this.fetch(node.n, { root, getLeaf, getPath });

		_doStore(key, value) {
		_doStore(key: any, value: any) {
		const path = [];
		@@ -390,3 +432,8 @@ let node = this.tree;
		}
		path.push({ t: node.t, k: node.k, v: node.v, i: i });
		path.push({
		t: node.t,
		k: node.k,
		v: node.v,
		i,
		});
		node = node.v[i];
		@@ -404,3 +451,4 @@ }
		return;
		} else if (this.cmpFn(key, node.k[i]) === -1) {
		}
		if (this.cmpFn(key, node.k[i]) === -1) {
		found = true;
		@@ -427,4 +475,14 @@ break;
		let tween = node.k[mid];
		let left = { t: 'leaf', k: node.k.slice(0, mid), v: node.v.slice(0, mid), n: node.k[mid] };
		let right = { t: 'leaf', k: node.k.slice(mid), v: node.v.slice(mid), n: node.n };
		let left = {
		t: 'leaf',
		k: node.k.slice(0, mid),
		v: node.v.slice(0, mid),
		n: node.k[mid],
		};
		let right = {
		t: 'leaf',
		k: node.k.slice(mid),
		v: node.v.slice(mid),
		n: node.n,
		};

		@@ -441,8 +499,20 @@ // ...and propagate the split back up the path.
		tween = node.k[mid - 1];
		left = { t: 'branch', k: node.k.slice(0, mid - 1), v: node.v.slice(0, mid), n: node.k[mid] };
		right = { t: 'branch', k: node.k.slice(mid), v: node.v.slice(mid), n: null };
		left = {
		t: 'branch',
		k: node.k.slice(0, mid - 1),
		v: node.v.slice(0, mid),
		n: node.k[mid],
		};
		right = {
		t: 'branch',
		k: node.k.slice(mid),
		v: node.v.slice(mid),
		n: null,
		};
		}

		// If we got here, we need a new root.
		this.tree = { t: 'branch', k: [tween], v: [left, right], n: null };
		this.tree = {
		t: 'branch', k: [tween], v: [left, right], n: null,
		};
		}
		@@ -456,3 +526,3 @@
		*/
		store(key, value) {
		store(key: any, value: any): boolean {
		this._doStore(key, value);
		@@ -465,3 +535,3 @@ if (this.debug) {

		_get(path, node = this.tree) {
		_get(path: number[], node?: Tree = this.tree): Object {
		let object = node;
		@@ -477,36 +547,36 @@ let index = 0;

		_genGetKeyFn(driller, depth) {
		_genGetKeyFn(driller: (tree: Tree) => any, depth: number): (tree: Tree) => any {
		if (depth === 0) {
		return (o) => driller(o).k[0];
		return (o: Tree): any => driller(o).k[0];
		}
		return this._genGetKeyFn((o) => driller(o).v[0], depth - 1);
		return this._genGetKeyFn((o: Tree): any => driller(o).v[0], depth - 1);
		}

		_getFirstKeyFn(depth) {
		_getFirstKeyFn(depth: number): (tree: Tree) => any {
		const fn = [
		(o) => o,
		(o) => o.v[0],
		(o) => o.v[0].v[0],
		(o) => o.v[0].v[0].v[0],
		(o) => o.v[0].v[0].v[0].v[0],
		(o) => o.v[0].v[0].v[0].v[0].v[0],
		(o) => o.v[0].v[0].v[0].v[0].v[0].v[0],
		(o) => o.v[0].v[0].v[0].v[0].v[0].v[0].v[0],
		(o) => o.v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0],
		(o) => o.v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0],
		(o) => o.v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0],
		(o) => o.v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0],
		(o) => 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],
		(o) => 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],
		(o) => 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],
		(o) => 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],
		(o) => 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],
		(o: Tree): any => o,
		(o: Tree): any => o.v[0],
		(o: Tree): any => o.v[0].v[0],
		(o: Tree): any => o.v[0].v[0].v[0],
		(o: Tree): any => o.v[0].v[0].v[0].v[0],
		(o: Tree): any => o.v[0].v[0].v[0].v[0].v[0],
		(o: Tree): any => o.v[0].v[0].v[0].v[0].v[0].v[0],
		(o: Tree): any => o.v[0].v[0].v[0].v[0].v[0].v[0].v[0],
		(o: Tree): any => o.v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0],
		(o: Tree): any => o.v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0],
		(o: Tree): any => o.v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0].v[0],
		(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],
		(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],
		(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],
		(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],
		(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],
		(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],
		];
		const length = fn.length;
		return (depth < length - 1 && ((o) => fn[depth](o).k[0])) \|\| this._genGetKeyFn(fn[length - 1], depth - length + 1);
		return (depth < length - 1 && ((o: Tree): any => fn[depth](o).k[0])) \|\| this._genGetKeyFn(fn[length - 1], (depth - length) + 1);
		}

		_fixKeys() {
		_fixKeys(): any {
		const result = [];
		function walk(node, depth, path) {
		function walk(node: Tree, depth: number, path: any) {
		if (node.t === 'branch') {
		@@ -526,3 +596,3 @@ const kids = node.v;

		result.forEach((path) => {
		result.forEach((path: any) => {
		const sub = this._get(path);
		@@ -539,3 +609,3 @@ sub.k = sub.v.slice(1).map(this._getFirstKeyFn(result[0].length - path.length));

		_removeKey(key, val) {
		_removeKey(key: any, val: any): boolean \| Object {
		const fetched = this.fetch(key, { getPath: true });
		@@ -574,10 +644,10 @@
		// we lost one val
		this.numvals--;
		this.numVals--;
		return { val: removed, leaf: fetched.leaf, path: fetched.path };
		}

		_doRemove(key, val) {
		_doRemove(key: any, val: any): boolean \| any {
		// get leaf for key, remove key from leaf
		const removed = this._removeKey(key, val);
		if (!removed) {
		if (typeof removed === 'boolean') {
		return false;
		@@ -599,3 +669,2 @@ }
		const leafIndex = path[path.length - 1];

		// else borrow
		@@ -615,3 +684,3 @@
		leaf.n = rightSibling.k[0];
		parent.k = parent.v.slice(1).map((o) => o.k[0]);
		parent.k = parent.v.slice(1).map((o: Object): any => o.k[0]);
		parent.v[leafIndex] = leaf;
		@@ -633,3 +702,3 @@ parent.v[leafIndex + 1] = rightSibling;
		leaf.v.unshift(valBorrowed);
		parent.k = parent.v.slice(1).map((o) => o.k[0]);
		parent.k = parent.v.slice(1).map((o: Object): any => o.k[0]);
		parent.v[leafIndex] = leaf;
		@@ -642,3 +711,3 @@ parent.v[leafIndex - 1] = leftSibling;
		let again = true;
		let lastIndex;
		let lastIndex = -1;
		while (again) {
		@@ -675,3 +744,3 @@ parent = this._get(path);
		// node becomes (sibling merged with node)
		parent.v[lastIndex] = this._mergeLeft(parent.v[lastIndex - 1], parent.v[lastIndex]);
		parent.v[lastIndex] = BPlusTree._mergeLeft(parent.v[lastIndex - 1], parent.v[lastIndex]);
		parent.v.splice(lastIndex, 1); // delete now merged sibling
		@@ -684,3 +753,3 @@ } else if (rightExists) {
		// node becomes (node merged with sibling)
		parent.v[lastIndex] = this._mergeRight(parent.v[lastIndex + 1], parent.v[lastIndex]);
		parent.v[lastIndex] = BPlusTree._mergeRight(parent.v[lastIndex + 1], parent.v[lastIndex]);
		parent.v.splice(lastIndex + 1, 1); // delete now merged sibling
		@@ -694,5 +763,5 @@ }
		const childType = parent.t;
		const left = { t: childType, k: leftContent.slice(1).map((o) => o.k[0]), v: leftContent };
		const right = { t: childType, k: rightContent.slice(1).map((o) => o.k[0]), v: rightContent };
		parent.v.splice.apply(parent.v, [splitIndex, 1].concat([left, right]));
		const left = { t: childType, k: leftContent.slice(1).map((o: Object): any => o.k[0]), v: leftContent };
		const right = { t: childType, k: rightContent.slice(1).map((o: Object): any => o.k[0]), v: rightContent };
		parent.v.splice(splitIndex, 1, left, right);
		}
		@@ -721,3 +790,3 @@ }
		if (slice.length && slice[0].t) {
		this.tree.k = slice.map((n) => n.k[0]);
		this.tree.k = slice.map((o: Object): any => o.k[0]);
		}
		@@ -738,3 +807,3 @@ }
		*/
		remove(key, value) {
		remove(key: any, value: any): any {
		const removed = this._doRemove(key, value);
		@@ -747,16 +816,19 @@ if (this.debug) {

		_mergeLeft(dest, src) {
		dest.k = dest.k.concat(src.k);
		dest.v = dest.v.concat(src.v);
		dest.n = src.n;
		return dest;
		static _mergeLeft(dest: Tree, src: Tree): Tree {
		const node = dest;
		node.k = node.k.concat(src.k);
		node.v = node.v.concat(src.v);
		node.n = src.n;
		return node;
		}

		_mergeRight(dest, src) {
		static _mergeRight(dest: Tree, _src: Tree): Tree {
		const node = dest;
		const src = _src;
		if (src.t !== 'leaf') {
		src.v[src.v.length - 1].n = dest.v[0].k[0];
		src.v[src.v.length - 1].n = node.v[0].k[0];
		}
		dest.k = src.k.concat(dest.k);
		dest.v = src.v.concat(dest.v);
		return dest;
		node.k = src.k.concat(node.k);
		node.v = src.v.concat(node.v);
		return node;
		}
		@@ -763,0 +835,0 @@ }

package.json

		{
		"name": "bplustree",
		"version": "1.2.2",
		"version": "2.0.0",
		"engines": {
		"node": ">=8.0.0"
		},
		"scripts": {
		"test": "mocha --compilers js:babel-core/register --check-leaks test/bplustree.js && npm run build",
		"test-full": "mocha --compilers js:babel-core/register --check-leaks test/bplustree.js test/full.js",
		"test-travis": "npm run build && npm run test-full && npm run coverage-full",
		"coverage": "babel-node node_modules/isparta/bin/isparta cover ./node_modules/mocha/bin/_mocha -- test/bplustree.js",
		"coverage-full": "./node_modules/.bin/babel-node ./node_modules/.bin/babel-istanbul cover ./node_modules/.bin/_mocha -- test/bplustree.js test/full.js",
		"coveralls": "npm run coverage-full && cat /home/travis/build/vhf/bplustree/coverage/lcov.info \| coveralls",
		"test": "jest && npm run build",
		"test-travis": "npm run build && npm run test && npm run coverage",
		"coverage": "jest --coverage",
		"coveralls": "npm run coverage && cat /home/travis/build/vhf/bplustree/coverage/lcov.info \| coveralls",
		"doc": "jsdoc -c .jsdoc lib -d docs",
		"build": "babel lib -d dist"
		"build": "babel lib -d dist",
		"eslint": "eslint .",
		"flow": "flow check",
		"lint": "npm run eslint && npm run flow"
		},
		"devDependencies": {
		"babel-cli": "^6.3.15",
		"babel-core": "^6.3.15",
		"babel-eslint": "^7.1.0",
		"babel-istanbul": "^0.11.0",
		"babel-plugin-transform-regenerator": "^6.16.1",
		"babel-preset-latest": "^6.16.0",
		"coveralls": "^2.11.6",
		"eslint": "^3.9.1",
		"eslint-config-airbnb-base": "^10.0.1",
		"@babel/cli": "^7.1.5",
		"@babel/core": "^7.1.6",
		"async": "^2.1.4",
		"babel-eslint": "^10.0.1",
		"babel-plugin-syntax-flow": "^6.18.0",
		"babel-plugin-transform-flow-strip-types": "^6.18.0",
		"benchmark": "^2.1.2",
		"colors": "^1.1.2",
		"coveralls": "^3.0.2",
		"eslint": "^5.9.0",
		"eslint-config-airbnb-base": "^13.1.0",
		"eslint-plugin-flowtype": "^3.2.0",
		"eslint-plugin-flowtype-errors": "^3.6.0",
		"eslint-plugin-import": "^2.1.0",
		"eslint-plugin-jest": "^22.0.0",
		"faker": "^4.1.0",
		"flow-bin": "^0.86.0",
		"istanbul": "^0.4.5",
		"mocha": "^3.1.2",
		"mocha-lcov-reporter": "^1.0.0"
		"jest": "^23.6.0",
		"jsdoc": "^3.5.5",
		"jsdoc-babel": "^0.5.0",
		"lodash": "^4.17.2"
		},
		"description": "B+ tree",
		"main": "dist/bplustree.js",
		"dependencies": {
		"babel-polyfill": "^6.16.0",
		"regenerator-runtime": "^0.9.6"
		},
		"dependencies": {},
		"repository": {
		@@ -42,3 +52,6 @@ "type": "git",
		"plus",
		"tree"
		"tree",
		"B+ tree",
		"b plus",
		"b plus tree"
		],
		@@ -45,0 +58,0 @@ "author": "Victor Felder",

.eslintrc

.npmignore

benchmark/findbestorder.js

test/bplustree.js

test/full.js

yarn.lock

.babelrc