sorted-btree
Advanced tools
A sorted list of key-value pairs in a fast, typed in-memory B+ tree with a powerful API.
B+ trees are ordered collections of key-value pairs, sorted by key.
This is a fast B+ tree implementation, largely compatible with the standard Map, but with a much more diverse and powerful API. To use it, import BTree from 'sorted-btree'.
BTree is faster and/or uses less memory than other popular JavaScript sorted trees (see Benchmarks). However, data structures in JavaScript tend to be slower than the built-in Array and Map data structures in typical cases, because the built-in data structures are mostly implemented in a faster language such as C++. Even so, if you have a large amount of data that you want to keep sorted, the built-in data structures will not serve you well, and BTree offers features like fast cloning that the built-in types don't.
Use npm install sorted-btree in a terminal to install it in your npm-based project.
I'm writing this on March 24, 2022: the one-month anniversary of the full-scale invasion of Ukraine.
This is the city of Mariupol, which Russia badly damaged after cutting off electricity, water and heat on March 1. Pre-war population: 431,859. Do you see any military targets here? No, these are homes that many people still live in. Russia has even made it dangerous to leave. An official told NPR: 'When the people organised in evacuation points, they [Russians] started attack on evacuation points. Not all the city. Just evacuation points.'
Officially, as of 9 days ago, 2,400 civilians had been killed, but this is said to be an underestimate and the actual number of murders may have been as high as 20,000... nine days ago.
Now, I'm just a lowly programming-language designer with no real following on Twitter, so I'm venting here.
I have donated to the Red Cross in support of Ukraine, and also to AVD-Info and Meduza in order to help give Russians access to information (the Russian internet is heavily censored, and independent media are banned). For more donation ideas, see here. Personally, I would like people to ask their government to offer large rewards to those who desert from the Russian military (plus large rewards for delivering Russian military hardware to Ukraine). The free world is already spending billions of dollars on military aid to Ukraine, but buying out soldiers can be cheaper than killing them. For talented Russian professionals, rewards should be offered for leaving Russia. Bring a brain drain to Putinland.
Without electricity, reports from Mariupol have been limited, but certainly there is enough information to see that the situation is very bad.
Here you can see the famous Donetsk Academic Regional Drama Theatre, labeled "дети" ("children") in huge letters, which held over 1,000 civilians. Russia bombed it anyway.
For more images and stories from Mariupol, see here.
Meanwhile, I hope you don't live in an apartment in Borodyanka, near Kyiv...
Or in these other places...
Edit: an image from Kharkiv was flagged as "in violation of the npm Service's Acceptable Use rules" but serves as a reminder that the direct death toll caused by the invasion will probably exceed 100,000 in 2022 alone.
What's that? You just wanted a B+ tree? Well, you're in for a treat.
Symbol.iterator is not required but is used if defined.)BTree was written in TypeScript)Map with methods such as size(), clear(),
forEach((v,k,tree)=>{}), get(K), set(K,V), has(K), delete(K),
plus iterator functions keys(), values() and entries().Date,
and objects that have a valueOf() method that returns a number or string.with and without, which return a
modified tree without changing the original (in O(log(size)) time).undefined is associated
with all keys in a given node.Range methods for batch operationsNaN as a key, but infinity is allowed.t.setIfNotPresent(k,v)t.changeIfPresent(k,v)for (pair of t.entriesReversed()) {}for (let p of t.entries(first)) {}t.toArray(), t.keysArray(), t.valuesArray()t.getRange(loK, hiK, includeHi)t.deleteRange(loK, hiK, includeHi)t.forEachPair((key, value, index) => {...})t.forRange(lowKey, highKey, includeHiFlag, (k,v) => {...})c = t.forRange(loK, hiK, includeHi, undefined)t.minKey(), t.maxKey()k: t.nextHigherKey(k), t.nextHigherPair(k)k: t.nextLowerKey(k), t.nextLowerPair(k)t.freeze() (you can also t.unfreeze())t.clone()t.diffAgainst(otherTree, ...)Note: Confusingly, the ES6 Map.forEach(c) method calls c(value,key) instead of c(key,value), in contrast to other methods such as set() and entries() which put the key first. I can only assume that they reversed the order on the hypothesis that users would usually want to examine values and ignore keys. BTree's forEach() therefore works the same way, but there is a second method .forEachPair((key,value)=>{...}) which sends you the key first and the value second; this method is slightly faster because it is the "native" for-each method for this class.
Note: Duplicate keys are not allowed (supporting duplicates properly is complex).
The "scanning" methods (forEach, forRange, editRange, deleteRange) will normally return the number of elements that were scanned. However, the callback can return {break:R} to stop iterating early and return a value R from the scanning method.
t.filter((k,v) => k.fitsCriteria())t.mapValues((v,k) => v.toString())t.reduce((acc, pair) => acc+pair[1], 0)t.with(key, value)t.withPairs([[k1,v1], [k2,v2]])t.withKeys([k1,k2])t.without(key)t.withoutKeys(keys)t.withoutRange(low, high, includeHi)Things to keep in mind: I ran a test which suggested t.with is three times slower than t.set. These methods do not return a frozen tree even if the original tree was frozen (for performance reasons, e.g. frozen trees use slightly more memory.)
Given a set of {name: string, age: number} objects, you can create a tree sorted by name and then by age like this:
// First constructor argument is an optional list of pairs ([K,V][])
var tree = new BTree(undefined, (a, b) => {
if (a.name > b.name)
return 1; // Return a number >0 when a > b
else if (a.name < b.name)
return -1; // Return a number <0 when a < b
else // names are equal (or incomparable)
return a.age - b.age; // Return >0 when a.age > b.age
});
tree.set({name:"Bill", age:17}, "happy");
tree.set({name:"Fran", age:40}, "busy & stressed");
tree.set({name:"Bill", age:55}, "recently laid off");
tree.forEachPair((k, v) => {
console.log(`Name: ${k.name} Age: ${k.age} Status: ${v}`);
});
The reduce method performs a reduction operation, like the reduce method of Array. It is used to combine all keys, values or pairs into a single value, or to perform type conversions conversions. reduce is best understood by example. So here's how you can multiply all the keys in a tree together:
var product = tree.reduce((p, pair) => p * pair[0], 1)
It means "start with p=1, and for each pair change p to p * pair[0]" (pair[0] is the key). You may be thinking "hey, wouldn't it make more sense if the 1 argument came first?" Yes it would, but in Array the parameter is second, so it must also be second in BTree for consistency.
Here's a similar example that adds all values together:
var total = tree.reduce((sum, pair) => sum + pair[1], 0)
This final example converts the tree to a Map:
var map = tree.reduce((m, pair) => m.set(pair[0], pair[1]), new Map())`
Remember that m.set returns m, which is different from BTree where tree.set returns a boolean indicating whether a new key was added.
You can scan a range of items and selectively delete or change some of them using t.editRange. For example, the following code adds an exclamation mark to each non-boring value and deletes key number 4:
var t = new BTree().setRange([[1,"fun"],[2,"yay"],[4,"whee"],[8,"zany"],[10,"boring"]);
t.editRange(t.minKey(), t.maxKey(), true, (k, v) => {
if (k === 4)
return {delete: true};
if (v !== "boring")
return {value: v + '!'};
})
BTree includes a lattice of interface types representing subsets of BTree's interface. I would encourage other authors of map/dictionary/tree/hashtable types to utilize these interfaces. These interfaces can be divided along three dimensions:
I have defined several kinds of interfaces along the read/write access dimension:
ISetSource<K> and IMapSource<K,V>). At minimum, sources include a size property and methods get, has, forEach, and keys.ISetSink<K> and IMapSink<K,V>). At minimum, sinks have set, delete and clear methods.ISet<K> and IMap<K,V>).F (ISetF<K> and IMapF<K,V>).The Sorted interfaces extend the non-sorted interfaces with queries that only a sorted collection can perform efficiently, such as minKey() and nextHigherKey(k). At minimum, sorted interfaces add methods minKey, maxKey, nextHigherKey, nextLowerKey, and forRange, plus iterators that return keys/values/pairs in sorted order and accept a firstKey parameter to control the starting point of iteration.
Note: in sorted-btree ≤ v1.7.x, these interfaces have methods nextHigherKey(key: K) and nextLowerKey(key: K) which should be nextHigherKey(key: K|undefined) and nextLowerKey(key: K|undefined). These signatures are changed in the next version.
A map is a collection of keys with values, while a set is a collection of keys without values.
For the most part, each Set interface is a subset of the corresponding Map interface with "values" removed. For example, MapF<K,V> extends SetF<K>. An exception to this is that IMapSink<K, V> could not be derived from ISetSink<K> (and thus IMap<K,V> is not derived from ISet<K>) because the type V does not necessarily include undefined. Therefore you can write set.set(key) to add a key to a set, but you cannot write map.set(key) without specifying a value (in TypeScript this is true even if V includes undefined.)
All of these interfaces use any as the default type of K and V.
ISetSource<K>ISetSink<K>ISet<K> extends ISetSource<K>, ISetSink<K>IMapSource<K, V> extends ISetSource<K>IMapSink<K, V>IMap<K, V> extends IMapSource<K,V>, IMapSink<K,V>ISortedSetSource<K> extends ISetSource<K>ISortedSet<K> extends ISortedSetSource<K>, ISetSink<K>ISortedMapSource<K,V> extends IMapSource<K, V>, ISortedSetSource<K>ISortedMap<K,V> extends IMap<K,V>, ISortedMapSource<K,V>ISetF<K> extends ISetSource<K>IMapF<K, V> extends IMapSource<K,V>, ISetF<K>ISortedSetF<K> extends ISetF<K>, ISortedSetSource<K>ISortedMapF<K,V> extends ISortedSetF<K>, IMapF<K,V>, ISortedMapSource<K,V>If the lattice were complete there would be 16 interfaces (4*2*2). In fact there are only 14 interfaces because ISortedMapSink<K,V> and ISortedSetSink<K, V> don't exist, because sorted sinks are indistinguishable from unsorted sinks.
BTree<K,V> implements all of these interfaces except ISetSink<K>, ISet<K>, and ISortedSet<K>. However, BTree<K,V> may be compatible with these interfaces even if TypeScript doesn't realize it. Therefore, if V includes undefined, the BTree<K,V>.asSet property is provided to cast the BTree to a set type. The asSet property returns the same BTree as type ISortedSet<K> (which is assignable to ISetSink<K>, ISet<K> and ISortedSetSource<K>).
The IMap<K,V> interface is compatible with the ES6 Map<K,V> type as well as BTree<K,V>. In order to accomplish this, compromises had to be made:
set(k,v) method returns any for compatibility with both BTree and Map, since BTree returns boolean (true if an item was added or false if it already existed), while Map returns this.Map.forEach(c) method calls c(value,key) instead of c(key,value), unlike all other methods which put the key first. Therefore IMap works the same way. Unfortunately, this means that ISetSource<K>, the supertype of IMapSource<K,V>, cannot sanely have a forEach method because if it did, the first parameter to the callback would be unused.setPairs, deletePairs and reduce are left out because they are not defined by Map. Instead, these methods are defined in ISortedMap<K,V>.reduce, filter and mapValues are not included in IMap, but they are defined in IMapF<K,V> and (except mapValues) ISetF<K>.Similarly, ISet<K> is compatible with ES6 Set. Again there are compromises:
set method is renamed add in Set and ISet<K>, so add exists on BTree.prototype as a synonym for set.forEach method for reasons alluded to above. Use keys() instead.filter or reduce because Set doesn't support them.Although BTree<K,V> doesn't directly implement ISet<K>, it does implement ISetSource<K> and it is safe to cast BTree<K,V> to ISet<K> or ISortedSet<K> provided that V is allowed to be undefined.
BTree is 3 to 5 times faster than SortedMap and SortedSet in the collections packageBTree has similar speed to RBTree at smaller sizes, but is faster at very large sizes and uses less memory because it packs many keys into one array instead of allocating an extra heap object for every key.functional-red-black-tree is remarkably fast for a persistent tree, but BTree should require less memory unless you frequently use clone/with/without and are saving snapshots of the old tree to prevent garbage collection.Map), although in JavaScript this is not guaranteed because the B+ tree's memory efficiency depends on avoiding wasted space in the arrays for each node, and JavaScript provides no way to detect or control the capacity of an array's underlying memory area. Also, Map should be faster because it does not sort its keys.SortedArray<K,V>, a wrapper class for an array of [K,V] pairs. Benchmark results were not gathered for sorted arrays with one million elements (it takes too long)0.8 Insert 1000 pairs in sorted-btree's BTree
0.4 Insert 1000 pairs in sorted-btree's BTree set (no values)
2.5 Insert 1000 pairs in collections' SortedMap
1.6 Insert 1000 pairs in collections' SortedSet (no values)
0.7 Insert 1000 pairs in functional-red-black-tree
0.5 Insert 1000 pairs in bintrees' RBTree (no values)
8.6 Insert 10000 pairs in sorted-btree's BTree
5.1 Insert 10000 pairs in sorted-btree's BTree set (no values)
37.8 Insert 10000 pairs in collections' SortedMap
25.8 Insert 10000 pairs in collections' SortedSet (no values)
8.7 Insert 10000 pairs in functional-red-black-tree
5.4 Insert 10000 pairs in bintrees' RBTree (no values)
95.9 Insert 100000 pairs in sorted-btree's BTree
69.1 Insert 100000 pairs in sorted-btree's BTree set (no values)
564 Insert 100000 pairs in collections' SortedMap
366.5 Insert 100000 pairs in collections' SortedSet (no values)
192.5 Insert 100000 pairs in functional-red-black-tree
107.3 Insert 100000 pairs in bintrees' RBTree (no values)
1363 Insert 1000000 pairs in sorted-btree's BTree
909 Insert 1000000 pairs in sorted-btree's BTree set (no values)
8783 Insert 1000000 pairs in collections' SortedMap
5443 Insert 1000000 pairs in collections' SortedSet (no values)
3356 Insert 1000000 pairs in functional-red-black-tree
1581 Insert 1000000 pairs in bintrees' RBTree (no values)
0.6 Insert 1000 sorted pairs in B+ tree
0.4 Insert 1000 sorted keys in B+ tree set (no values)
0.6 Insert 1000 sorted pairs in collections' SortedMap
0.4 Insert 1000 sorted keys in collections' SortedSet (no values)
0.7 Insert 1000 sorted pairs in functional-red-black-tree
0.5 Insert 1000 sorted keys in bintrees' RBTree (no values)
1 Delete every second item in B+ tree
3 Delete every second item in B+ tree set
1 Bulk-delete every second item in B+ tree set
1 Delete every second item in collections' SortedMap
1 Delete every second item in collections' SortedSet
5 Delete every second item in functional-red-black-tree
10 Delete every second item in bintrees' RBTree
6.5 Insert 10000 sorted pairs in B+ tree
3.9 Insert 10000 sorted keys in B+ tree set (no values)
6.5 Insert 10000 sorted pairs in collections' SortedMap
3.9 Insert 10000 sorted keys in collections' SortedSet (no values)
12.4 Insert 10000 sorted pairs in functional-red-black-tree
5.8 Insert 10000 sorted keys in bintrees' RBTree (no values)
4 Delete every second item in B+ tree
4 Delete every second item in B+ tree set
3 Bulk-delete every second item in B+ tree set
13 Delete every second item in collections' SortedMap
7 Delete every second item in collections' SortedSet
8 Delete every second item in functional-red-black-tree
6 Delete every second item in bintrees' RBTree
75.9 Insert 100000 sorted pairs in B+ tree
45 Insert 100000 sorted keys in B+ tree set (no values)
98.7 Insert 100000 sorted pairs in collections' SortedMap
61.4 Insert 100000 sorted keys in collections' SortedSet (no values)
145.8 Insert 100000 sorted pairs in functional-red-black-tree
82.6 Insert 100000 sorted keys in bintrees' RBTree (no values)
79 Delete every second item in B+ tree
52 Delete every second item in B+ tree set
18 Bulk-delete every second item in B+ tree set
166 Delete every second item in collections' SortedMap
58 Delete every second item in collections' SortedSet
64 Delete every second item in functional-red-black-tree
74 Delete every second item in bintrees' RBTree
700 Insert 1000000 sorted pairs in B+ tree
452.5 Insert 1000000 sorted keys in B+ tree set (no values)
1069 Insert 1000000 sorted pairs in collections' SortedMap
864 Insert 1000000 sorted keys in collections' SortedSet (no values)
1531 Insert 1000000 sorted pairs in functional-red-black-tree
966 Insert 1000000 sorted keys in bintrees' RBTree (no values)
435 Delete every second item in B+ tree
291 Delete every second item in B+ tree set
159 Bulk-delete every second item in B+ tree set
1447 Delete every second item in collections' SortedMap
796 Delete every second item in collections' SortedSet
573 Delete every second item in functional-red-black-tree
537 Delete every second item in bintrees' RBTree
0.5 Insert 1000 pairs in sorted array
0.6 Insert 1000 pairs in B+ tree
0.1 Insert 1000 pairs in ES6 Map (hashtable)
13.2 Insert 10000 pairs in sorted array
7.2 Insert 10000 pairs in B+ tree
1.3 Insert 10000 pairs in ES6 Map (hashtable)
56980 Insert 100000 pairs in sorted array
122 Insert 100000 pairs in B+ tree
17.7 Insert 100000 pairs in ES6 Map (hashtable)
SLOW! Insert 1000000 pairs in sorted array
1354 Insert 1000000 pairs in B+ tree
304.5 Insert 1000000 pairs in ES6 Map (hashtable)
0.4 Insert 1000 sorted pairs in array
0.6 Insert 1000 sorted pairs in B+ tree
0.1 Insert 1000 sorted pairs in Map hashtable
0 Sum of all values with forEach in sorted array: 27350180
0 Sum of all values with forEachPair in B+ tree: 27350180
0 Sum of all values with forEach in B+ tree: 27350180
0 Sum of all values with iterator in B+ tree: 27350180
0 Sum of all values with forEach in Map: 27350180
0.1 Delete every second item in sorted array
0.1 Delete every second item in B+ tree
0 Delete every second item in Map hashtable
3.9 Insert 10000 sorted pairs in array
6.7 Insert 10000 sorted pairs in B+ tree
1.3 Insert 10000 sorted pairs in Map hashtable
0.2 Sum of all values with forEach in sorted array: 2716659330
0.3 Sum of all values with forEachPair in B+ tree: 2716659330
0.4 Sum of all values with forEach in B+ tree: 2716659330
0.3 Sum of all values with iterator in B+ tree: 2716659330
0.2 Sum of all values with forEach in Map: 2716659330
1.2 Delete every second item in sorted array
1.1 Delete every second item in B+ tree
0.3 Delete every second item in Map hashtable
68.4 Insert 100000 sorted pairs in array
72.7 Insert 100000 sorted pairs in B+ tree
18.4 Insert 100000 sorted pairs in Map hashtable
2.5 Sum of all values with forEach in sorted array: 275653049020
3.3 Sum of all values with forEachPair in B+ tree: 275653049020
4.5 Sum of all values with forEach in B+ tree: 275653049020
2.8 Sum of all values with iterator in B+ tree: 275653049020
2.2 Sum of all values with forEach in Map: 275653049020
2420 Delete every second item in sorted array
14.4 Delete every second item in B+ tree
3.7 Delete every second item in Map hashtable
969 Insert 1000000 sorted pairs in array
773 Insert 1000000 sorted pairs in B+ tree
305.5 Insert 1000000 sorted pairs in Map hashtable
25.3 Sum of all values with forEach in sorted array: 27510295368690
32.4 Sum of all values with forEachPair in B+ tree: 27510295368690
46.1 Sum of all values with forEach in B+ tree: 27510295368690
29.9 Sum of all values with iterator in B+ tree: 27510295368690
22 Sum of all values with forEach in Map: 27510295368690
SLOW! Delete every second item in sorted array
305.5 Delete every second item in B+ tree
95.6 Delete every second item in Map hashtable
ISortedSetSource.nextHigherKey(key: K) changed to key?: KISortedSetSource.nextLowerKey(key: K) changed to key?: KISortedMapSource.nextHigherPair(key: K) changed to key?: KISortedMapSource.nextLowerPair(key: K) changed to key?: KasSet method, defined as follows: asSet<K,V>(btree: BTree<K,V>): undefined extends V ? ISortedSet<K> : unknown { return btree as any; }BTree.getPairOrNextLower and BTree.getPairOrNextHigher methods (PR #23)reusedArray to nextHigherPair and nextLowerPair (PR #23)diffAgainst (PR #24) and nextLowerPair (PR #23)BTree.diffAgainst method (PR #16)simpleComparator function (PR #15)defaultComparator (PR #15) to support edge cases better. Most notably, heterogenous key types will no longer cause trouble such as failure to find keys that are, in fact, present in the tree. BTree is slightly slower using the new default comparator, but the benchmarks above have not been refreshed. For maximum performance, use simpleComparator or a custom comparator as the second constructor parameter. The simplest possible comparator is (a, b) => a - b, which works for finite numbers only.nextLowerPair(0) was being treated like nextLowerPair(undefined), and nextLowerPair(undefined) was returning the second-highest pair when it should have returned the highest pair.typings option in package.json so that tsc works for end-usersisEmpty property getternextHigherPair, nextHigherKey, nextLowerPair, nextLowerKey methodseditAll, which is like editRange but touches all keysdeleteKeys for deleting a sequence of keys (iterable)with, withPairs, withKeys, without, withoutKeys, withoutRangefilter, reduce, mapValuesgreedyClone for cloning nodes immediately, to avoid marking the original tree as shared which slows it down.entries/entriesReversedsetRange to setPairs for logical consistency with withoutPairs and withoutRange. The old name is deprecated but added to the prototype as a synonym. setPairs returns the number of pairs added instead of this.EmptyBTree, a frozen empty tree♥ This package was made to help people learn TypeScript & React.
Are you a C# developer? You might like the similar data structures I made for C# (BDictionary, BList, etc.), and other dynamically persistent collection types.
You might think that the package name "sorted btree" is overly redundant, but I did make a data structure similar to B+ Tree that is not sorted. I called it the A-List (C#). But yeah, the names btree and bplustree were already taken, so what was I supposed to do, right?
FAQs
A sorted list of key-value pairs in a fast, typed in-memory B+ tree with a powerful API.
The npm package sorted-btree receives a total of 4,857 weekly downloads. As such, sorted-btree popularity was classified as popular.
We found that sorted-btree 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.