B树顾名思义本身也是一棵树,满足树的所有定义,但是其“分枝因子”会相当大,也就会导致一个节点会派生出大量的孩子节点;同时B树对除了跟节点以外的每一个节点的孩子数目以及树的整体高度都有严格要求.使得B树的读取等操作大幅度地减少,从而适用于磁盘等操作.一个常见的B树的变形是B+树,将所有的卫星数据存放在了根节点值周,从而使得每一个节点的分枝数又极大地增加.
一棵B树是具有以下性质的树
-
每个节点至少具有以下属性
- x.n: x节点之中关键字的个数
- x.n内部本身的关键字:x.key[i](),节点内部的关键字,按照非递减顺序排放
- x.leaf:一个bool值,如果x是叶子结点的话就表示为true,否则为false
-
节点内部还有x.n+1个指向孩子节点的指针x.c[i]
- 设为孩子x.c[i]的内部的值,那么满足:,即x的内部节点完成分割
每个叶节点具有相同的深度
-
每个节点(除了根节点)的孩子数有上界和下界,下界用字母 ()来表示
- 除了根节点之外,每一个节点内部至少有个关键字
- (包含根节点)每一个节点内部至多个关键字
-
B树的高度:由于B树的每个叶子结点的高度都是一样的,因此B树的高度就是根节点到叶子结点的长度
-
定理:如果,那么对任意一棵包含个关键字、高度为、最小度数的B树 有:
证明:
为什么不允许最小度数?
当最小度数为1的时候,如果要一个节点只有一个孩子,那么这个节点甚至不能有值,很明显这样的树是没有意义的
请给出{1、2、3、4、5}表示的所有的最小度数为2的所有合法B树的数目
2棵
一棵高度为h,最小度数为t的B树最多可以存储多少个关键字
每个节点都产生2t个孩子,那么高度为h的话会产生:个节点
如果一个红黑树之中每个黑节点吸收她的红色孩子,并把他们的孩子纳入作为自己的孩子,描述这个行为产生的数据结构
会产生一棵2-3-4树,即的B树
B树的操作基本类似于对磁盘所进行的操作,有读写、查找等操作.我们对所有的操作进行以下约定:
- B树的根节点始终在在主存之中,这样我们就无需对根节点进行读取
- 算法都是单程算法:从根节点向下进行,不会涉及到任何从底部向上的过程(每个节点就只需要一组指向孩子的链表,而无需维护指向父亲的指针)
对B树的搜索与普通而插树的搜索类似,只是每一路的分枝数较大.
B-TREE-SEARCH(x,k):在根为x的B树之中搜索值k,如果找到了节点的话返回指向节点的x的指针,以及k在节点之中的下标,否则返回NULL
值得注意的是对于B树来说,越往下遍历的节点就和目标越接近,如果在最下层都没有找到的话,那么就表示这棵树之中没有我们要寻找的值,也就没必要再重新遍历其他分支了
如何在B树之中搜索最小的关键字?如何找一个节点的前驱?
最左节点;左孩子的最右节点
关键字被插入到一棵的空B树之中,最后有多少个节点?
首先我们可以得出节点数目的上限,如果每个节点只有1个关键字,那么最多有个节点(其实考虑到每次插入的值都是比之前大的值,最后一定会插入到一个叶节点内部使得节点数目为)
然后我们思考节点数目的下限,由于我们每次插入节点的时候都会插入到最右叶子节点的内部,因此除了最右侧那一列其余列均为分裂出去的内部只有一个关键字的节点,同样可得节点数目为数量级
证明:即使我们在每个节点内部使用二分查找,在B树之中搜索某个关键字的时间复杂度仍未
证:
本文地址：http://dfvalve.xrbh.cn/quote/7066.html 迅博思语资讯 http://dfvalve.xrbh.cn/ , 查看更多
-