个人总结系列38B+树学习总结数据库数据结构.docx

个人总结系列38B+树学习总结数据库数据结构.docx

《个人总结系列38B+树学习总结数据库数据结构.docx》由会员分享，可在线阅读，更多相关《个人总结系列38B+树学习总结数据库数据结构.docx（12页珍藏版）》请在冰点文库上搜索。

个人总结系列38B+树学习总结数据库数据结构

3.3B+树学习总结

3.3.1B+树原理与概念

在数据库或其他文件系统中，为了便于对记录进行查找，通常需要对记录根据某个或某些字段进行索引，从而系统可以直接对记录进行定位，避免顺序查找造成的效率低下。

现在通常包括两种基本的索引方法：

顺序索引和哈希索引。

顺序索引主要根据searchkey的值对记录进行排序，查找时就可以根据特定的查找算法（如二分法）快速找到符合条件的值。

哈希索引的做法则是使用哈希函数对searchkey进行计算求值，相同结果的记录被分到一个记录桶中，这样查找时就可以快速定位记录桶的位置，然后在桶中进行查找，大大缩小了遍历记录的数目，提高了查找效率。

顺序索引方式主要包括稠密索引和稀疏索引两种类型，稠密索引是为每一个searchkey都建立索引，稀疏索引则是为部分searchkey建立索引。

但是当记录数量较大时，即使采用稀疏索引，索引本身也会变得非常巨大而难于有效处理，因此在系统实际处理时会采用多级索引的方式。

索引顺序文件最大的缺点是随着索引文件的增大，索引查找性能和数据顺序扫描性能都会下降。

而B+树索引结构是使用最广泛的，在数据插入和删除的情形下仍能保持其效率的几种索引结构之一。

B+树索引采用平衡树的结构，其中树根到树叶的每条路径长度相同。

B+树是B树的一种变体，但是在索引方面比B树应用的更为广泛。

首先来了解一下B树，B树是R.Bayer和E.mccreight于1970年提出来的，是一种适用于外查找的树，也是一种平衡的多叉树。

B树结构特性是：

一棵m阶B树，或为空树，或为满足下列特性的m叉树：

（m≥3）

•根结点只有1个，关键字字数的范围[1,m-1]，分支数量范围[2,m]；

•除根以外的非叶结点，每个结点包含分支数范围[[m/2],m]，即关键字字数的范围是[[m/2]-1,m-1]，其中[m/2]表示取大于等于m/2的最小整数；

•叶结点是由非叶结点分裂而来的，所以叶结点关键字个数也满足[[m/2]-1,m-1]；

•所有的非终端结点包含信息：

（n，A0，K1，A1，K2，A2，……，Kn，An），其中Ki为关键字，Ai为指向子树根结点的指针，并且Ai-1所指子树中的关键字均小于Ki，而Ai所指的关键字均大于Ki（i=1，2，……，n）。

n+1表示B树的阶，n表示关键字个数；

•所有叶子结点都在同一层，并且指针域为空

B+树是应文件系统所需而出的一种B树的变型树。

对于一个m阶的B+树而言，具有如下性质和特定：

•根结点只有1个，分支数量范围[2,m]

•除根以外的非叶子结点，每个结点包含分支数范围[[m/2],m]，其中[m/2]表示取大于m/2的最小整数

•所有非叶子结点的关键字数目等于它的分支数量

•所有叶子结点都在同一层，且关键字数目范围是[[m/2],m]，其中[m/2]表示取大于m/2的最小整数

•所有非叶子结点的关键字可以看成是索引部分，这些索引等于其子树（根结点）中的最大（或最小）关键字，例如一个非叶子结点包含信息（n,A0,K0,A1,K1,……,Kn,An），其中Ki为关键字，Ai为指向子树根结点的指针，n表示关键字个数。

即Ai所指子树中的关键字均小于或等于Ki，而Ai+1所指的关键字均大于Ki（i=1，2，……，n）

•叶子结点包含全部关键字的信息（非叶子结点只包含索引），且叶子结点中的所有关键字依照大小顺序链接（所以一个B+树通常有两个头指针，一个是指向根节点的root指针，另一个是指向最小关键字的sqt指针）

图3-9B+树示意图

一棵m阶的B+树和m阶的B树的差异在于：

•有n棵子树的结点中含有n个关键字，每个关键字不保存数据，只用来索引，所有数据都保存在叶子结点。

•所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

•所有的非终端结点可以看成是索引部分，结点中仅含其子树（根结点）中的最大（或最小）关键字。

通常在B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。

3.3.2B+树查找

通常对B+树可以进行两种方式的查找运算：

•从最小关键字起顺序查找；

•从根结点开始，进行随机查找。

因为B+树包括两个头指针，分别是根节点的root指针和指向最小关键字的sqt指针。

采用最小关键字顺序查找的方式同按顺序对记录进行遍历的方式效果一样。

采用从根结点开始，进行随机查找的方式类似二分法的查找方式，可以充分发挥B+树的效率。

查找过程为从根节点开始，在根结点所包含的关键字K1,…,kj查找给定的关键字（可用顺序查找或二分查找法），若找到等于给定值的关键字，则查找成功；否则，一定可以确定要查的关键字在某个Ki或Ki+1之间，于是取Pi所指的结点继续查找，直到找到，或指针Pi为空时查找失败。

值得注意的是，B+树的非叶子结点只有索引功能，没有数据信息，所有数据都在叶子结点中，因此在查找时，若非叶子结点上的关键值等于给定值，并不终止，而是继续向下直到叶子结点。

因此，在B+树中，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。

举一个例子，在如下图所示的B+树中查找44，从根节点开始，发现44小于59，因此在关键字59所在的子树上（15,44,59），在对新的节点上从15开始查找，找到了44，但是这时查找并没有结束，而是必须直到在叶子结点上找到为止。

图3-10B+树查找

3.3.3B+树插入

m阶B+树的插入操作在叶子结点上进行，假设要插入关键值a，找到叶子结点后插入a，做如下算法判别：

1）如果当前结点是根结点并且插入后结点关键字数目小于等于m，则算法结束；

2）如果当前结点是非根结点并且插入后结点关键字数目小于等于m，则判断若a是新索引值时转步骤④后结束，若a不是新索引值则直接结束；

3）如果插入后关键字数目大于m（阶数），则结点先分裂成两个结点X和Y，并且他们各自所含的关键字个数分别为：

u=大于（m+1）/2的最小整数，v=小于（m+1）/2的最大整数；由于索引值位于结点的最左端或者最右端，不妨假设索引值位于结点最右端，有如下操作：

如果当前分裂成的X和Y结点原来所属的结点是根结点，则从X和Y中取出索引的关键字，将这两个关键字组成新的根结点，并且这个根结点指向X和Y，算法结束；如果当前分裂成的X和Y结点原来所属的结点是非根结点，依据假设条件判断，如果a成为Y的新索引值，则转步骤④得到Y的双亲结点P，如果a不是Y结点的新索引值，则求出X和Y结点的双亲结点P；然后提取X结点中的新索引值a，在P中插入关键字a，从P开始，继续进行插入算法；

4）提取结点原来的索引值b，自顶向下，先判断根是否含有b，是则需要先将b替换为a，然后从根结点开始，记录结点地址P，判断P的孩子是否含有索引值b而不含有索引值a，是则先将孩子结点中的b替换为a，然后将P的孩子的地址赋值给P，继续搜索，直到发现P的孩子中已经含有a值时，停止搜索，返回地址P。

 例1：

往下图的3阶B+树中插入关键字9

图3-11例1-1

首先查找9应插入的叶节点（最左下角的那一个）,插入发现没有破坏B+树的性质,完毕。

插完如下图所示：

图3-12例1-2

例2：

往下图的3阶B+树插入20

图3-13例2-1

首先查找20应插入的叶节点（第二个叶子结点）,插入，如下图

图3-14例2-2

发现第二个叶子结点已经破坏了B+树的性质,则把之分解成[20 21], [37 44]两个,并把21往父节点移，如下图：

图3-15例2-3

发现父节点也破坏了B+树的性质,则把之再分解成[15 21], [44 59]两个,并把21往其父节点移，如下图

图3-16例2-4

这次没有破坏B+树的性质（如果还是不满足B+树的性质,可以递归上去,直到满足为至）,插入完毕。

例3：

往下图的3阶B+树插入100

图3-17例3-1

首先查找100应插入的叶节点（最后一个节点）, 插入，如下图：

图3-18例3-2

修改其所有父辈节点的键值为100（只有插入比当前树的最大数大的数时要做此步）,如下图

图3-19例3-3

然后重复Eg.2的方法拆分节点,最后得

图3-20例3-4

3.3.4B+树删除

B+树的删除也仅在叶子结点进行，当叶子结点中的最大关键字被删除时，其在非终端结点中的值可以作为一个“分界关键字”存在。

若因删除而使结点中关键字的个数少于m/2（m/2结果取上界，如5/2结果为3）时，其和兄弟结点的合并过程亦和B树类似。

B树删除算法分析，分以下5种情况讨论：

1）被删除关键字所在的结点为叶结点，关键字数目大于或等于[m/2]，则只需要直接删去Ai和Ki即可；

2）被删除关键字所在的结点为叶结点，关键字数目等于[m/2]-1，相邻的左右兄弟关键字数目至少有一方大于或者等于[m/2]，此时，如果右兄弟关键字数目大于或者等于[m/2]，则将右兄弟中最小的关键字上移到双亲结点中，然后将其中紧靠在上移关键字左边的一个关键字移动到被删除关键字所在的结点的最右边；否则，如果左兄弟的关键字数目大于或者等于[m/2]，则左兄弟中最大的关键字上移到双亲结点中，将紧靠在该上移关键字右边的一个关键字移动到被删除关键字所在的结点的最左边。

这些做法类似于减法的借位运算。

3）被删除关键字所在的结点为叶结点，关键字数目等于[m/2]-1，相邻的左右兄弟关键字数目均等于[m/2]-1，则从双亲借关键字补充，然后算法进入非叶结点的删除判断；

4）被删除关键字所在的结点为非叶结点，并且关键字数目大于或等于[m/2]，则删去Ai和Ki后，原来关键字的左右孩子进行合并，若合并后的结点的关键字数目满足B-树性质，则结束，而对于关键字数目大于m-1，则进行一次分裂，将其中一个结点移到当前结点中。

5）被删除关键字所在的结点为非叶结点，关键字数目等于[m/2]-1，相邻的左右兄弟关键字数目均等于[m/2]-1，则删除该关键字之后优先判断能否从被删除的关键字的左右孩子中寻找关键字补充，如果左右孩子的关键字数目均为[m/2]-1，如果此结点已经是树的根，则直接将被删除关键字的左右孩子结点合并即可，如果不是树的根，则从自己的双亲补充关键字，然后重复上述判断算法4）或者5）。

例1：

删除下图3阶B+树的关键字91

图3-21例1-1

首先找到91所在叶节点（最后一个节点）,删除之，如下图：

图3-22例1-2

没有破坏B+树的性质,删除完毕。

例2：

删除下图3阶B+树的关键字97

图3-23例2-1

首先找到97所在叶节点（最后一个节点）,删除之，然后修改该节点的父辈的键字为91（只有删除树中最大数时要做此步），如下图：

图3-24例2-2

 例3：

删除下图3阶B+树的关键字51

图3-25例3-1

首先找到51所在节点（第三个节点）,删除之，如下图：

图3-26例3-2

破坏了B+树的性质,从该节点的兄弟节点（左边或右边）借节点44，并修改相应键值,判断没有破坏B+树,完毕，如下图：

图3-27例3-3

例4：

删除下图3阶B+树的关键字59

图3-28例4-1

首先找到59所在叶节点（第三个节点）,删除之，如下图：

图3-29例4-2

破坏B+树性质,尝试借节点,无效（因为左兄弟节点被借也会破坏B+树性质）,合并第二第三叶节点并调整键值，如下图：

图3-30例4-3

例5：

删除下图3阶B+树的关键字63

图3-31例5-1

首先找到63所在叶节点（第四个节点）,删除之，如下图：

图3-32例5-2

合并第四五叶节点并调整键值，如下图：

图3-33例5-3

发现第二层的第二个节点不满足B+树性质,从第二层的第一个节点借59,并调整键值，如下图

图3-34例5-4