B Tree

读过资料中, B树最完整清晰定义来自TAOCP:

1970年, R.Bayer和E.McCreight发现了一种利用多路树分支进行外部查找的新方法, 马克.考夫曼也几乎在同一时间独立地发现了这一方法(未发表). 他们的思想基于一种 被称为B树的通用新型数据结构, 有可能利用相对简单的算法来查找和更新大型数据文件, 并能在最差情况下保证效率.

\(m\)阶B树是满足以下性质的树:

1. 每个节点最多有\(m\)个子节点;
2. 除了根节点及叶子外, 每个节点至少有\(m/2\)个子节点;
3. 根节点至少有\(2\)个子节点(除非它是一个叶子);
4. 所有叶子都出现在同一级别, 并且不携带任何信息;
5. 具有k个子节点的非叶节点包含\(k-1\)个键.

R.Bayer和McCreight仅考虑了\(m\)为奇数的情景, 因此m阶B树实际指\(2m+1\)阶B树.

B树插入节点导致分割时, 是由顶部向上生长的, 而不是在底部向下延伸, 这是因为 B树仅在分割根节点时才增高. 这正是此思想的美妙之处.

给定\(m\)阶B树, 假定存在\(N\)个键, \(N+1\)个叶子出现在\(l\)级, 则 \(1, 2, 3, \dots{}\)级上的节点数至少为 \(2, \lceil{}m/2\rceil, \lceil{}m/2\rceil^2, \dots{}\) 因此 \[N+1 \ge 2\lceil{}m/2\rceil^{l-1} \] \[l \le 1+log_{\lceil{}m/2\rceil}(\frac{N+1}{2})\] 在\(N=1999 998, m=199\)时, \(l\)最多为3, 根常驻内存, 因此最多两次读盘.

插入一个新的节点时, 可能必须分割多达\(l\)个节点, 但构造整颗树时, 发生的总分割 次数就是树中内部节点总数减去\(l\), 所以分割节点的平均数要少很多. 如果有\(p\)个 内部节点, 则至少有\(1+(\lceil{}m/2\rceil{}-1)(p-1)\)个键. 因此 \[p \le 1 + \frac{N-1}{\lceil{}m/2\rceil{}-1}\] 可知, 在构造一个由\(N\)个键组成的树时, 每做一次插入, 需要分割节点的平均次数 少于\(\frac{1}{\lceil{}m/2\rceil-1}\).

参考B+ Tree(WIKI)和\(B^*\) Tree(WIKI).