m阶B树中“阶”的含义
程序员文章站
2022-05-26 17:13:40
...
http://en.wikipedia.org/wiki/B-tree#Terminology
B树的阶(英语对应order)定义是不统一的：
Unfortunately, the literature on B-trees is not uniform in its terminology (Folk & Zoellick 1992, p. 362).
Bayer & McCreight (1972), Comer (1979), and others define the order of B-tree as the minimum number of keys in a non-root node.
Folk & Zoellick (1992) points out that terminology is ambiguous because the maximum number of keys is not clear. An order 3 B-tree might hold a maximum of 6 keys or a maximum of 7 keys.
Knuth (1998, p. 483) avoids the problem by defining the order to be maximum number of children (which is one more than the maximum number of keys).
国内的数据结构教材一般是按照Knuth定义,即“阶”定义为一个节点的子节点数目的最大值。
对于一棵m阶B-tree，每个结点至多可以拥有m个子结点。各结点的关键字和可以拥有的子结点数都有限制，规定m阶B-tree中，根结点至少有2个子结点，除非根结点为叶子节点，相应的，根结点中关键字的个数为1~m-1，比节点数目少一个；非根结点至少有[m/2]（[]，向上取整）个子结点，相应的，关键字个数为[m/2]-1~m-1。
B树的阶(英语对应order)定义是不统一的：
Unfortunately, the literature on B-trees is not uniform in its terminology (Folk & Zoellick 1992, p. 362).
Bayer & McCreight (1972), Comer (1979), and others define the order of B-tree as the minimum number of keys in a non-root node.
Folk & Zoellick (1992) points out that terminology is ambiguous because the maximum number of keys is not clear. An order 3 B-tree might hold a maximum of 6 keys or a maximum of 7 keys.
Knuth (1998, p. 483) avoids the problem by defining the order to be maximum number of children (which is one more than the maximum number of keys).
国内的数据结构教材一般是按照Knuth定义,即“阶”定义为一个节点的子节点数目的最大值。
对于一棵m阶B-tree，每个结点至多可以拥有m个子结点。各结点的关键字和可以拥有的子结点数都有限制，规定m阶B-tree中，根结点至少有2个子结点，除非根结点为叶子节点，相应的，根结点中关键字的个数为1~m-1，比节点数目少一个；非根结点至少有[m/2]（[]，向上取整）个子结点，相应的，关键字个数为[m/2]-1~m-1。
推荐阅读