EEP 46: B-trees: balanced search trees of order n #

Abstract #

This EEP proposes the creation of a new module named b_trees for the administration of b-trees. Both the optional persistence and the sort order should be implemented by pluggable functionality.

Copyright #

This document has been placed in the public domain.

Specification #

Data Structure #

{MinimumSubtrees,
 MaximumKeys,
 SizeKeyValues,
 SortFunction/2,
 State,
 Tree}

Tree is composed of nodes of the form

{KeyNumber,
 SubtreeNumber,
 [{Key, Value}],
 [Tree]}

and the “empty b-tree” node

nil

State is a tuple composed of the following parameters:

{StateTarget,
 DeleteFunction/3,
 InsertFunction/3,
 LookupFunction/3}

Since the b-trees are always balanced, there is no need for a balance operation.

DATA TYPES #

b_tree() = {pos_integer(),
            pos_integer(),
            non_neg_integer(),
            sort_function(),
            state(),
            tree()}

A general balanced tree.

iterator() = [{key_values(), subtrees()}]

A general balanced tree iterator.

EXPORTS #

copy(Tree1, Tree2) -> Tree3 #

Types:

Tree1 = Tree2 = Tree3 = b_tree() | gb_trees:tree()

Copies tree Tree1 to an empty tree Tree2. Both trees may be either of type b-tree or binary tree (gb_trees). Returns the new tree Tree3 of the same type as tree Tree2.

delete(Key, B-Tree1) -> B-Tree2 #

Types:

Key = any()
B-Tree1 = B-Tree2 = b_tree()

Removes the node with key Key from b-tree B-Tree1 and returns the new b-tree B-Tree2. Assumes that key Key is present in b-tree B-Tree1, crashes otherwise.

delete_any (Key, B-Tree1) -> B-Tree2 #

Types:

Key = any()
B-Tree1 = B-Tree2 = b_tree()

Removes the node with key Key from b-tree B-Tree1 if key Key is present in b-tree B-Tree1, otherwise does nothing. Returns the new b-tree B-Tree2.

empty (Order) -> B-Tree #

Types:

Order = pos_integer()
B-Tree = b_tree()

Returns a new empty b-tree. The order is defined as the maximum number of children nodes a non-leaf node may hold.

enter (Key, Value, B-Tree1) -> B-Tree2 #

Types:

Key = any()
Value = any()
B-Tree1 = B-Tree2 = b_tree()

Inserts key Key with value Value into b-tree B-Tree1 if key Key is not present in b-tree B-Tree1, otherwise updates the current value of key Key to value Value in b-tree B-Tree1. Returns a new b-tree B-Tree2.

from_dict (B-Tree1, List) -> B-Tree2 #

Types:

B-Tree1 = B-Tree2 = b_tree()
List = [{Key, Value}]

Turns an ordered list List of key value tuples into a b-tree. The given b-tree B-Tree1 must be empty. The list must not contain duplicate keys.

get (Key, B-Tree) -> Value #

Types:

Key = any()
B-Tree = b_tree()
Value = any()

Retrieves the value stored with key Key in b-tree B-Tree. Assumes that key Key is present in b-tree B-Tree, crashes otherwise.

height (B-Tree) -> integer() >= 0 #

Types:

B-Tree = b_tree()

Returns the height of b-tree B-Tree as an integer. Assumes that b-tree B-Tree is non-empty.

insert (Key, Value, B-Tree1) -> B-Tree2 #

Types:

Key = any()
Value = any()
B-Tree1 = B-Tree2 = b_tree()

Inserts key Key with value Value into b-tree B-Tree1 and returns the new b-tree B-Tree2. Assumes that key Key is not present in b-tree B-Tree1, crashes otherwise.

is_defined (Key, B-Tree) -> boolean() #

Types:

Key = any()
B-Tree = b_tree()

Returns true if key Key is present in b-tree B-Tree, otherwise false.

is_empty (B-Tree) -> boolean() #

Types:

B-Tree = b_tree()

Returns true if b-tree B-Tree is an empty b-tree, otherwise false.

iterator (B-Tree) -> Iterator #

Types:

B-Tree = b_tree()
Iterator = iterator()

Returns iterator Iterator that can be used for traversing the entries of b-tree B-Tree; see next/1. The implementation of this iterator is very efficient; traversing the whole b-tree using next/1 is only slightly slower than getting the list of all key-value pairs using to_list/1 and traversing that. The main advantage of the iterator approach is that it does not require the complete list of all key-value pairs to be built in memory at one time.

iterator_from (Key, B-Tree) -> Iterator #

Types:

Key = any(9
B-Tree = b_tree()
Iterator = iterator()

Returns iterator Iterator that can be used for traversing the entries of b-tree B-Tree; see next/1. The difference, as compared to the iterator returned by iterator/1, is that the first key greater than or equal to key Key is returned.

keys (B-Tree) -> [Key] #

Types:

B-Tree = b_tree()
Key = any()

Returns the keys in b-tree B-Tree as an ordered list.

largest (B-Tree) -> {Key, Value} #

Types:

B-Tree = b_tree()
Key = any()
Value = any()

Returns a tuple {Key, Value}, where Key is the largest key in b-tree B-Tree, and Value is the value associated with this key. Assumes that b-tree B-Tree is not empty.

lookup (Key, B-Tree) -> none | {value, Value} #

Types:

Key = any()
B-Tree = b_tree()
Value = any()

Looks up key Key in b-tree B-Tree. Returns {value, Value}, or none if key Key is not present.

map (Function, B-Tree1) -> B-Tree2 #

Types:

Function = fun((Key, Value1) -> Value2)
B-Tree1 = B-Tree2 = b_tree()
Key = any()
Value1 = Value2 = any()

Maps function Function(Key, Value1) -> Value2 to all key value pairs of b-tree B-Tree1. Returns the new b-tree B-Tree2 with the same set of keys as b-tree B-Tree1 and the new set of values.

next (Iterator1) -> ‘none’ | {Key, Value, Iterator2} #

Types:

Iterator1 = Iterator2 = iterator()
Key = any()
Value = any()

Returns the tuple {Key, Value, Iterator2}, where Key is the smallest key referred to by iterator Iterator1, and iterator Iterator2 is the new iterator to be used for traversing the remaining nodes, or the atom ‘none’ if no nodes remain.

set_parameter (B-Tree1, Name, Value) -> B-Tree2 #

Types:

B-Tree1 = B-Tree2 = b_tree()
Name : Value = sort  : Function = fun((Key1, Key2) -> equal |
                                                      greater |
                                                      less)
             | state : {StateTarget,
                        Function = fun(StateTarget, delete, Key)
                                 -> true,
                        Function = fun(StateTarget, insert, Subtrees)
                                 -> Key,
                        Function = fun(StateTarget, lookup, Key)
                                 -> Subtrees}

Sets the parameter Name to value Value in the empty b-tree B-Tree1 and returns the new b-tree B-Tree2. This function can only be used in conjunction with an empty b-tree.

size_key_values (B-Tree) -> integer() >= 0 #

Types:

B-Tree = b_tree()

Returns the number of key value pairs in b-tree B-Tree as an integer. Returns 0 (zero) if b-tree B-Tree is empty.

size_nodes (B-Tree) -> {integer() >= 0, integer() >= 0} #

Types:

B-Tree = b_tree()

Returns the number of total nodes and the number of leaf nodes in b-tree B-Tree as a tuple of two integers. Returns {0, 0} (zero) if b-tree B-Tree is empty.

smallest (B-Tree) -> {Key, Value} #

Types:

B-Tree = b_tree()
Key = any()
Value = any()

Returns tuple {Key, Value}, where Key is the smallest key in b-tree B-Tree, and Value is the value associated with this key. Assumes that b-tree B-Tree is not empty.

sort_ascending (Key1, Key2) -> ‘equal’ | ‘greater’ | ‘less’ #

Types:

Key1 = Key2  = any()
equal = greater = less = atom()

Returns the atom ‘greater’ if Key1 > Key2, the atom ‘less’ if Key1 < Key2 and otherwise the atom ‘equal’.

sort_descending (Key1, Key2) -> ‘equal’ | ‘greater’ | ‘less’ #

Types:

Key1 = Key2  = any()
equal = greater = less = atom()

Returns the atom ‘less’ if Key1 > Key2, the atom ‘greater’ if Key1 < Key2 and otherwise the atom ‘equal’.

take(Key, B-Tree1) -> B-Tree2 #

Types:

Key = any()
B-Tree1 = B-Tree2 = b_tree()

Removes the node with key Key from b-tree B-Tree1 and returns the new b-tree B-Tree2. Assumes that key Key is present in b-tree B-Tree1, crashes otherwise.

take_largest (B-Tree1) -> {Key, Value, B-Tree2} #

Types:

B-Tree1 = B-Tree2 = b_tree()
Key = any()
Value = any()

Returns tuple {Key, Value, B-Tree2}, where Key is the largest key in b-tree B-Tree1, Value is the value associated with this key, and b-tree B-Tree2 is this b-tree with the corresponding key value pair deleted. Assumes that b-tree B-Tree1 is not empty.

take_smallest (B-Tree1) -> {Key, Value, B-Tree2} #

Types:

B-Tree1 = B-Tree2 = b_tree()
Key = any()
Value = any()

Returns tuple {Key, Value, B-Tree2}, where Key is the smallest key in b-tree B-Tree1, Value is the value associated with this key, and b-tree B-Tree2 is this b-tree with the corresponding key value pair deleted. Assumes that b-tree B-Tree1 is not empty.

to_list (B-Tree) -> [{Key, Value}] #

Types:

B-Tree = b_tree()
Key = any()
Value = any()

Converts b-tree B-Tree into an ordered list of key value tuples.

update (Key, Value, B-Tree1) -> B-Tree2 #

Types:

Key = any()
Value = any()
B-Tree1 = B-Tree2 = b_tree()

Updates key Key to value Value in b-tree B-Tree1 and returns the new b-tree B-Tree2. Assumes that key Key is present in b-tree B-Tree1.

values (B-Tree) -> [Value] #

Types:

B-Tree = b_tree()
Value = any()

Returns the values in b-tree B-Tree as an ordered list, sorted by their corresponding keys. Duplicates are not removed.

Pluggable Persistence Functionality #

Format #

{StateTarget, DeleteFunction, InsertFunction, LookupFunction}

StateTarget = any()

DeleteFunction(StateTarget, delete, Key) -> true

InsertFunction(StateTarget, insert, Subtrees) -> Key

LookupFunction(StateTarget, lookup, Key) -> Subtrees

Examples for state targets are a Dets table or a Mnesia table. The delete function takes a state target, the atom delete and a key as arguments and returns the atom true if successful. The insert function takes a state target, the atom insert and a subtrees data structure as arguments and returns a key if successful. The lookup function takes a state target, the atom lookup and a key as arguments and returns a subtrees data structure if successful.

Example functions #

The following examples are based on Mnesia.

persistence_by_mnesia(_, delete, SubtreesKey)
                     when is_list(SubtreesKey) ->
    true;
persistence_by_mnesia(StateTarget, delete, SubtreesKey) ->
    F = fun() ->
        ok = mnesia:delete({StateTarget, SubtreesKey}),
        true
    end,
    mnesia:activity(transaction, F);

persistence_by_mnesia(_, insert, []) ->
    [];
persistence_by_mnesia(StateTarget, insert,
                      [{_, _, [{Key, _} | _], _} | _] = Subtrees) ->
    SubtreesKey = list_to_binary(Key),
    F = fun() ->
        ok = mnesia:write(StateTarget,
                          #subtrees{subtreesKey = SubtreesKey,
                          subtrees = Subtrees}, write),
        SubtreesKey
    end,
    mnesia:activity(transaction, F);

persistence_by_mnesia(_, lookup, SubtreesKey)
                     when is_list(SubtreesKey) ->
    SubtreesKey;
persistence_by_mnesia(StateTarget, lookup, SubtreesKey) ->
    F = fun() ->
        [{subtrees, SubtreesKey, Subtrees}] = mnesia:read(StateTarget,
                                                          SubtreesKey),
        Subtrees
    end,
mnesia:activity(transaction, F).

Example usage #

Creating the Mnesia table:

-record(subtrees, {subtreesKey, subtrees}).

{atomic, ok} = mnesia:create_table(StateTargetName, [{record_name,
                                                      subtrees}]),

Creating the b-tree:

BTree1 = b_trees:empty(500),
BTree2 = b_trees:set_parameter(BTree1, state,
                               {StateTargetName,
                                fun persistence_by_mnesia/3,
                                fun persistence_by_mnesia/3,
                                fun persistence_by_mnesia/3}),

Pluggable Sort Functionality #

Format #

FunctionName(Key1, Key2) -> equal | greater | less

Key1 = Key2 = any()

The sort function takes two keys as arguments and returns the atom less if Key1 < Key2, the atom greater if Key1 > Key2 and otherwise the atom equal.

Example function #

-spec sort_descending(key(), key()) -> sort_result().

sort_descending(Key_1, Key_2) ->
if
    Key_1 < Key_2 -> greater;
    Key_1 > Key_2 -> less;
    true -> equal
end.

Example usage #

BTree1 = b_trees:empty(500),
BTree2 = b_trees:set_parameter(BTree1, sort, fun sort_descending/2),

Motivation #

B-trees are self-balancing tree data structures that keep data sorted and allow searches, sequential access, insertions, and deletions in logarithmic time. B-trees are a generalization of a binary search trees in that a node can have more than two children. Unlike self-balancing binary search trees, the b-tree is optimized for systems that read and write large blocks of data. B-trees are a good example of a data structure for external memory.

Rationale #

The functional design of the module b_trees is based on the module gb_trees:

 b_trees          | gb_trees
------------------|---------
 n/a              | balance/1
 copy/2           | n/a
 delete/2         | delete/2
 delete_any/2     | delete_any/2
 empty/1          | empty/0
 enter/3          | enter/3
 from_dict/2      | from_orddict/1
 get/2            | get/2
 height/1         | n/a
 insert/3         | insert/3
 is_defined/2     | is_defined/2
 is_empty/1       | is_empty/1
 iterator/1       | iterator/1
 iterator_from/2  | iterator_from/2
 keys/1           | keys/1
 largest/1        | largest/1
 lookup/2         | lookup/2
 map/2            | map/2
 next/1           | next/1
 set_parameter/3  | n/a
 size_key_values/1| size/1
 size_nodes/1     | n/a
 smallest/1       | smallest/1
 sort_ascending/2 | n/a
 sort_descending/2| n/a
 take/2           | take/2
 take_any/2       | take_any/2
 take_largest/1   | take_largest/1
 take_smallest/1  | take_smallest/1
 to_list/1        | to_list/1
 update/3         | update/3
 values/1         | values/1

The functions delete/2 and insert/3 are implementations of the algorithms of Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (2009), Introduction to Algorithms (Third ed.), MIT Press and McGraw-Hill, pp. 484-504, ISBN 0-262-03384-4. Chapter 18: B-Trees.

Backwards Compatibility #

No issues - except module name collisions.

Reference Implementation #

The reference implementation can be fetched from Github:

https://github.com/walter-weinmann/b_trees