三 . B树、B+树、B*树
Published by linzhi teng
三 . B树、B+树、B*树
3.1 B树(B-树)
3.1.1 B树简介
- B-树是一种多路搜索树(并不一定是二叉的)
- 1970年,R.Bayer和E.mccreight提出了一种适用于外查找的树,它是一种平衡的多叉树,称为B树(或B-树、B_树)。
B-Tree的接点结构B-tree中,每个结点包含:
本结点所含关键字的个数;
指向父结点的指针;
关键字;
指向子结点的指针数组;

一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树,或者是满足下列性质的树:
1、根结点至少有两个子女;
2、每个非根节点所包含的关键字个数 j 满足:m/2 - 1 <= j <= m - 1;
3、除根结点以外的所有结点(不包括叶子结点)的度数正好是关键字总数加1,故内部子树个数 k 满足:m/2 <= k <= m ;
4、所有的叶子结点都位于同一层。
3.1.2 B树特点
是一种多路搜索树(并不是二叉的):
- 定义任意非叶子结点最多只有M个儿子;且M>2;
- 根结点的儿子数为[2, M];
- 除根结点以外的非叶子结点的儿子数为[M/2, M];
- 每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字)
- 非叶子结点的关键字个数=指向儿子的指针个数-1;
- 非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] < K[i+1];
- 非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树;
- 所有叶子结点位于同一层;
3.1.3 B树的查找

在B-树中查找给定关键字的方法类似于二叉排序树上的查找。不同的是在每个结点上确定向下查找的路径不一定是二路而是keynum+1路的。
对结点内的存放有序关键字序列的向量key[l..keynum] 用顺序查找或折半查找方法查找。
- 若在某结点内找到待查的关键字K,则返回该结点的地址及K在key[1..keynum]中的位置;
- 否则,确定K在某个key[i]和key[i+1]之间结点后,从磁盘中读son[i]所指的结点继续查找。直到在某结点中查找成功;或直至找到叶结点且叶结点中的查找仍不成功时,查找过程失败。
查找操作的时间开销
B-树上的查找有两个基本步骤:
- 在B-树中查找结点,该查找涉及读盘DiskRead操作,属外查找;
- 在结点内查找,该查找属内查找。
查找操作的时间为:
- 外查找的读盘次数不超过树高h,故其时间是O(h);
- 内查找中,每个结点内的关键字数目keynum
注意:
- 实际上外查找时间可能远远大于内查找时间。
- B-树作为数据库文件时,打开文件之后就必须将根结点读人内存,而直至文件关闭之前,此根一直驻留在内存中,故查找时可以不计读入根结点的时间。
3.1.4 B树的插入
插入一个元素时:
- 首先判断在B树中是否存在,如果不存在,即在叶子结点处结束,然后在叶子结点中插入该新的元素
注意:
1.1 如果叶子结点空间足够,这里需要向右移动该叶子结点中大于新插入关键字的元素,
1.2 如果叶子节点空间满了以致没有足够的空间去添加新的元素,则将该结点进行"分裂",将一半数量的关键字元素分裂到新的其相邻右结点中,中间关键字元素上移到父结点中(当然,如果父结点空间满了,也同样需要"分裂"操作),而且当结点中关键元素向右移动了,相关的指针也需要向右移。
1.3 如果在根结点插入新元素,空间满了,则进行分裂操作,这样原来的根结点中的中间关键字元素向上移动到新的根结点中,因此导致树的高度增加一层。
3.1.5 B树的删除
- 首先查找B树中需删除的元素,如果该元素在B树中存在,则将该元素在其结点中进行删除,
- 如果删除该元素后,首先判断该元素是否有左右孩子结点,如果有,则上移孩子结点中的某相近元素到父节点中,然后是移动之后的情况;如果没有,直接删除后,移动之后的情况。
3.2 B+树
3.2.1 B+树简介
B+ 树是一种树数据结构,是一个n叉树,每个节点通常有多个孩子。
一棵B+树包含根节点、内部节点和叶子节点。根节点可能是一个叶子节点,也可能是一个包含两个或两个以上孩子节点的节点。
B+树用途
B+ 树通常用于数据库和操作系统的文件系统中。NTFS, ReiserFS, NSS, XFS, JFS, ReFS 和BFS等文件系统都在使用B+树作为元数据索引。B+ 树的特点是能够保持数据稳定有序,其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入。
3.2.2 B+树定义
B+树是应文件系统所需而出的一种B-树的变型树。

一棵m阶的B+树和m阶的B-树的差异在于:
1.有n棵子树的结点中含有n个关键字,每个关键字不保存数据,只用来索引,所有数据都保存在叶子节点。
2.所有的叶子结点中包含了全部关键字的信息,及指向含这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的非终端结点可以看成是索引部分,结点中仅含其子树(根结点)中的最大(或最小)关键字。
通常在B+树上有两个头指针,一个指向根结点,一个指向关键字最小的叶子结点。
B+树与B-树的不同
B+树是B-树的变体,也是一种多路搜索树:
- 定义基本与B-树同,除了:
- 叶子结点的子树指针与关键字个数相同;
- 叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树(B-树是开区间);
- 为所有叶子结点增加一个链指针;
- 所有关键字都在叶子结点出现;
3.2.3 B+树的特性:
- 所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好是有序的;
- 不可能在非叶子结点命中;
- 非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层;
- 更适合文件索引系统;
3.2.4 B+树 vs B树
为什么说B+-tree比B 树更适合实际应用中操作系统的文件索引和数据库索引?
- B+-tree的磁盘读写代价更低
B+-tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
举个例子,假设磁盘中的一个盘块容纳16bytes,而一个关键字2bytes,一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+ 树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候,B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。 - B+-tree的查询效率更加稳定
由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。
3.3 B*树
3.3.1 B*树简介
是B+树的变体,在B+树的非根和非叶子结点再增加指向兄弟的指针;
B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+树的1/2);

3.3.2 B*树 vs B+树
-
B+树的分裂:
当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针; -
B*树的分裂:
当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针;
所以,B*树分配新结点的概率比B+树要低,空间使用率更高;
3.4 小结:
- B-树:
多路搜索树,每个结点存储M/2到M个关键字,非叶子结点存储指向关键字范围的子结点;
所有关键字在整颗树中出现,且只出现一次,非叶子结点可以命中;
- B+树:在B-树基础上,为叶子结点增加链表指针,所有关键字都在叶子结点中出现,非叶子结点作为叶子结点的索引;
B+树总是到叶子结点才命中;
- B*树:在B+树基础上,为非叶子结点也增加链表指针,将结点的最低利用率从1/2提高到2/3;