(Heap-based) BTreeMap library for Motoko

Hey Motoko devs :wave:

Just wanted to introduce to you a BTreeMap library that I’ve been picking away at over the past few months.

Contributions and feature requests welcome!

What’s a BTree?

  • Think of this like a much more memory efficient Red-Black Tree. A common BTree use case you may have seen is in the indexes of SQL and NoSQL databases in order to support range queries.

What’s a Red-Black Tree?

  • Both a BTree and RBTree are self balancing data structures that keep data in a sorted format, for more on BTrees → wiki & interactive visualizer.

Why is it called StableHeapBTreeMap?

  • This library lives in heap memory, but is written such that it if declared stable with stable types, it will persist across canister upgrades (serialized to/from stable memory during the canister upgrade process) without the need for a pre or post-upgrade hook.

Here’s just a few examples of how to use this library:

import BTree "mo:btree/BTree";
// initialize the BTree
let t = BTree.init<Text, Nat>(?32); // choose an order anywhere between 4 and 512, defaults to 8

// initialize from an array or buffer (similar methods for toArray/toBuffer)
let t = BTree.fromArray<Text, Nat>(32, Text.compare, array);
let t = BTree.fromBuffer<Text, Nat>(32, Text.compare, buffer);

// insert (write)
let originalValue = BTree.insert<Text, Nat>(t, Text.compare, "John", 52);

// paginate through a collection in ascending order grab first 10 and the next key
let { results; nextKey } = BTree.scanLimit<Text, Nat>(t, Text.compare, "A", "Z", #fwd, 10);

// get min element
let minElement = BTree.min<Text, Nat>(t);

And much more, head to the API documentation for more.

Also, for those who have been following the CanDB project, this library is replacing the current Red-Black tree in there, at which point the CanDB and it’s client libraries will be released publicly (target mid-late March).


Released v0.2.2 yesterday with a bugfix for scanLimit().

It’s a bug-fix and not a breaking change, so I recommend upgrading from v0.2.x to 0.2.2 as soon as you have the time :slight_smile:

1 Like

Have you measured how much more efficient it is? I would love to see some numbers/benchmarks.