思考一下

7.2.3分块查找

算法思想

“索引表”中保存每个分块的最大关键字和分块的存储空间

特点：块内无序，块间有序

分块查找，又称之为索引顺序查找，算法过程如下：

1.在索引表中确定待查记录所属的分块(可顺序，可折半)

2.在块内顺序查找（块内是乱序的）

代码：

typedef struct{
  elemtype maxvalum;
  int low,high;
}index;
elemtype list[100];// 实际存储元素的储存结构；

用折半查找索引：

看这样一个索引表，怎么利用折半查找呢？

首先第一类就是查找的数是在索引表有的，比如上面索引表中有的有10 20 30 40 50;待查找的数就是30在索引表中有。利用之前的折半查找是一定能返回对应的表格的。然后再到对应的表中顺序查找。

第二类就是查找的数不在这个索引表中，但是在表内一定是有的。这样他在索引表中一定会不断查找到失败为止，但是这个失败左后的指针都指向索引表内，也就是说最后失败的点就是所查找的数值在对应的表里。

第三类是查找失败了，在索引表中也是不断查找，但是最后指针的指向超出了索引表，那就是说明要查找的数值不在表内；

查找效率分析（ASL）

思考一下

有什么弊端，当你插入一个删除一个元素的时候，你的索引表相应的也会做出相应的调整，这样的话，就意味着要花费掉较大的开销；这是我们不能后接受的

但是我们可以通过改变储存结构来解决这一问题：

7.3 B树和B+树

7.3.1 B树及其基本操作

B树是什么

回顾：二叉查找树

typedef struct BSTNode{
  int key;
  struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

结构如图：

能不能在此之上拓展呢？

五×排序树

struct Node{
  elemtype keys[4];
  struct node *child[5];
  int num;
};

图如下：

我们来看一个查找成功的例子；

从第一层开始查找，9<22,进入第二层第一个；进行比较，9>5继续查找，9<11;进入第三层第二个；分别和6，8，9比较；最后的定位在9。查找成功；

注意：如果每一层的模块里面的个数比较多，那么也是可以进行折半查找的。

我们在看一个查找失败的例子；

查找41；首先和22比较，大于进入第二层第二个；进入第二层开始比较，和第一个首先和36比较大于，再和45比较小于，进入第三层，如下图；开始和40比较，再和42比较。如果比较不成功；则进入退回进入失败节点；

如何保证查找效率？

若每个结点内的关键字太少，导致树变高，要查更多层结点，效率低；

咱们来看一看有什么解决办法；我们规定一个策略：

也就是说，对于5×排序树，规定除了根节点外，任何结点都至少有三个分叉，2个关键字；

那么我们看下面这棵树：你觉得合理么；显然不合理，但他满足了上面的要求，那么接下来看看他那里不合理；

明显这个数也是非常高，原因是不够平衡；

那就再加一个要求：

如果我满足了这两点策略，那么我就可以称之为这颗树为B树；来来看看他的定义：

咱们压缩一下特性：

B树的高度

咱们来计算一下树的高度

回顾

B树的插入

5阶B树

B树的核心要求就是满足B树的特性：

新元素一定是插入到最底层“终端节点”，用“查找”来确定位置
在插入key后，若导致原结点关键字超过上限，则从中间位置将其中的关键字分为两部分，左部分包含的关键字放在原结点中，右部分包含的关键字放在新节点中，中间位置的结点插入到原结点的父节点。若此时此时导致其父结点的关键字个数也超过了上限，则继续进行这种分裂操作，直到这个过程到根结点为止，进而导致B树高度增1；

B树的删除

若删除的关键字是在终端节点，则直接删除该关键字（要注意结点的关键字的个数是否低于下限）

若删除的关键字是在非终端结点，则用直接前驱或直接后继代替被删除的关键字：

直接前驱:当前关键字左侧指针所指子树中最右下的元素

直接后继：当前关键字右侧指针所指子树中最左下的元素

说白了对非终端结点关键字的删除，其实最后必然转化为终端结点的删除操作

兄弟够借。若被删除的关键字所在的结点删除前的关键字个数低于下限，且此节点右（或左）兄弟节点的关键字数还很宽裕，则需要调整该结点，右（或左）兄弟结点（父子换位法）说白了，就是当右兄弟很宽裕的时候，用当前结点的后继，后继的后继来填补空缺。

当左兄弟很宽裕的时候，用当前节点的前驱，前驱的前驱来填补空缺。

兄弟不够借用。若被删除的关键字所在结点删除前的关键字低于下限，且此时与该节点相邻的左右兄弟结点的关键字个数均复合最低要求，则将关键字删除后与左（或右）兄弟节点以及双亲结点中的关键字进行合并

7.3.2 B+树的基本概念

我们来看一看这个图m阶B+树的性质：

1.每个分支结点最多有m棵子树（孩子结点）

3.结点的子树个数与关键字个数相等（对于B树来说，子树个个数会比关键字多一个）

4.所有叶子结点包含全部的关键字以及指向相应的记录的指针，叶子节点中将关键字按照大小顺序进行排序，并且相邻叶子结点按大小顺序连接起来，也支持顺序查找。

5.所有分支结点中仅仅包含他的各个子节点中的关键字的最大值以及指向其子节点的指针

B+树的查找

查找成功：从上到下一一比较，直到比较到最后一层的时候。才算彻底找到，在其他层找到不算，因为他和B树的差别还是有的。

查找失败：

依然是一层一层到最后一层，直到在最后一层没找到他的结点就算失败。应为结点是顺序排列，所以说到最后来说如果找到比他大的之前找到该节点，如果没找到就说明该节点查找失败。

无论是查找成功还是查找失败，最终都要走到最后一层；

顺序查找，你看到那个指针没的，可以通过指针进行链表的顺序查找