有了以上的感性认识,我们从理性上洞察一下B-树为何物。每一颗B-树都有自己的阶次,这是它的固有属性。M阶B-树是一颗具有以下结构特征的树:
树根处限制:0个儿子 or 儿子数量在2和M之间
除树根外,所有非叶节点的儿子数量在\left\lceil M/2 \right\rceil\; \; \; \left\lfloor \right\rfloor和M之间
所有的树叶都在相同深度,外部节点也在相同深度
每个内部节点有不超过M-1个关键码
换句话讲,M这个指标规定了B-树内部节点和分支的上下界:M阶B树每个节点最多有M条分支,除根之外,其他节点至少有\left\lceil M/2 \right\rceil\; \; \; \left\lfloor \right\rfloor条分支,这棵树又叫(\left\lceil M/2 \right\rceil\; \; \; \left\lfloor \right\rfloor,M)-树。节点最多存M-1个值,其他的节点至少有实际分支数-1个值(by wikipedia)。对于4阶B树而言,也可以称之为(2,4)树,有趣的是,(2,4)树在B树中具有非常独特的作用和地位,后面我们将会看到(2,4)树与红黑树有不解的渊源。这篇写B-树分析,下篇写具体实现,再下一篇就写红黑树。
红色的部分是真实存在的叶子结点,在很多文献中可以和“外部节点”互称,但在B-树中这是两个完全不同的概念。另外B-树的高度是把外部节点也计入在内的,与通常的BST不同。还需要说明的是,关于B-树的表示问题,因为他特殊的性质导致很多情况下要预留出很多指针位,具体来说就是,如果需要完整的将一棵B树画出来,那就要为每一个关键码的左右后代画出2个指针,如下
但是纸没那么大,所以要紧凑一点来表示,我们把这些指针简化为质点,变成这样:
而外部节点都在同一层,没有差异,就把它忽略掉,我们只关注不同点。可以这样表示:
或者这样:
如此一来就能节省篇幅地表达巨量的数据和引用了。但是画归画,实际上心里还是要明白,里面存在大量的外部节点和引用。接下来的一个问题自然就是:“你说的道理我懂,可是为什么鸽子那么大?” 该如何实现B-树呢?又该如何完成配套的一系列维护操作呢?各位下篇见,明天6点左右发。