title: 数据结构之B+树
date: 2018-11-04 20:39:00
tags: 数据结构与算法之美
一、 浅谈B-树索引
1.B-树的特性
一棵m阶B-树，或者是空树，或者是满足以下性质的m叉树
根结点至少有两个分支；
除根以外的非叶结点，每个结点包含分支数范围[[m/2],m]，即关键字字数的范围是[[m/2]-1,m-1]，其中[m/2]表示取大于等于m/2的最小整数
所有叶子结点都在树的同一层上，并且指针域为空；
所有的非终端结点应包含如下信息： (n，A0，K1，A1，K2，A2，… ，Kn，An)，结点内关键字互不相等，且从小到大排列。
解释：
m阶的意思是这颗树最多的分支是多少，每个节点可以包含很多关键字，范围是[[m/2]-1,m-1]，比如m为 3，就说明是3阶的B-树，
那么它的树的节点的关键字最少2，最多4个。下面的B+树也是同样的理解。
2.B-树索引结构图
3.B-树查找代价分析
设关键字的总数为 N ，求 m阶 B- 树的最大层次 L。
二、 B+树的索引结构
1.B+树特性
在实际的文件系统中，基本上不使用B_树，而是使用B_树的一种变体，称为m阶B+树。 它与B-树的主要不同是叶子结点中存储记录。在B+树中，所有的非叶子结点可以看成是索引，而其中的关键字是作为“分界关键
字”，用来界定某一关键字的记录所在的子树。一棵m阶B+树与m阶B-树的主要差异是：
1.若一个结点有n棵子树，则必含有n个关键字；
2.所有叶子结点中包含了全部记录的关键字信息以及这些关键字记录的指针，而且叶子结点按关键字的大小从小到大顺序链接；
3.所有的非叶子结点可以看成是索引的部分，结点中只含有其子树的根结点中的最大(或最小)关键字。
2.B+树索引结构图
三、 B+树的索引操作
1.B+树查找
对B+树可以进行两种查找运算：
从最小关键字开始，进行顺序查找。
从根结点开始，进行随机查找
在查找时，若非终端结点上的关键值等于给定值，并不终止，而是继续向下直到叶子结点。因此，在B+树中，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。其余同B-树的查找类似。
// 在树中查找数据bool BPlusTree::Search(KEY_TYPE data, char* sPath)
{ int i = 0; int offset = 0; if (NULL != sPath)
{
(void)sprintf(sPath+offset, "The serach path is:");
offset+=19;
}
CNode * pNode = GetRoot(); // 循环查找对应的叶子结点
while (NULL != pNode)
{
// 结点为叶子结点，循环结束
if (NODE_TYPE_LEAF == pNode->GetType())
{ break;
}
// 找到第一个键值大于等于key的位置
for (i = 1; (data >= pNode->GetElement(i) )&& (i <= pNode->GetCount()); i++)
{
} if (NULL != sPath)
{
(void)sprintf(sPath+offset, " %3d -->", pNode->GetElement(1));
offset+=8;
}
pNode = pNode->GetPointer(i);
} // 没找到
if (NULL == pNode)
{ return false;
}if (NULL != sPath)
{
(void)sprintf(sPath+offset, "%3d", pNode->GetElement(1));
offset+=3;
} // 在叶子结点中继续找
bool found = false; for (i = 1; (i <= pNode->GetCount()); i++)
{ if (data == pNode->GetElement(i))
{
found = true;
}
}if (NULL != sPath)
{ if (true == found)
{
(void)sprintf(sPath+offset, " ,successed.");
} else
{
(void)sprintf(sPath+offset, " ,failed.");
}
} return found;
}2.B+树查找代价分析
3.B+树插入
m阶B树的插入操作在叶子结点上进行，假设要插入关键值a，找到叶子结点后插入a，做如下算法判别：
1、如果当前结点是根结点并且插入后结点关键字数目小于等于m，则算法结束；
2、如果当前结点是非根结点并且插入后结点关键字数目小于等于m，则判断若a是新索引值时转步骤④后结束，若a不是新索引值则直接结束；
3、如果插入后关键字数目大于m(阶数)，则结点先分裂成两个结点X和Y，并且他们各自所含的 关键字个数分别为：u=大于(m+1)/2的最小整数，v=小于(m+1)/2的最大整数；由于索引值位于结点的最左端或者最右端，不妨假设索引值位于结点最右端，有如下操作：
a)如果当前分裂成的X和Y结点原来所属的结点是根结点，则从X和Y中取出索引的关键字，将这两个关键字组成新的根结点，并且这个根结点指向X和Y，算法结束；
b)如果当前分裂成的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。
4.B+树的插入过程
5.B+树的删除操作
B+树的删除仅在叶结点上进行。
当叶子结点中的最大关键字被删除时，其在非终端结点中的值可以作为一个“分界关键字”存在。若因删除而使结点中关键字的个数少于m/2 （m/2结果取上界，如5/2结果为3）时，其和兄弟结点的合并过程亦和B-树类似。
6.B+树的删除过程
四、 B+树的优分析
1.为什么选择B+树？
1、B+树的磁盘读写代价更低
我们都知道磁盘时可以块存储的，也就是同一个磁道上同一盘块中的所有数据都可以一次全部读取。而B+树的内部结点并没有指向关键字具体信息的指针 。因此其内部结点相对B_树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。这样，一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
2、B+树的查询效率更加稳定。
由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。