摘要: 一, M阶B+树的定义(M阶是指一个节点最多能拥有的孩子数,M>2): 图1.1 3阶B+树 (1)根结点只有1个,分支数量范围[2,m]。 (2)除根以外的非叶子结点,每个结点包含分支数范围[[m/2],m],其中[m/2]表示取大于m/2的最小整数。
一, M阶B+树的定义(M阶是指一个节点最多能拥有的孩子数,M>2):
图1.1 3阶B+树
(1)根结点只有1个,分支数量范围[2,m]。
(2)除根以外的非叶子结点,每个结点包含分支数范围[[m/2],m],其中[m/2]表示取大于m/2的最小整数。
(3)所有非叶子节点的关键字数目等于它的分支数量。
(4) 所有叶子节点都在同一层,且关键字数目范围是[[m/2],m],其中[m/2]表示取大于m/2的最小整数。
(5)所有非叶子节点的关键字可以看成是索引部分,这些索引等于其子树(根结点)中的最大(或最小)关键字。例如一个非叶子节点包含信息: (n,A0,K0, A1,K1,……,Kn,An),其中Ki为关键字,Ai为指向子树根结点的指针,n表示关键字个数。即Ai所指子树中的关键字均小于或等于Ki,而Ai+1所指的关键字均大于Ki(i=1,2,……,n)。
(6)叶子节点包含全部关键字的信息(非叶子节点只包含索引),且叶子结点中的所有关键字依照大小顺序链接(所以一个B+树通常有两个头指针,一个是指向根节点的root,另一个是指向最小关键字的sqt)。
二, 3阶B+树的插入举例:
l 例1:
往下图的3阶B+树中插入关键字9
首先查找9应插入的叶节点(最左下角的那一个),插入发现没有破坏B+树的性质,完毕。插完如下图所示:
l 例2:
往下图的3阶B+树插入20
首先查找20应插入的叶节点(第二个叶子节点),插入,如下图
发现第二个叶子节点已经破坏了B+树的性质,则把之分解成[20 21], [37 44]两个,并把21往父节点移,如下图
发现父节点也破坏了B+树的性质,则把之再分解成[15 21], [44 59]两个,并把21往其父节点移,如下图
这次没有破坏B+树的性质(如果还是不满足B+树的性质,可以递归上去,直到满足为至),插入完毕。
l 例3:
往下图的3阶B+树插入100
首先查找100应插入的叶节点(最后一个节点), 插入,如下图
修改其所有父辈节点的键值为100(只有插入比当前树的最大数大的数时要做此步),如下图
然后重复Eg.2的方法拆分节点,最后得
三, 3阶B+树的删除举例:
l 例1:
删除下图3阶B+树的关键字91
首先找到91所在叶节点(最后一个节点),删除之,如下图
没有破坏B+树的性质,删除完毕
l 例2:
删除下图3阶B+树的关键字97
首先找到97所在叶节点(最后一个节点),删除之,然后修改该节点的父辈的键字为91(只有删除树中最大数时要做此步),如下图
l 例3:
删除下图3阶B+树的关键字51
首先找到51所在节点(第三个节点),删除之,如下图
破坏了B+树的性质,从该节点的兄弟节点(左边或右边)借节点44,并修改相应键值,判断没有破坏B+树,完毕,如下图
l 例4:
删除下图3阶B+树的关键字59
首先找到59所在叶节点(第三个节点),删除之,如下图
破坏B+树性质,尝试借节点,无效(因为左兄弟节点被借也会破坏B+树性质),合并第二第三叶节点并调整键值,如下图
完毕。
l 例5:
删除下图3阶B+树的关键字63
首先找到63所在叶节点(第四个节点),删除之,如下图
合并第四五叶节点并调整键值,如下图
发现第二层的第二个节点不满足B+树性质,从第二层的第一个节点借59,并调整键值,如下图
这里的B树,也就是英文中的B-Tree,一个 m 阶的B树满足以下条件:
- 每个结点至多拥有m棵子树;
- 根结点至少拥有两颗子树(存在子树的情况下);
- 除了根结点以外,其余每个分支结点至少拥有 m/2 棵子树;
- 所有的叶结点都在同一层上;
- 有 k 棵子树的分支结点则存在 k-1 个关键码,关键码按照递增次序进行排列;
- 关键字数量需要满足ceil(m/2)-1 <= n <= m-1;
B树上大部分的操作所需要的磁盘存取次数和B树的高度是成正比的,在B树中可以检查多个子结点,由于在一棵树中检查任意一个结点都需要一次磁盘访问,所以B树避免了大量的磁盘访问。
操作
既然是树,那么必不可少的操作就是插入和删除,这也是B树和其它数据结构不同的地方,当然了,还有必不可少的搜索,分享一个对B树的操作进行可视化的网址,它是由usfca提供的。
插入
新结点一般插在第h层,通过搜索找到对应的结点进行插入,那么根据即将插入的结点的数量又分为下面几种情况。
- 如果该结点的关键字个数没有到达m-1个,那么直接插入即可;
- 如果该结点的关键字个数已经到达了m-1个,那么根据B树的性质显然无法满足,需要将其进行分裂。分裂的规则是该结点分成两半,将中间的关键字进行提升,加入到父亲结点中,但是这又可能存在父亲结点也满员的情况,则不得不向上进行回溯,甚至是要对根结点进行分裂,那么整棵树都加了一层。
删除
同样的,我们需要先通过搜索找到相应的值,存在则进行删除,需要考虑删除以后的情况,
- 如果该结点拥有关键字数量仍然满足B树性质,则不做任何处理;
- 如果该结点在删除关键字以后不满足B树的性质(关键字没有到达ceil(m/2)-1的数量),则需要向兄弟结点借关键字,这有分为兄弟结点的关键字数量是否足够的情况。
- 其余情况参照BST中的删除。
B树和B+树的区别
这都是由于B+树和B具有这不同的存储结构所造成的区别,以一个m阶树为例。
- 关键字的数量不同;B+树中有m个分支节点那么该节点就有m个关键字,其关键字只是起到了一个索引的作用,但是B树虽然也有m个子结点,但是其只拥有m-1个关键字。
- 存储的位置不同;B+树中的数据都存储在叶子结点上,也就是其所有叶子结点的数据组合起来就是完整的数据,但是B树的数据存储在每一个结点中,并不仅仅存储在叶子结点上。B树适用于文件存储,B+树适合于索引存储,查找数据时不需要遍历整个树,只是需要在对应的区间内查找。而B树需要一遍中序遍历
- 分支结点的构造不同;B+树的分支结点仅仅存储着关键字信息和儿子的指针(这里的指针指的是磁盘块的偏移量),也就是说内部结点仅仅包含着索引信息。
- 查询不同;B树在找到具体的数值以后,则结束,而B+树则需要通过索引找到叶子结点中的数据才结束,也就是说B+树的搜索过程中走了一条从根结点到叶子结点的路径。