btree

A BTree is a sorted, in-memory data store built on a B+ Tree. Keys and their associated values are stored directly in the tree's leaf nodes, providing sorted access and efficient range-based iteration without any secondary data structure.

There is one important way in which a BTree differs from a Map. The design inspiration comes from database indexes, which can either enforce unique key constraints or allow keys to have multiple associated values. A BTree can be configured either way. When keys are unique, a BTree effectively functions like a Map with the added benefit of key sorting and range-based access. When keys are non-unique, each key can have an array of associated values. This has several implications:

• The get method always returns an array of values for a key (a single-element array when keys are unique).
• The delete method removes the entire array of values associated with a key.
• The deleteValue method removes a single value from a key's array of associated values, and removes the key itself if the array becomes empty.
• The values iterator yields a result for each individual element of a key's array of associated values.
• The entries iterator yields a [key, value] pair for each individual element of a key's array of associated values.
• The forEach method applies the supplied function to each individual element of a key's array of associated values.

By default, a BTree is configured for unique keys.

Examples

Unique keys

const { BTree } = require("@jamesbontempo/btree");

const bt = new BTree();
bt.set(1, "one");
bt.get(1); // returns ["one"]
bt.set(1, "two"); // overwrites "one" with "two"
bt.get(1); // returns ["two"]
bt.delete(1); // deletes key 1 and its value

Non-unique keys

const { BTree } = require("@jamesbontempo/btree");

const bt = new BTree({ unique: false });
bt.set(1, "one");
bt.get(1); // returns ["one"]
bt.set(1, "two"); // adds "two" for key 1
bt.get(1); // returns ["one", "two"]
bt.deleteValue(1, "one"); // removes "one", key 1 still exists
bt.get(1); // returns ["two"]
bt.delete(1); // deletes key 1 and all its values

Custom comparator

When using object, array, or other keys that require custom ordering, provide a compare function. For deleteValue, provide a custom match function so that value matching is based on value rather than reference.

• compare — controls ordering in the tree (defaults to </> comparison)
• match (passed to deleteValue) — controls value matching during deletion (defaults to ===)

const { BTree } = require("@jamesbontempo/btree");

const bt = new BTree({
  compare: (a, b) => {
    const sa = JSON.stringify([...a].sort());
    const sb = JSON.stringify([...b].sort());
    return sa < sb ? -1 : sa > sb ? 1 : 0;
  }
});

bt.set([1, 2], "first");
bt.set([1, 3], "second");

const match = (a, b) => a === b;
bt.deleteValue([1, 2], "first", match);

Table of contents

• Constructor
• Properties
• Data manipulation methods
• Iterators
• Functional methods

Constructor

Syntax

new BTree([options])

Parameters

options

An object containing configuration options for the BTree.

Option|Type|Description|Default ------|----|-----------|------- unique|boolean|Whether keys are unique|true order|number|The order of the B+ Tree (minimum 3)|3 compare|function|The function used to compare keys for ordering|See below

The default comparator compares keys using the < and > operators, which works correctly for keys of a consistent primitive type (numbers, strings, BigInts, etc.). For custom ordering — such as object or array keys — supply your own comparator. It must take two values as input and return a negative number if the first should be sorted before the second, a positive number if the second should be sorted before the first, or zero if they are equal.

Examples

// Custom order and comparator
const bt = new BTree({
	unique: false,
	order: 5,
	compare: (a, b) => (a < b) ? -1 : ((a > b) ? 1 : 0)
});

// Array keys with custom comparator
const bt2 = new BTree({
	compare: (a, b) => {
		const sa = JSON.stringify([...a].sort());
		const sb = JSON.stringify([...b].sort());
		return sa < sb ? -1 : sa > sb ? 1 : 0;
	}
});

Properties

BTree.lowest

Returns the lowest key in the BTree, or undefined if the tree is empty.

BTree.highest

Returns the highest key in the BTree, or undefined if the tree is empty.

BTree.order

Returns the order of the BTree.

BTree.unique

Returns true if the BTree is configured for unique keys; false otherwise.

BTree.size

Returns the number of unique keys in the BTree. When configured for non-unique keys, the number of values may be greater than the size.

BTree.stats

Returns a copy of an object with statistics for the BTree:

Property|Description --------|----------- depth|The depth of the tree nodes|The number of internal nodes in the tree leaves|The number of leaf nodes in the tree keys|The number of keys in the tree values|The total number of values stored across all keys

Data manipulation methods

BTree.has()

Returns a boolean indicating whether the specified key exists.

Syntax

has(key)

Parameters

key

The key to test for presence in the BTree object.

Return value

true if the specified key exists; otherwise false.

BTree.set()

Adds a value for the specified key. If configured for unique keys and the key already exists, overwrites the existing value. If configured for non-unique keys, appends the value to the key's array of associated values. The key's values array preserves insertion order and allows duplicates.

Syntax

set(key, value)

Parameters

key

The key to add to the BTree object.

value

The associated value to add to the BTree object.

Return value

The BTree object.

BTree.get()

Returns the array of values associated with the specified key.

Syntax

get(key)

Parameters

key

The key whose associated values should be returned.

Return value

An array of values associated with the specified key, or undefined if the key doesn't exist. When configured for unique keys, the array will always contain a single element.

Examples

const bt = new BTree({ unique: false });
bt.set(1, "one");
bt.set(1, "uno");
bt.get(1); // returns ["one", "uno"]
bt.get(2); // returns undefined

BTree.delete()

Removes the specified key and all its associated values from the BTree.

Syntax

delete(key)

Parameters

key

The key to remove from the BTree object.

Return value

true if the key existed and was removed; false if the key does not exist.

BTree.deleteValue()

Removes a single value from the array of values associated with the specified key. If removing the value causes the array to become empty, the key itself is also removed.

By default, values are compared using strict equality (===). A custom match function can be provided for other equality semantics.

Syntax

deleteValue(key, value[, match])

Parameters

key

The key whose associated value should be removed.

value

The specific value to remove from the key's array of associated values.

match

An optional function (a, b) => boolean used to determine value equality. Defaults to a strict equality check.

Return value

true if the value was found and removed; false if either the key or value does not exist.

Examples

const bt = new BTree({ unique: false });
bt.set(1, "one");
bt.set(1, "uno");
bt.deleteValue(1, "one"); // returns true; key 1 still exists with ["uno"]
bt.deleteValue(1, "uno"); // returns true; key 1 is also removed
bt.deleteValue(1, "one"); // returns false; key 1 no longer exists

// Custom match function
bt.set(1, "Hello");
bt.set(1, "World");
bt.deleteValue(1, "hello", (a, b) => a.toLowerCase() === b.toLowerCase()); // removes "Hello"

BTree.clear()

Removes all elements from the BTree object.

Syntax

clear()

Return value

undefined

Iterators

BTree[@@iterator]()

Returns the same iterator object as the entries method.

Examples

for (const [key, value] of bt) {
	console.log(key, value);
}

BTree.keys()

Returns a new iterator object that contains the keys in the BTree in sorted order.

Syntax

keys([start, end, includeStart, includeEnd])

Parameters

start

The lowest key to include. Defaults to the lowest key in the BTree.

end

The highest key to include. Defaults to the highest key in the BTree.

includeStart

Whether to include start in the results. Default is true.

includeEnd

Whether to include end in the results. Default is true.

Return value

A new iterator object.

Examples

// All keys
bt.keys();

// Keys 1 through 10 (inclusive on both ends)
bt.keys(1, 10);

// Keys from the lowest up through 10
bt.keys(undefined, 10);

// Keys from 10 up through the highest
bt.keys(10, undefined);

// Keys greater than 1 and less than 10 (exclusive on both ends)
bt.keys(1, 10, false, false);

// Keys greater than 1 through 10 (exclusive start, inclusive end)
bt.keys(1, 10, false, true);

// Keys 1 up to but not including 10 (inclusive start, exclusive end)
bt.keys(1, 10, true, false);

BTree.values()

Returns a new iterator object that contains the values in the BTree, sorted by key order. When configured for non-unique keys, yields one value per element across all keys' value arrays.

Syntax

values([start, end, includeStart, includeEnd])

Parameters

See keys for parameter descriptions.

Return value

A new iterator object.

BTree.entries()

Returns a new iterator object that contains [key, value] pairs in the BTree, sorted by key order. When configured for non-unique keys, yields one [key, value] pair per element across all keys' value arrays — meaning more than one pair may be yielded for a given key.

Syntax

entries([start, end, includeStart, includeEnd])

Parameters

See keys for parameter descriptions.

Return value

A new iterator object.

Functional methods

BTree.forEach()

Executes a provided function once per [key, value] pair in the BTree, in sorted key order. When configured for non-unique keys, applies the function to each individual element of a key's array of associated values.

Syntax

forEach(function [, start, end, includeStart, includeEnd])

Parameters

function

The function to execute, invoked with three arguments: the value, the key, and the BTree object.

start, end, includeStart, includeEnd

See keys for parameter descriptions.

Return value

undefined

BTree.toString()

Returns a string representing the internal structure of the BTree. Primarily useful for debugging.

Syntax

toString()

Return value

A string representing the BTree object.