此 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()
返回迭代器 Iterator，可用於遍歷 B 樹 B-Tree 的條目；請參閱 next/1。此迭代器的實現非常高效；使用 next/1 遍歷整個 B 樹只比使用 to_list/1 取得所有鍵值對列表並遍歷它稍微慢一些。迭代器方法的主要優點是它不需要一次在記憶體中建立所有鍵值對的完整列表。
類型
Key = any(9
B-Tree = b_tree()
Iterator = iterator()
返回迭代器 Iterator，可用於遍歷 B 樹 B-Tree 的條目；請參閱 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。如果鍵 Key 不存在，則返回 {value, Value}，否則返回 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()
sort 函數以兩個鍵作為引數，如果 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