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