本 EEP 提议创建一个名为 b_trees 的新模块来管理 B 树。可选的持久性和排序顺序都应通过可插拔的功能来实现。
本文档已置于公共领域。
{MinimumSubtrees,
MaximumKeys,
SizeKeyValues,
SortFunction/2,
State,
Tree}
Tree 由以下形式的节点组成
{KeyNumber,
SubtreeNumber,
[{Key, Value}],
[Tree]}
以及“空 B 树”节点
nil
State 是由以下参数组成的元组
{StateTarget,
DeleteFunction/3,
InsertFunction/3,
LookupFunction/3}
由于 B 树始终是平衡的，因此不需要平衡操作。
b_tree() = {pos_integer(),
pos_integer(),
non_neg_integer(),
sort_function(),
state(),
tree()}
通用的平衡树。
iterator() = [{key_values(), subtrees()}]
通用的平衡树迭代器。
类型
Tree1 = Tree2 = Tree3 = b_tree() | gb_trees:tree()
将树 Tree1 复制到空树 Tree2。两个树的类型可以是 B 树或二叉树 (gb_trees)。返回与树 Tree2 类型相同的新树 Tree3。
类型
Key = any()
B-Tree1 = B-Tree2 = b_tree()
从 B 树 B-Tree1 中删除键为 Key 的节点，并返回新的 B 树 B-Tree2。假设键 Key 存在于 B 树 B-Tree1 中，否则会崩溃。
类型
Key = any()
B-Tree1 = B-Tree2 = b_tree()
如果键 Key 存在于 B 树 B-Tree1 中，则从 B 树 B-Tree1 中删除键为 Key 的节点，否则不执行任何操作。返回新的 B 树 B-Tree2。
类型
Order = pos_integer()
B-Tree = b_tree()
返回一个新的空 B 树。阶数定义为非叶节点可以容纳的最大子节点数。
类型
Key = any()
Value = any()
B-Tree1 = B-Tree2 = b_tree()
如果键 Key 不存在于 B 树 B-Tree1 中，则将键 Key 和值 Value 插入到 B 树 B-Tree1 中，否则将 B 树 B-Tree1 中键 Key 的当前值更新为值 Value。返回新的 B 树 B-Tree2。
类型
B-Tree1 = B-Tree2 = b_tree()
List = [{Key, Value}]
将键值元组的有序列表 List 转换为 B 树。给定的 B 树 B-Tree1 必须为空。列表不得包含重复键。
类型
Key = any()
B-Tree = b_tree()
Value = any()
检索 B 树 B-Tree 中与键 Key 存储的值。假设键 Key 存在于 B 树 B-Tree 中，否则会崩溃。
类型
B-Tree = b_tree()
以整数形式返回 B 树 B-Tree 的高度。假设 B 树 B-Tree 为非空。
类型
Key = any()
Value = any()
B-Tree1 = B-Tree2 = b_tree()
将键 Key 和值 Value 插入到 B 树 B-Tree1 中，并返回新的 B 树 B-Tree2。假设键 Key 不存在于 B 树 B-Tree1 中，否则会崩溃。
类型
Key = any()
B-Tree = b_tree()
如果键 Key 存在于 B 树 B-Tree 中，则返回 true，否则返回 false。
类型
B-Tree = b_tree()
如果 B 树 B-Tree 为空 B 树，则返回 true，否则返回 false。
类型
B-Tree = b_tree()
Iterator = iterator()
返回可用于遍历 B 树 B-Tree 条目的迭代器 Iterator；请参见 next/1。此迭代器的实现非常高效；使用 next/1 遍历整个 B 树仅比使用 to_list/1 获取所有键值对列表并遍历该列表稍慢。迭代器方法的主要优点是它不需要一次在内存中构建所有键值对的完整列表。
类型
Key = any(9
B-Tree = b_tree()
Iterator = iterator()
返回可用于遍历 B 树 B-Tree 条目的迭代器 Iterator；请参见 next/1。与 iterator/1 返回的迭代器相比，区别在于返回的第一个键大于或等于键 Key。
类型
B-Tree = b_tree()
Key = any()
以有序列表形式返回 B 树 B-Tree 中的键。
类型
B-Tree = b_tree()
Key = any()
Value = any()
返回元组 {Key, Value}，其中 Key 是 B 树 B-Tree 中最大的键，而 Value 是与此键关联的值。假设 B 树 B-Tree 不为空。
类型
Key = any()
B-Tree = b_tree()
Value = any()
在 B 树 B-Tree 中查找键 Key。返回 {value, Value}，如果键 Key 不存在，则返回 none。
类型
Function = fun((Key, Value1) -> Value2)
B-Tree1 = B-Tree2 = b_tree()
Key = any()
Value1 = Value2 = any()
将函数 Function(Key, Value1) -> Value2 映射到 B 树 B-Tree1 的所有键值对。返回与 B 树 B-Tree1 具有相同键集和新值集的新 B 树 B-Tree2。
类型
Iterator1 = Iterator2 = iterator()
Key = any()
Value = any()
返回元组 {Key, Value, Iterator2}，其中 Key 是迭代器 Iterator1 引用的最小键，而迭代器 Iterator2 是用于遍历剩余节点的新迭代器，如果没有剩余节点，则返回原子 'none'。
类型
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}
在空 B 树 B-Tree1 中将参数 Name 设置为值 Value，并返回新的 B 树 B-Tree2。此函数只能与空 B 树结合使用。
类型
B-Tree = b_tree()
以整数形式返回 B 树 B-Tree 中键值对的数量。如果 B 树 B-Tree 为空，则返回 0（零）。
类型
B-Tree = b_tree()
以两个整数的元组形式返回 B 树 B-Tree 中的节点总数和叶节点数。如果 B 树 B-Tree 为空，则返回 {0, 0}（零）。
类型
B-Tree = b_tree()
Key = any()
Value = any()
返回元组 {Key, Value}，其中 Key 是 B 树 B-Tree 中最小的键，而 Value 是与此键关联的值。假设 B 树 B-Tree 不为空。
类型
Key1 = Key2 = any()
equal = greater = less = atom()
如果 Key1 > Key2，则返回原子 'greater'，如果 Key1 < Key2，则返回原子 'less'，否则返回原子 'equal'。
类型
Key1 = Key2 = any()
equal = greater = less = atom()
如果 Key1 > Key2，则返回原子 'less'，如果 Key1 < Key2，则返回原子 'greater'，否则返回原子 'equal'。
类型
Key = any()
B-Tree1 = B-Tree2 = b_tree()
从 B 树 B-Tree1 中删除键为 Key 的节点，并返回新的 B 树 B-Tree2。假设键 Key 存在于 B 树 B-Tree1 中，否则会崩溃。
类型
B-Tree1 = B-Tree2 = b_tree()
Key = any()
Value = any()
返回元组 {Key, Value, B-Tree2}，其中 Key 是 B 树 B-Tree1 中最大的键，Value 是与此键关联的值，而 B 树 B-Tree2 是删除了相应键值对的 B 树。假设 B 树 B-Tree1 不为空。
类型
B-Tree1 = B-Tree2 = b_tree()
Key = any()
Value = any()
返回元组 {Key, Value, B-Tree2}，其中 Key 是 B 树 B-Tree1 中最小的键，Value 是与此键关联的值，而 B 树 B-Tree2 是删除了相应键值对的 B 树。假设 B 树 B-Tree1 不为空。
类型
B-Tree = b_tree()
Key = any()
Value = any()
将 B 树 B-Tree 转换为键值元组的有序列表。
类型
Key = any()
Value = any()
B-Tree1 = B-Tree2 = b_tree()
将 B 树 B-Tree1 中键 Key 的值更新为 Value，并返回新的 B 树 B-Tree2。假设键 Key 存在于 B 树 B-Tree1 中。
类型
B-Tree = b_tree()
Value = any()
以有序列表形式返回 B 树 B-Tree 中的值，按其对应的键排序。不删除重复项。
{StateTarget, DeleteFunction, InsertFunction, LookupFunction}
StateTarget = any()
DeleteFunction(StateTarget, delete, Key) -> true
InsertFunction(StateTarget, insert, Subtrees) -> Key
LookupFunction(StateTarget, lookup, Key) -> Subtrees
状态目标的示例是 Dets 表或 Mnesia 表。delete 函数接受一个状态目标、原子 delete 和一个键作为参数，如果成功则返回原子 true。insert 函数接受一个状态目标、原子 insert 和一个子树数据结构作为参数，如果成功则返回一个键。lookup 函数接受一个状态目标、原子 lookup 和一个键作为参数，如果成功则返回一个子树数据结构。
以下示例基于 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).
创建 Mnesia 表
-record(subtrees, {subtreesKey, subtrees}).
{atomic, ok} = mnesia:create_table(StateTargetName, [{record_name,
subtrees}]),
创建 B 树
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}),
FunctionName(Key1, Key2) -> equal | greater | less
Key1 = Key2 = any()
排序函数接受两个键作为参数，如果 Key1 < Key2，则返回原子 less，如果 Key1 > Key2，则返回原子 greater，否则返回原子 equal。
-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.
BTree1 = b_trees:empty(500),
BTree2 = b_trees:set_parameter(BTree1, sort, fun sort_descending/2),
B 树是自平衡树数据结构，可使数据保持排序，并允许在对数时间内进行搜索、顺序访问、插入和删除。B 树是二叉搜索树的泛化，因为一个节点可以有两个以上的子节点。与自平衡二叉搜索树不同，B 树针对读取和写入大数据块的系统进行了优化。B 树是外部存储器的数据结构的一个很好的示例。
模块 b_trees 的功能设计基于模块 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
函数 delete/2 和 insert/3 是 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. 第 18 章：B 树算法的实现。
没有问题 - 除了模块名称冲突。
可以从 Github 获取参考实现
https://github.com/walter-weinmann/b_trees