第97页 4.7 B-树

虽然迄今为止我们所看到的查找树都是二叉树，但是还有一种常用的查找树不是二叉树。这种树叫做B-树（B-tree）。
阶为M的B-树是一棵具有下列结构特性的树：
   1.树的根或者是一片树叶，或者其儿子数在2和M之间。
   2.除根外，所有非树叶节点的儿子数在取顶符号（M/2）和M之间。
   3.所有的树叶都在相同的深度上。
所有的数据都存储在树叶上。在每一个内部节点上皆含有指向该节点各儿子的指针P1，P2，……，Pm和分别代表在子树P2，P3……，Pm中发现的最小关键字的值K1，K2，……，Km-1。当然，可能有些指针是NULL，而其对应的Ki则是未定义的。对于每一个节点，其子树P1中的所有关键字都小于子树P2的关键字，如此等等。树叶包含所有实际数据，这些数据或者是关键字本身，或者是指向含有这些关键字的记录的指针。B-树有多重定义，这些定义在一些次要的细节上不同于我们定义的结构，不过，我们定义的B-树是一种流行的结构。（另一种流行的结构允许实际数据存储在树叶上，也可以存储在内部节点上，正如我们在二叉查找树中所做的那样。）我们还要求（暂时）在（非根）树叶中关键字的个数也在取顶符号（M/2）和M之间。
4阶B-树更流行的称呼是2-3-4树，而3阶B-树叫做2-3树。
B-树的深度最多是xxx（参见书上P101，符号打不出来）。经验指出，从运行时间考虑，M的最好（合法的）选择是M=3或M=4。
B-树实际用于数据库系统。
B-树的一些重要概念。
注：取顶符号的解释，详见wiki：https://zh.wikipedia.org/wiki/%E9%AB%98%E6%96%AF%E7%AC%A6%E8%99%9F