# Multiway Tree

多叉树任意节点的所有子树也都是有顺序的

多叉树可以按固定的方法向二叉树转化：

1. 对所有节点只保留与最左侧子节点的连接，删除其他连接
2. 从左到右依次连接同一层的兄弟节点 (siblings)

# B-Tree

Banlanced Multiway Tree, 顾名思义，B - 树是一种平衡的多路查找树，是平衡二叉树的外延概念。

B-Tree 是为外部查找（如磁盘）设计的一种平衡查找树。

系统从磁盘读取数据到内存时是以存储块 （block） 为基本单位的，位于同一个磁盘块中的数据会被一次性读取出来，而不是需要什么取什么。B-Tree 结构的数据可以让系统高效的找到数据所在的磁盘块。

为了描述 B-Tree，首先定义一条记录为一个二元组$[key,data]$，key 为记录的健值，对应表中的主键值，data 为一行记录中除主键外的数据。对于不同的记录，key 值互不相同。

# 定义

一颗 m 阶 B - 树 (m 路 B - 树) 满足：

1. 所有叶子节点在同一层 (level)，所有叶节点实际上不存在，都是空节点，平衡因子 = 0
2. • 根节点若非空 (不是叶节点 / 空节点)，则有至少 2 颗子树
   • 除 根节点 以外所有 内部节点 的 子节点 / 子树 数量$X$ 满足: $\left\lceil\frac{m}{2}\right\rceil \leq X \leq m$
3. • 根节点至少有 $1$ 个关键字，至多有 $m-1$ 个关键字
   • 非根节点至少有 $\left\lceil\frac{m}{2}\right\rceil-1$ 个关键字，至多有 $m-1$ 个关键字
4. 每个节点中的关键字都按照从小到大 (升序) 排列，每个关键字的左子树中的所有关键字都小于它，右子树中的所有关键字都大于它 (也可以反过来，只要满足查找树的定义)

# 推论

高度为$h$ 的$m$ 阶 B - 树关键字$N$ 取值范围为：
$2\left\lceil\frac{m}{2}\right\rceil^{h-1}-1\leq N\leq m^h-1$

$N$ 个关键字的$m$ 阶 B - 树的高度$h$ 的取值范围为：
$log_m(N+1)\leq h\leq log_{\left\lceil\frac{m}{2}\right\rceil}\frac{N+1}{2}+1$