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

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

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号