(a, b) tree

[katsusan]

(a, b)树是一种多路搜索树，每个节点有a到b个孩子节点

定义

• a，b为整数且满足2<=a<=(b+1)/2
• 每个内部节点至少有a个孩子节点，至多b个孩子节点。根节点除外。
• 根节点至多b个孩子节点。
• 所有叶子节点有相同深度。

特性

• 存储n个记录的(a, b)树深度在O(log n/log b)到O(log n/log a)之间。

B树是(a, b)树的一个版本，常用来作为在外部存储器上维护信息的结构。

特性

• 一个d阶B树满足a=d/2和b=d。
• 可以选择适当的d使得一个节点中存储的d-1个键和d个孩子的引用能紧凑地存入一个磁盘块。
• n个记录的B树的搜索和更新操作的IO复杂度为O(logB n)，并且使用O(n/B)个块，B是块的大小。