bp_tree

An Erlang implementation of B+ tree.

Build

Dependencies:

• erlang >= 18.0
• make

Once you have all of the dependencies, simply run make in bp_tree directory to build it.

User Guide

Add bp_tree as a rebar dependency to your project:

{deps, [
  {bp_tree, "1.0.0", {git, "https://github.com/krzysztof-trzepla/bp_tree.git", {tag, "1.0.0"}}}
}.

API

In order to create a B+ tree a init function from a bp_tree module should be called. Overloaded init/1 function accepts following options:

• order - each node of a tree will hold up to 2 * order keys and 2 * order + 1 values (default: 50),
• store_module - the name of a tree store backend module (default: bp_tree_map_store),
• store_args - list of arguments that will be passed to init/1 function of store_module module (default: []).

A bp_tree module provides standard B+ tree operations:

• find/2 - search key in a tree and return associated value,
• insert/3 - store key-value pair in a tree (keys must be unique),
• remove/2 - remove key and associated value from a tree.

In addition to standard operations a fold operation is provided. It allows for iterating over B+ tree leaf in a similar fashion to lists:foldl/3 function. It accepts following options:

• start_key - key from which start iteration (inclusive), start_key takes precedence over offset (by default the leftmost - smallest - key),
• end_key - key on which stop iteration (inclusive) (by default the rightmost - largest - key),
• offset - distance from the leftmost key from which start iteration (default: 0),
• total_size - how many key in total should be iterated (by default return all nodes),
• batch_size - how many key should be iterated in terms of a batch (by default use single batch).

fold will iterate keys in batch if batch_size option is provided. For batch iteration a continuation token is returned which should be passed to an overloaded fold function in order to continue iteration. It is guaranteed that iterated keys are provided in a strictly increasing order, even if fold operation is interleaved with insert operations.

Tree store backend

The bp_tree uses bp_tree_store module to save, access and modify tree structure. The bp_tree_store uses yet another customizable module as a storage backend, which must implement bp_tree_store behaviour. Default bp_tree_store storage backend is bp_tree_map_store, which stores tree nodes in a map. There is also bp_tree_ets_store module that holds tree structure in an ETS. It is easy to add new storage by creating new module implementing bp_tree_store behaviour and passing its name as store_module option to init/1 function.

Test

$ make test