A performant, in-memory, immutable B+ tree data structure.
BTMap and BTSet)import { BTMap } from 'ibtree';
let map = BTMap.from([
[1, 'one'],
[2, 'two'],
[3, 'three'],
]);
map = map.set(4, 'four');
map.has(1)
// true
map.get(1)
// 'one'
Array.from(map.values())
// ['one', 'two', 'three', 'four']
// Range searches use the values/entries/keys API with
// arguments to specify boundaries.
Array.from(map.values(2, 3));
// ['two', 'three']
Array.from(map.values(3, 2));
// ['three', 'two']
map = map.withMutations(m => {
m.set(5, 'five').set(6, 'six').set(7, 'seven');
});
Array.from(map.values())
// ['one', 'two', 'three', 'four', 'give', 'six', 'seven']
import { BTSet } from 'ibtree';
let set = BTSet.from([1, 2, 3]);
set.has(1)
// true
set.has(4)
// false
set = set.add(0);
set.has(0)
// true
Array.from(set.values())
// [0, 1, 2, 3]
Array.from(map.values(2, 3));
// [2, 3]
Array.from(map.values(2, -10));
// [2, 1, 0]
BTMap is similar in performance to Immutable.Map. The range search is much faster because of the difference in data structures.
The tradeoff between Immutable.Map and BTMap is that BTMap uses more memory to store updated trees.
When the tree is updated, each affected node's keys and children (Arrays of length between 32 and 64) are shallow copied. There's 1-5 affected nodes based on the height of your tree, therefore each update creates (1-5) * 2 new arrays of length between 32 and 64, whereas Immutable.js doesn't copy as much. However, if you don't keep references to many historical versions, they should get garbage collected and shouldn't be a problem.
These are relative, not absolute benchmarks. The benchmark implementation uses an adapter to interface with both Immutable and ibtree, which introduces a small overhead.
Add N entries to an empty structure
N=10:
1. ibtree : 421 869,00 +/- 2.88% op/s,
2. Immutable.Map : 110 444,00 +/- 3.09% op/s, 73.8% slower than ibtree
N=1000:
1. ibtree : 1 156,00 +/- 3.59% op/s,
2. Immutable.Map : 1 114,00 +/- 2.79% op/s, 3.6% slower than ibtree
N=100000:
1. ibtree : 7,00 +/- 8.39% op/s,
2. Immutable.Map : 4,00 +/- 3.51% op/s, 42.9% slower than ibtree
Add N entries to a non-empty structure (transient)
N=10:
1. ibtree : 466 782,00 +/- 0.76% op/s,
2. Immutable.Map : 155 428,00 +/- 1.24% op/s, 66.7% slower than ibtree
N=1000:
1. Immutable.Map : 6 423,00 +/- 0.86% op/s,
2. ibtree : 1 578,00 +/- 3.13% op/s, 75.4% slower than Immutable.Map
N=100000:
1. ibtree : 13,00 +/- 1.56% op/s,
2. Immutable.Map : 10,00 +/- 7.70% op/s, 23.1% slower than ibtree
Bulkload N entries from empty (transient)
N=10:
1. Immutable.Map : 151 434,00 +/- 0.93% op/s,
2. ibtree : 150 663,00 +/- 6.91% op/s, 0.5% slower than Immutable.Map
N=1000:
1. Immutable.Map : 6 208,00 +/- 0.97% op/s,
2. ibtree : 5 512,00 +/- 1.60% op/s, 11.2% slower than Immutable.Map
N=100000:
1. ibtree : 45,00 +/- 0.82% op/s,
2. Immutable.Map : 10,00 +/- 7.43% op/s, 77.8% slower than ibtree
Get a random key from N entries
N=10:
1. Immutable.Map : 5 081 087,00 +/- 1.88% op/s,
2. ibtree : 4 652 828,00 +/- 2.13% op/s, 8.4% slower than Immutable.Map
N=1000:
1. Immutable.Map : 4 670 681,00 +/- 2.12% op/s,
2. ibtree : 2 909 412,00 +/- 1.62% op/s, 37.7% slower than Immutable.Map
N=100000:
1. ibtree : 1 404 300,00 +/- 2.37% op/s,
2. Immutable.Map : 1 006 802,00 +/- 4.51% op/s, 28.3% slower than ibtree
Delete one entry from N entries
N=10:
1. Immutable.Map : 1 620 353,00 +/- 1.77% op/s,
2. ibtree : 642 680,00 +/- 3.95% op/s, 60.3% slower than Immutable.Map
N=1000:
1. Immutable.Map : 837 346,00 +/- 1.00% op/s,
2. ibtree : 420 102,00 +/- 2.67% op/s, 49.8% slower than Immutable.Map
N=100000:
1. Immutable.Map : 418 477,00 +/- 1.68% op/s,
2. ibtree : 317 902,00 +/- 2.49% op/s, 24.0% slower than Immutable.Map
Delete All N Entries
N=10:
1. Immutable.Map : 4 196 670,00 +/- 0.76% op/s,
2. ibtree : 2 420 761,00 +/- 1.72% op/s, 42.3% slower than Immutable.Map
N=1000:
1. Immutable.Map : 45 432,00 +/- 0.93% op/s,
2. ibtree : 25 508,00 +/- 1.46% op/s, 43.9% slower than Immutable.Map
N=100000:
1. Immutable.Map : 433,00 +/- 2.53% op/s,
2. ibtree : 254,00 +/- 0.96% op/s, 41.3% slower than Immutable.Map
Delete All N Entries (transient)
N=10:
1. Immutable.Map : 4 951 169,00 +/- 4.10% op/s,
2. ibtree : 2 363 744,00 +/- 1.12% op/s, 52.3% slower than Immutable.Map
N=1000:
1. Immutable.Map : 63 367,00 +/- 2.62% op/s,
2. ibtree : 27 575,00 +/- 4.21% op/s, 56.5% slower than Immutable.Map
N=100000:
1. Immutable.Map : 564,00 +/- 0.93% op/s,
2. ibtree : 275,00 +/- 1.78% op/s, 51.2% slower than Immutable.Map
Get a random key range in order from N entries
N=10:
1. ibtree : 314 549,00 +/- 6.00% op/s,
2. Immutable.Map : 172 788,00 +/- 5.14% op/s, 45.1% slower than ibtree
N=1000:
1. ibtree : 288 446,00 +/- 5.25% op/s,
2. Immutable.Map : 7 632,00 +/- 2.30% op/s, 97.4% slower than ibtree
N=100000:
1. ibtree : 239 099,00 +/- 5.02% op/s,
2. Immutable.Map : 60,00 +/- 2.99% op/s, 100.0% slower than ibtree
Two classes are exposed: BTMap and BTSet.
Returns a new, empty BTMap. Override defaults with opts object. Defaults are:
{
// A function that extracts a key to use for comparisons.
// If you're using `tree.set(key, value)`, the key is extracted
// from `key`. If you're using `tree.add(value)`, it's
// extracted from `value`.
extractor: x => x,
// a and b are the keys extracted with `extractor`.
// This is close to the normal JavaScript comparison.
comparator: (a, b) => a === b ? 0 : a < b ? -1 : 1,
}
Returns a new BTMap with data from a sorted array of [key, value] pairs. Uses a bulkloading algorithm internally, which is significantly faster than inserting values individually. opts works the same as to new BTMap(opts). entries must be an array of key-value pairs. Example:
const map = BTMap.from([
['key1', 'value1'],
['key2', 'value2'],
]);
map.get('key1');
// 'value1'
map.get('key2');
// 'value2'
delete(key) and set(key, value) return a new, updated BTMap instance instead of mutating the current one.clear returns an empty BTMap.withMutations(fn) calls fn with a mutable version of the BTMap. Any methods called inside fn on the mutable version will be applied mutatively. Returns an immutable version of the tree.asMutable returns a mutable version of the BTMap.asImmutable returns an immutable version of the BTMap.These work the same as native Map:
entries()values()keys()get(key)has(key)[Symbol.iterator]()size: Returns number of values in the mapWorks the same as new BTMap().
Works the same as BTMap.from, except the first argument is a list of values instead of key-value pairs.
const btree = BTSet.from([
'value1',
'value2',
]);
btree.has('value1');
// true
btree.get('value1');
// 'value1'
btree.has('value2');
// true
delete(value) and add(value) return a new, updated BTSet instance instead of mutating the current one.clear returns an empty BTSet.withMutations(fn) calls fn with a mutable version of the BTSet. Any methods called inside fn on the mutable version will be applied mutatively. Returns an immutable version of the tree.asMutable returns a mutable version of the BTSet.asImmutable returns an immutable version of the BTSet.These work the same as native Set:
entries()values()keys()has(value)[Symbol.iterator]()size: Returns number of values in the setThe key benefit of B+ trees is the fast range search. Range searches extend the entries, values and keys instance methods to accept two arguments that specify the range boundaries.
entries([any fromKey, any toKey]) (also alias entryRange)values([any fromKey, any toKey]) (also alias valueRange)keys([any fromKey, any toKey]) (also alias keyRange)If these functions are called with zero arguments, they iterate through all the elements in order, just like the corresponding native Map and Set methods.
These additional methods are also supported:
range, which is an alias for entries in BTMap and values in BTSet.All these methods return an iterator for elements whose keys satisfy fromKey <= key <= toKey. The order of iteration is decided by comparing fromKey and toKey. If fromKey > toKey according to the instance's comparator, the iteration will be performed in reverse.
const entries = [
[1, 'one'],
[2, 'two'],
[3, 'three'],
[4, 'four'],
[5, 'five'],
[6, 'six'],
]
const map = BTMap.from(entries);
Array.from(map.values(2, 5));
// ['two', 'three', 'four', 'five']
// Reverse works by switching the argument position
Array.from(map.values(5, 2));
// ['five', 'four', 'three', 'two']
MIT. See LICENSE
FAQs
A performant, in-memory, immutable B+ tree data structure
The npm package ibtree receives a total of 9 weekly downloads. As such, ibtree popularity was classified as not popular.
We found that ibtree demonstrated a not healthy version release cadence and project activity because the last version was released a year ago. It has 1 open source maintainer collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Security News
GitHub removed 27 malicious pull requests attempting to inject harmful code across multiple open source repositories, in another round of low-effort attacks.
Security News
RubyGems.org has added a new "maintainer" role that allows for publishing new versions of gems. This new permission type is aimed at improving security for gem owners and the service overall.
Security News
Node.js will be enforcing stricter semver-major PR policies a month before major releases to enhance stability and ensure reliable release candidates.