tiny-tree

Efficient, no-dependency b-tree and binary search tree for node or the browser

Usage no npm install needed!

<script type="module">
  import tinyTree from 'https://cdn.skypack.dev/tiny-tree';
</script>

README

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 -