B-树

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 颗子树
3. 除 根节点 以外所有 内部节点 的 子节点 / 子树 数量$X$ 满足: $\lceil \frac{m}{2}\rceil \le X\le m$
4. • 根节点至少有 $1$ 个关键字，至多有 $m-1$ 个关键字
5. 非根节点至少有 $\lceil \frac{m}{2}\rceil -1$ 个关键字，至多有 $m-1$ 个关键字
6. 每个节点中的关键字都按照从小到大(升序)排列，每个关键字的左子树中的所有关键字都小于它，右子树中的所有关键字都大于它(也可以反过来，只要满足查找树的定义)

推论

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

$N$个关键字的$m$阶 B-树的高度$h$的取值范围为： $lo{g}_m(N+1)\le h\le lo{g}_{\lceil \frac{m}{2}\rceil }\frac{N+1}{2}+1$