btreejs

A ridiculously lean B-tree of variable orders in plain JavaScript. Closure-compiled using advanced optimizations, 100% typed code.

  • Supports variable orders
  • Implemented in plain JavaScript
  • Compiled with ClosureCompiler.js using advanced optimizations
  • Zero vebose warnings and errors, 100% typed code
  • Zero dependencies
  • Type checking reduced to the absolute minimum (everything else is left to you)
  • Exposes only the bare minimum to the outside world

npm install btreejs

var btree = require("btreejs");
var Tree = btree.create(2, btree.numcmp);
var tree = new Tree();
tree.put(0, "null");
tree.put(1, "one");
tree.put(2, "two");
tree.del(1);
tree.get(2); // == "two" 
...

Creates and returns a Tree class of the specified order with the specified comparator.

ParameterFunction
orderOrder of the Tree-class to build as a number. Defaults to 2.
comparefunction(a: *, b: *):number returning -1 if a<b, 1 if a>b and 0 otherwise. Defaults to btree.numcmp

Numeric comparator.

Strict string comparator that compares strings character by character.

Constructs a Tree instance of the order specified to btree.create previously.

Puts a non-undefined, non-null key with the given non-undefined value into the tree. You have to type check keys on your own.

Gets the value of the specified key. Returns undefined if the key does not exist. There is no Tree#exists method or similar because it just would encourage multiple lookups if one is already sufficient. So the correct usage is:

var value = tree.get(myKey);
if (typeof value == 'undefined') {
    // Key does not exist 
} else {
    // Key exists, value may be null 
}

Deletes a key from the tree. Returns true on success or false if there is no such key.

Walks the range [minKey, ..., maxKey] in ascending order by calling the callback for every key/value pair found.

ParameterFunction
minKeyMinimum key or null to start at the beginning
maxKeyMaximum key or null to walk till the end
callbackfunction(key:, value:):undefined|boolean

To break the loop, let callback explicitly return true.

Walks the range [minKey, ..., maxKey] in descending order by calling the callback for every key/value pair found.

Counts the number of keys in the range [minKey, ..., maxKey]. See Tree#walk.

Note: Tree#put, Tree#get and Tree#del throw an Error only if the key is undefined or null or the value is undefined. Other methods do not throw.

The test suite contains a 100k benchmark:

Ran in node v0.10.5 on one core of an 3.40Ghz Intel Core i7-2600K working with premium DDR3 ram (I'm too lazy to look up the exact model). To test on your own hardware, simply run npm [-g] install testjs && npm test.

testjs itself is an optimized wrapper around node's native assert module.

Also includes a cluster-based (runs in a dedicated worker) optimizer in tests/optimize.js that takes ranges of orders to calculate the optimal order for a specific tree size:

The times parameter specifies how many benchmarks for each order shall be run to eliminate random peeks and is responsible for how long a test takes. Results may vary depending on the actual hardware configuration used. Beware: The default settings that have been used to find btree's default order of 52 (orders 0 to 200, 100k items, 20 times) will take a while to process.

Apache License, Version 2.0