TinyTree

TinyTree is a zero-dependency library that efficiently searches for uniquely-identified items in a range. It includes two implementations with different performance characteristics. ArrayTree provides extremely fast access for data that rarely changes. BTree provides slightly slower access but performs well with highly volatile data.

Both trees expose the same API, so you can use them interchangeably.

Motivation

Let's say you have a list of customers, and you want to find everyone with id between 320 and 400. If you had your customers in a database, you might write a query like SELECT * from customers where id >=320 and id <= 400;. If you wanted this query to run fast, you'd create an index on the id field.

TinyTree provides this kind of indexed lookup for JavaScript objects.

One way to do this is to create an array that is sorted by id. Then you can use binary search to find quickly find the items you want. This is roughly what ArrayTree does, but it includes a number of methods to make these queries more convenient to write and provides methods for modifying the list.

Sorted arrays perform extremely well for searches, but they are expensive to update, especially if you are inserting items in the middle. BTree provides a performant alternative for volatile data based on the B-Tree data structure.

Usage

Creating a new tree

// Node.js
const tinyTree = require("tiny-tree"); // or import {ArrayTree, BTree} from "tiny-tree" if you're using ES modules
const bTree = new tinyTree.BTree();
const arrayTree = new tinyTree.ArrayTree();

<!--Browser-->
<script type="text/javascript" src="tiny-tree.js"></script>
<script type="text/javascript">
  const bTree = new tinyTree.BTree();
  const arrayTree = new tinyTree.ArrayTree();
</script>

Options

const tree = new BTree({degree: 17});

BTree can create trees of any degree; by default, trees are of degree 15, which provides reasonable performance most of the time. You can change this by passing options to the constructor:

• degree (integer; default 15; min 3)—determines how many items are stored at each node. See the performance section below for guidance on setting the degree.

ArrayTree does not take any options.

Adding/replacing entries

tree.set(key, value);

Keys must be strings or numbers. They are compared with javascript's default comparison operators (<, >, =, etc).

Values can be any data type.

Bulk loading items

let mySortedData = [
  ["key-a", "value-for-key-a"],
  ["key-b", "value-for-key-b"],
  ["key-c", "value-for-key-c"],
  ["key-d", "value-for-key-d"],
];

tree.bulkLoad(mySortedData);

You can get substantially better loading time by bulk loading a sorted list of entries. Bulk loading is only allowed on empty trees.

The data must be a sorted array of key/value arrays as shown in the example.

For BTrees, bulk loading also leads to better query performance (roughly 50%) and memory usage.

Removing entries

tree.delete(key);

Removing all entries

tree.clear();

Getting a single value by key or index

tree.get(key);
// returns value for the given key or `undefined` if no value has been set for this key

tree.getByIndex(4); // get the fifth entry from the sorted entries

Both functions return undefined if the index or key is not in the tree.

Getting all entries in order

// get all entries
tree.toArray();
// output [["key-a", "value-a"], ["key-b", "value-b"], ["key-c", "value-c"], ...]

// get all values (no keys)
tree.toArray(null, true);
// output ["value-a", "value-b", "value-c", ...]

Note that the first argument to toArray is an optional bounds (see below).

Getting values only is substantially faster than getting keys and values together. See the Performance section for more information.

Getting a range of entries based on key

// get all entries where key >= "key-a" and key < "key-c"
let bounds = {min: "key-a", max: "key-c"};
tree.toArray(bounds);
// output [["key-a", "value-a"], ["key-b", "value-b"]]

// get just values where key >= "key-a" and key < "key-c"
let bounds = {min: "key-a", max: "key-c"};
tree.toArray(bounds, true);
// output ["value-a", "value-b"]

You can limit your results to just the keys in a certain range. BTrees and ArrayTrees are especially well-suited to this kind of query.

tree.toArray(bounds optional object, valuesOnly optional boolean)—get key/value pairs or values based on bounds.

When setting bounds, min is inclusive and max is exclusive. If you need to change this behavior, set minExclusive and/or maxInclusive instead. All min/max properties are optional. It is equivalent to set min/minInclusive and max/maxExclusive.

Examples:

• {min: 100, max: 200}: 100 ≤ key < 200
• {minInclusive: 100, max: 200}: 100 ≤ key < 200
• {minExclusive: 100, max: 200}: 100 < key < 200
• {min: 100, maxInclusive: 200}: 100 ≤ key ≤ 200
• {min: 100}: 100 ≤ key
• {max: 200}: 200 < key

Getting a range of entries based on index (sort position)

// get the top two entries
tree.toArrayByIndex(0, 2, true);
// output ["value-a", "value-b"]

// get the bottom two entries
tree.toArrayByIndex(tree.size - 3, 2, true);
// output ["value-y", "value-z"]

tree.toArrayByIndex(start integer, count integer, valuesOnly optional boolean)

This works very much like toArray, but instead of querying by key, you are querying by sort position. This is useful for determining the top N or bottom N entries.

Size and other statistics

tree.size; // get total number of values stored

tree.getStats(); // get detailed information about the BTree

If you are trying to tune your tree for performance, detailed statistics might be helpful.

For BTree, getStats returns an object with the following fields:

• degree—the BTree's degree, as set in the constructor.
• size—the total number of values stored. This is the same value as tree.size.
• depth—the depth of the tree structure. Deeper trees can take longer to traverse. In general, trees with higher degrees will be shallower.
• fillFactor—the proportion of keys that are non-empty. A fillFactor of 1 means that all keys are filled and there is no empty space. For a large tree with random data, values of 0.6 to 0.7 are typical.
• nodes—the total number of nodes in the tree. In general, trees with higher degrees will need fewer nodes.
• saturationFactor—the proportion of nodes that are completely filled. Adding keys to a saturated node will cause the tree to rebalance. Conversely, trees with a low saturation factor can accommodate new entries with higher performance. In general, trees of higher degree have a lower saturation factor.
• keySlots—the total number of keys that the tree can store with its current node configuration.
• filledKeySlots—the number of these slots that are filled. Note that fillFactor = filledKeySlots / keySlots.
• saturatedNodes—the number of saturated nodes. Note that saturationFactor = saturatedNodes / nodes.

For ArrayTree, getStats is included mostly for compatibility and returns an object with the following field:

• size—the total number of values stored. This is the same value as tree.size.

Performance

Performance is highly dependent on your data and access patterns, but there are some general rules that can help.

• For gets and queries, ArrayTree is always faster than BTree, in some cases by more than 50x. If your data doesn't change much, you should use ArrayTree.
• If your data changes a lot, you should use BTree. If you have more than 50,000 items or so with lots of adds and removes, ArrayTree may be unusably slow.
• For queries, you should use valuesOnly = true if possible. For ArrayTree, this provides an enormous performance benefit (often 10x). For BTree, the performance boost is modest (typically around 5%).
• For both ArrayTree and BTree, bulk loads are always faster and provide equal or better query performance. If you can bulk load your data, you should.

BTree Benchmarks

For BTrees, degree affects performance in a complicated way that depends on how you access data (especially the number of items you query at a time). Up to a point, higher-degree trees have slower inserts/deletes but faster lookups. The following table also illustrates the substantial benefits of bulk loading.

On a 2017 15" MacBook Pro, here are operations per second for typical operations.

Test	Degree 3	Degree 7	Degree 15	Degree 31	Degree 63
Bulk load 10,000 items	142 ops/s	232 ops/s	216 ops/s	159 ops/s	91 ops/s
Fill factor	99.9%	99.8%	99.7%	99.5%	99.0%
Depth	9	5	4	3	3
Get 1000 items by key	2,329 ops/s	2,855 ops/s	2,469 ops/s	1,887 ops/s	985 ops/s
Get 1000 items by index	5,317	8,659	11,038	12,504	9,649
Query 1000 ranges of size 100 by key	212	336	352	327	237
Query 1000 ranges of size 100 by index	259	446	521	465	427
Query 1000 ranges of size 1000 by key	28	50	61	60	64
Query 1000 ranges of size 1000 by index	29	51	64	72	75
Load 10,000 items in random order	82 ops/s	150 ops/s	162 ops/s	133 ops/s
Fill factor	67.0%	68.3%	69.4%	69.2%	69.5%
Depth	11	6	4	3	3
Get 1000 items by key	2,289 ops/s	2,646 ops/s	2,392 ops/s	1,749 ops/s	1,131 ops/s
Get 1000 items by index	3,932	7,443	9,708	10,981	8,889
Query 1000 ranges of size 100 by key	132 ops/s	233 ops/s	274 ops/s	273 ops/s	218 ops/s
Query 1000 ranges of size 100 by index	148	284	363	410	357
Query 1000 ranges of size 1000 by key	17	33	43	50	51
Query 1000 ranges of size 1000 by index	17	34	45	53	58
Bulk load 1,000,000 items	0.57 ops/s	0.74 ops/s	0.72 ops/s	0.57 ops/s	0.42 ops/s
Fill factor	100%	100%	100%	100%	100%
Depth	13	8	6	5	4
Get 1000 items by key	329 ops/s	420 ops/s	305 ops/s	186 ops/s	114 ops/s
Get 1000 items by index	1,694	2,518	2,875	2,620	2,092
Query 1000 ranges of size 100 by key	49	84	86	69	46
Query 1000 ranges of size 100 by index	61	146	229	342	294
Query 1000 ranges of size 1000 by key	7.1	16	23	27	22
Query 1000 ranges of size 1000 by index	7.5	18	29	37	41
Load 1,000,000 items in random order	0.17 ops/s	0.25 ops/s	0.25 ops/s	0.21 ops/s	0.15 ops/s
Fill factor	67.0%	68.1%	68.6%	69.2%	69.4%
Depth	16	9	6	5	4
Get 1000 items by key	310 ops/s	386 ops/s	354 ops/s	226 ops/s	147 ops/s
Get 1000 items by index	614	1,542	1,998	2,271	2,364
Query 1000 ranges of size 100 by key	22	48	68	66	51
Query 1000 ranges of size 100 by index	24	60	116	171	221
Query 1000 ranges of size 1000 by key	2.7	6.7	13	16	20
Query 1000 ranges of size 1000 by index	2.8	6.9	14	22	29

BTree vs ArrayTree benchmarks

ArrayTree provides very close to the theoretical best-case performance for queries. If your data changes rarely, you can get an enormous boost in performance by using it. Also, if your data is fairly small (less than 10,000 items), you should consider using it even if your data is volatile, provided that queries are significantly more common than updates.

ArrayTree is especially efficient at getting contiguous arrays of values, where it achieves nearly the same performance as raw array access.

Test	BTree (degree 15)	ArrayTree	Speedup (slowdown)
Bulk load 10k items, add/remove 5k items	71 ops/s	37 ops/s	(1.9x)
Get 1000 items by key	2,100	3,700	1.8x
Get 1000 items by index	9,800	540,000	55x
Query 1000 ranges of size 100 by key	300	1,500	5x
Query 1000 ranges of size 100 by index	450	12,000	34x
Query 1000 ranges of size 1000 by key	55	730	13x
Query 1000 ranges of size 1000 by index	59	1,400	24x
Bulk load 100k items, add/remove 50k items	3.0 ops/s	0.07 ops/s	(42x)
Get 1000 items by key	880	1,600	1.8x
Get 1000 items by index	4,700	300,000	64x
Query 1000 ranges of size 100 by key	130	430	3.3x
Query 1000 ranges of size 100 by index	340	1,900	5.6x
Query 1000 ranges of size 1000 by key	31	160	5.2x
Query 1000 ranges of size 1000 by index	41	580	14x
Bulk load 1M items, add/remove 500k items	0.16 ops/s	Did not finish	-
Get 1000 items by key	305	n/a	-
Get 1000 items by index	2,069	n/a	-
Query 1000 ranges of size 100 by key	71	n/a	-
Query 1000 ranges of size 100 by index	150	n/a	-
Query 1000 ranges of size 1000 by key	17	n/a	-
Query 1000 ranges of size 1000 by index	20	n/a	-