当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

m阶B树中“阶”的含义

发表于: 2014-04-20   作者:darrenzhu   来源:转载   浏览次数:
摘要: 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 &
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。

m阶B树中“阶”的含义

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
继续前面TWaver Flex的基础开发课程,本期我们再接再厉,推出了更多内容,这就是《TWaver Flex中阶
继续前面TWaver Flex的基础开发课程,本期我们再接再厉,推出了更多内容,这就是《TWaver Flex中阶
pocket cube , mini cube 二阶魔方 rubik's cube 三阶魔方 rubik's revenge 四阶魔方 professor's c
pocket cube , mini cube 二阶魔方 rubik's cube 三阶魔方 rubik's revenge 四阶魔方 professor's c
已知k阶裴波那契序列的定义为 f(0)=0, f(1)=0, ..., f(k-2)=0, f(k-1)=1; f(n)=f(n-1)+f(n)-2+...+f
1、拉普拉斯算子:对噪声相当敏感,很少用于边缘检测,主要用于已知边缘像素后确定该像素在图像的暗
  零状态响应就是电路在零初始状态下(动态元件初始储能为零)由外施激励引起的响应。 RC电路的零状
下图是本教程介绍的三阶魔方入门的玩法 (层先法)复原的基本步骤示意图: 国丙魔方精彩视频演示 第
一阶负反馈的补偿特性 此例子重点说明了当有外部的恒定变量时,无论如何,LEV都无法到达目标值。最
一阶负反馈的补偿特性 此例子重点说明了当有外部的恒定变量时,无论如何,LEV都无法到达目标值。最
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号