Skip to content

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

推论

高度为\(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\)