Hey Motoko devs 
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
stablewith 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).
