`
- 浏览:
781431 次
- 性别:
- 来自:
上海
-
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。
分享到:
Global site tag (gtag.js) - Google Analytics
相关推荐
B-Trees 是一类满足特殊条件的M 路查找树。首先说明M 路查找树,M 路查找树是二元查找树的一般化,其结构如下图所示的3 路查找树:M 路查找树中的任一结点至多存放M-1个数据,并至多拥有M棵子树;每个结点中的数据按...
B-树:多路搜索树,每个结点存储M/2到M个关键字,非叶子结点存储指向关键字范围的子结点; 所有关键字在整颗树中出现,且只出现一次,非叶子结点可以命中; B+树:在B-树基础上,为叶子结点增加链表指针,所有关键字...
B树最多只能有M个子节点,最少有三个子节点 三、B+树 介绍:B+树是B树的升级版本,就目前情况,绝大部分都已经用B+树代替了B树了,文件管理、索引等等 四、红黑树 本质:自平衡二叉树 在二叉查找树基础上,添加...
B-树 C++实现 基本功能已实现, 代码经过严格测试,应该没有什么问题了
提出了基于最小误比特率(MBER)准则的变阶长自适应均衡算法——FT-MBER算法。变阶长自适应均衡是未知多径信道均衡的重要技术,准确估计自适应均衡器最佳阶长能同时实现低复杂度和较好的均衡性能,而传统的最小均方...
一棵 m 阶 B 树(Balance Tree of order m), 或为空树,或满足下列的特性的 m 叉树:(本次实验采用链式存储结构) (1)树中每个结点最多含有 m 棵子树。 (2)若根结点是非终端结点,则至少有 2 棵子树 (3)除根结点之外...
这是利用异或法产生M序列及逆M序列的程序实例。
* 1已知一棵树边的集合为(I,m(I,n(e,i(b,e(b,d(a,b(g,j(g,k, (c,g(c,f(h,l(c,h(a,c,画出这棵树并回答以下问题 1) 哪是根节点 2哪是叶子节点 3哪
否则将这个叶子结点分裂成左右两个叶子结点,左叶子结点包含前m/2个记录,右结点包含剩下的记录,将第m/2+1个记录的key进位到父结点中(父结点一定是索引类型结
m序列的verilog实现,12阶伪随机序列的编程
用matlab构造4阶m序列,显示出其波形和自相关函数
定义B-树存储结构(要求m3;为方便操作,结点中增加双亲结点指针域,最底层的Fail结点用NULL指针表示并且所有结点均存储于内存)。定义B-树插入关键字函数、删除关键字函数、查找关键字函数以及按层次遍历输出B-树...
生成5,6,7阶m序列,并选择最优序列对生成Gold序列
想研究算法的可以参考一下, 本文所讨论的m路查找树多为可以动态调整的多路查找树
分数阶傅里叶变换m程序 是典型的程序,可以帮助很好的理解分数阶傅里叶变换
在分析最小生成树问题数学性质的基础上,给出了一种基于降阶技术的快速最小生成...该算法采用降阶技术,大大加快了算法的求解速度,在最坏情况下算法的时间复杂度为O(m);另一方面,算法易于找到问题的全部最小生成树。
题目描述:输入一个N阶方阵(0<N<10),输出此方阵顺时针旋转M(0<=M<=10000)次后的方阵 题目示例:三阶方阵,围绕方阵中心顺时针旋转 输入描述: (1) 第一行输入一个正整数N (0<N<10) (2) 接下来...
富士施乐M205b/M158/P105中文维修手册 施乐205/158/105原厂代码手册,打开密码 tdlcsdec04
定义B-树存储结构(要求m?3;为方便操作,结点中增加双亲结点指针域,最底层的Fail结点用NULL指针表示并且所有结点均存储于内存)。定义B-树插入关键字函数、删除关键字函数、查找关键字函数以及按层次遍历输出B-树...