查找概论：
查找表（Search Table）是由同一类型的数据元素（或记录）构成的集合。
关键字（Key）是数据元素中某个数据项的值，又称为键值，用它可以标识一个数据元素。
若此关键字可以唯一地标识一个记录，则称此关键字为主关键字（Primay Key）。
对于那些可以识别多个数据元素（或记录）的关键字，我们称为次关键字（Secondary Key ）。
查找： 查找(Searching)就是根据给定的某个值，在查找表中确定一个其关键字等于给定值得数据元素（或记录）
查找表按照操作方式来分有两种：静态查找表和动态查找表
静态查找表（Static Search Table）:只作查找操作的查找表。它的主要操作有：
(1)查询某个“特定的”数据元素是否存在查找表中。
(2)检索某个“特定的”数据元素和各种属性。
动态查找表（Dynamic Search Table）：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。动态查找表的操作是两个：
(1)查找时插入数据元素。
(2)查找时删除数据元素。
顺序表查找：
针对线性表进行查找操作，因此它就是静态查找表。
顺序查找（Sequential Search）又叫线性查找，是最基本的查找技术，它的查找过程是：从表中的第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查找的记录；如果直到最后一个记录（或第一个）记录，其关键字和给定的值都不等时，则表中没有所查找的记录，则查找不成功。
顺序表查找算法：
/*顺序查找，a为数组，n为要查找的数组长度，key为要查找的关键字*/
int Sequential_Search(int *a,int n,key)
{
int i;
for(i = 1;i<=n;i++)
{
if(a[i-1]==key)/*因为数组一般是从0开始的，具体可以根据实际情况来定,例如如果要从1开始的话，就可以直接这样写
if(a[i]==key)，从1开始的数组在下面的优化中是有用处的，实际上来说，当然设置在末尾也是可以的，但是要进行一些修改*/
return i;
}
return 0;
}
顺序表查找优化：
因为我们每次循环都需要对i是否越界的进行判定，那么我们可以改变一下思路，设置一个哨兵
/*有哨兵顺序查找*/
int Sequential_Search_Better(int *a,int n,int key)
{
int i;
a[0] = key;//设置a[0]为关键字值，我们称之为“哨兵”
i = n;
while(a[i]!=key)
{
i--;
}
return i;//返回0说明查找失败
}
时间复杂度O(n).
缺点：n很大时，查找效率低下。
有序表查找：
折半查找(Binary Search)技术，又称为二分查找。它的前提是线性表中的记录必须是关键码有序(通常是从小到大有序)，线性表必须采用顺序存储。折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定与中间值的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区域继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区域继续查找。不断重复上述过程，知道查找成功，或所有查找区域无记录，查找失败为止。
以下是折半查找算法的代码实现：
/*折半查找*/
int Binary_Search(int *a,int n,int key)
{
int low,high,mid;
low = 1;//定义最低下标为记录首位
high = n;//定义最高下标为记录末位
while(low<=high)
{
mid = (low+high)/2;//折半
if(key<a[mid])//若查找值比中值小
high = mid-1;//最高下标调整到中位下标小一位
else if(key>a[mid])//若查找值比中值大
low = mid+1;
else
return mid;
}
return 0;
}
时间复杂度：O(logn)
插值查找：
在折半查找中把
mid = (low+high)/2;//折半
改成
mid = low + (high-low)*(key-a[low])/(a[high]-a[low]);//插值
就可以得到另一种有序表查找算法---》插值查找法。
插值查找(Interpolation Search)是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找算法，其核心就在于插值的计算公式：(key-a[low])/(a[high]-a[low])。
其时间复杂度也是O(logn),但是对于表长较大，而且关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布类似{0,1,2,2000,2001,……,999998,999999}这种极端不均匀的数据，用插值就未必是一个好的选择了。
斐波那契查找(Fibonacci Search)：
利用了黄金分割原理来实现的。
以下是斐波那契查找算法的实现代码：
/*斐波那契查找*/
int Fibonacci_Search(int *a,int n,int key)
{
int low,high,mid,i,k;
low = 1;//定义最低下标为记录首位
high = n;//定义最高下标为记录末位
k = 0;
while(n>F[k]-1)//计算n位于斐波那契数列的位置
k++;
for(i=n;i<F[k]-1;i++)//讲不满的数值补全
a[i] = a[n];
while(low<=high)
{
mid=low+F[k-1]-1;//计算当前分隔的下标
if(key<a[mid])//若查找记录小于当前分隔记录
{
high=mid-1;//最高下标调整到分隔下标mid-1处
k = k-1;
}
else if(key>a[mid])//若查找记录大于当前分隔记录
{
low=mid+1;//最低下标调整到分隔下标的mid+1处
k = k-2;//斐波那契数列下标减两位
}
else
{
if(mid<=n)
return mid;//若相等则说明mid即为查找到的位置
else
return n;//若mid>n说明是补全数值，返回n
}
}
return 0;
}
斐波那契算法的核心在于：
1.当key=a[mid]时，就查找成功；
2.当key<a[mid]时，新范围是第low个到第mid-1个，此时范围个数为F[k-1]-1个；
3.当key>a[mid]时，新范围是第m+1个到第high个，此时范围个数为F[k-2]-1个。
也就是说，如果要查找的记录在右侧，则左侧的数据都不用再判断了，不断反复进行下去，处于当中的大部分数据，其工作效率要高一些。所以尽管斐波那契查找的时间复杂度也为O(logn),但就平均性能来说，还是要优于折半查找的。可惜如果是最坏情况，比如这里的key=1，那么始终都处于左侧长半区在查找，则查找效率要低于折半查找。
还有比较关键一点，折半查找是进行加法与除法运算(mid=(low+high)/2)，插值查找进行复杂的四则运算(mid=low+(high-low)*(key-a[low])/(a[high]-a[low])),而斐波那契查找只是最简单的加减法运算(mid=low+F[k-1]-1),在海量数据的查找过程中，这种细微的差别可能会影响最终的查找效率。
线索索引查找:
数据结构的最终目的是提高数据的处理速度，索引是为了加快查找速度而设计的一种数据结构。---》》》索引就是把一个关键字与它对应的记录相关联的过程；；；一个索引由若干个索引项构成，每个索引项至少至少应该包含关键字和其对应的记录在存储器中的位置等信息。
索引技术是组织大型数据库及磁盘文件的一种重要的技术。
索引按照结构可以分为：
线索索引、树形索引和多级索引。
以下只介绍线索索引：
所谓线索索引就是讲索引项集合组织为线性结构，也称为索引表。
以下会重点介绍三种线性索引：
稠密索引、分块索引和倒排索引
稠密索引：
稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项。
对于稠密索引这个索引表来说，索引项一定是按照关键码有序的排序。
索引项有序也就意味着我们要查找关键字时，可以使用折半、插值、斐波那契等有序查找算法，大大提高了效率。这显然是稠密索引的优点，但是如果数据集非常大，那也就意味着索引也得同样的数据集长度规模，对于内存有限的计算机来说，可能就需要反复去访问磁盘，查找性能反而大大下降了。
分块索引：
稠密索引因为索引项与数据集的记录个数相同，所以空间代价很大。为了减少索引项的个数，我们可以对数据集进行分块，使其分块有序，然后再对每一块建立一个索引项，从而减少索引项的个数。
分块有序，是把数据集的记录分成了若干块，并且这些块需要满足两个条件：
(1)块内无序，即每一块内的记录不要求有序。
(2)块间有序，例如，要求第二块所有记录的关键字均要大于第一块中所有记录的关键字，第三块的所有记录的关键字均要大于第二块的所有记录关键字……因为只有块间有序，才有可能在查找时带来效率。
对于分块有序的数据集，将每块对应一个索引项，这种索引叫做分块索引。
如下图所示：
我们定义的分块索引的索引项结构分为三个数据项：
》最大关键码，它存储每一块中的最大关键字，这样的好处就是可以使得在它之后的下一块重的最小关键字也能比这一块最大的关键字要大。
》存储了块中的记录个数，以便于循环时使用。
》用于指向块首数据元素的指针，便于开始对这一块中记录进行遍历。
在分块索引表中查找，就是分两步进行：
1.在分块索引表中查找要查关键字所在的块。由于分块索引表是块间有序的，因此很容易利用折半、插值等算法得到结果。
2.根据块首指针找到相应的块，并在块中顺序查找关键码。因为块中可以是无序的，因此只能顺序查找。
分块索引的效率比顺序查找的O(n)是高了不少，但是显然它与折半查找的O(logn)相比还有不少的差距。因此在确定所在块的过程中，由于块间有序，所以可以应用折半、插值等手段来提高效率。
总的来说，分块索引在兼顾了对细分块不需要有序的情况下，大大增加了整体查找的速度，所以普遍被用于数据库表查找等技术的应用中。
倒排索引：
索引项的通用结构是：
次关键码
记录号表
其中，记录号表存储具有相同次关键字的所有记录的记录号(可以使指向记录的指针或者是该记录的主关键字)。这样的索引方法就是倒排索引(inverted index).
倒排索引源于实际应用中需要根据属性（或字段、次关键码）的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而成为倒排索引。
倒排索引的优点：查找速度非常快，基本等于生成索引后，查找时都不用去读取记录，就可以得到结果。
倒排索引的缺点：记录号不是定长的，若是对多篇文章所有单词建立倒排索引，每个单词都将对应相当多的文章编号，维护比较困难，插入和删除操作都需要作相应的处理。
二叉排序树：
二叉排序树(Binary Sort Tree)，又称为二叉查找树。它或者是一颗空树，或者是具有下列性质的二叉树。
若它的左子树不为空，则左子树的所有节点均小于它的根结构的值；
若它的右子树不为空，则右子树的所有节点均大于它的根结构的值；
它的左、右子树也分别为二叉排序树。
从二叉排序树的定义可以知道，它气体是二叉树，然后它采用了递归的定义方法，再者，它的结点间满足一定的次序关系，左子树结点一定比其双亲结点小，右子树结点一定比其双亲结点大。
构造一棵二叉排序树的目的，其实并不是为了排序，而是为了提高查找和插入删除关键字的速度。不管怎么说，在一个有序数据集上的查找，速度总是要快于无序的数据集的，而二叉排序树这种非线性的结构，也有利与插入和删除的实现。
二叉排序树查找操作：
首先提供一个二叉树的数据结构：
/*二叉树的二叉链表结点结构定义*/
typedef struct BiTNode //结点结构
{
int data;//结点数据
struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
然后以下是二叉排序树的查找实现：
/*递归查找二叉排序树T中是否存在key，指针f指向T的双亲，其初始调用值为NULL;
若查找成功，则指针p指向该数据元素结点，并返回TRUE;
否则指针p指向查找路径上访问的最后一个结点并返回FALSE*/
Status SearchBST(BiTree T,int key,BiTree f,BiTree *p)
{
if(!T) //查找不成功
{
*p = f;
return FALSE;
}
else if(key==T->data)//查找成功
{
*p = T;
return TRUE;
}
else if(key<T->data)
return SearchBST(T->lchild,key,T,p);//在左子树继续查找
else
return SearchBST(T->rchild,key,T,p);//在右子树继续查找
}
二叉排序树插入操作：
/*当二叉排序树T中不存在关键字等于key的数据元素是，
插入key并返回TRUE，否则返回FALSE*/
Status InsertBST(BiTree *T,int key)
{
BiTree p,s;
if(!SearchBST(*T,key,NULL,&p))//查找不成功
{
s = (BiTree)malloc(sizeof(BiTree));
s->data=key;
s->lchild = s->rchild = NULL;
if(!p)
*T = s;//插入s为新的根结点
else if (key<p->data)
p->lchild = s;//插入s为左孩子
else
p->rchild = s;//插入s为右孩子
return TRUE;
}
else
return FALSE;//树中已存在关键字
}
构建二叉排序树的程序代码：
int i;
int a[10]={62,88,58,47,35,73,51,99,37,93}
BiTree T = NULL;
for(i=0;i<10;i++)
{
InsertBST(&T,a[i]);
}
二叉排序树删除操作：
删除结点的三种情况：
(1)叶子结点
(2)仅有左或右子树的结点
(3)左右子树都有的结点，我们来看代码，下面这个算法是递归方式对二叉排序树T查找key,查找到时删除
实现代码
/*若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点，并返回TRUE；否则返回FALSE */
Status DeleteBST(BiTree *T,int key)
{
if(!*T)//不存在关键字等于key的数据元素
return FALSE;
else
{
if(key==(*T)->data//找到关键字等于key的数据元素
return Delete(T);
else if(key<(*T)->data)
return DeleteBST(&(*T)->lchild,key);
else
return DeleteBST(&(*T)->rchild,key);
}
}
这段饭吗和前面的二叉排序查找几乎完全相同个，唯一的区别就在于
return Delete(T);
这行，此时执行的是Delete方法，对当前结点进行删除操作。
以下是Delete代码：
/*从二叉排序树中删除结点p，并重接它的左或右子树.*/
Status Delete(BiTree *p)
{
BiTree q,s;
if((*p)->rchild==NULL)//右子树空则只需重接它的左子树
{
q=*p;*p=(*p)->lchild;free(q);
}
else if((*p)->lchild==NULL)//只需重接它的左子树
{
q=*p;*p=(*p)->rchild;free(q);
}
else//左右子树均不变
{
q=*p;s=(*p)->lchild;
while(s->rchild)//转左，然后向右到尽头
{
q=s;s=s->rchild;
}
(*p)->data=s->data;//s指向被删结点的直接前驱
if(q!=*p)
q->rchild=s->lchild;//重接q的右子树
else
q->lchild=s->lchild;//重接q的左子树
free(s);
}
return TRUE;
}
总之，二叉排序树是以链接的方式存储，保持了连接存储结构在执行插入或删除操作时不用移动元素的优点，只要找到合适的插入和删除位置后，仅需要修改链接指针即可。插入删除的时间性能比较好。而对于二叉排序树的查找，走的就是从根节点到要查找的结点的路径，其比较次数等于给定的结点在二叉排序树的层数。极端情况，最少为1次，最多也不会超过树的深度。
但是问题在于，二叉排序树的形状是不确定的。
如果二叉排序树是比较平衡的，即其深度与完全二叉树相同，均为【log2n】+1，那么查找的时间复杂也就是O(logn),近似与折半查找。
不平衡的情况就是斜树，查找的时间复杂度为O(n)，等同于顺序查找。
于是我们可以引申出“平衡二叉树”这样的一个概念，即探讨关于如何让二叉排序树平衡的问题。
平衡二叉树（AVL树）：
平衡二叉树（Self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree),是一种二叉排序树，其中每一个结点的左子树和右子树的高度差至多等于1。-----》》》一种高度平衡的二叉排序树。
二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF(Balance Factor)，那么平衡二叉树上所有结点的平衡因子只可能是-1、0、1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。
距离插入结点最贱的，且平衡影子的绝对值大于1的结点为根的子树，我们称为最小不平衡子树。
平衡二叉树实现原理
平衡二叉树构建的基本思想就是在构建二叉排序树的过程中，每当插入一个结点时，先检查是否因为插入而破坏了树的平衡性，若是，则找出最小不平衡子树。在保持二叉排序树特性的前提下，调整最小不平衡子树中各个结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。
平衡二叉树的实现算法：
改进二叉排序树的结点结构，增加一个bf，用来存放平衡因子：
typedef struct BiTNode //结点结构
{
int data;//结点数据
int bf;//结点的平衡因子
struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
右旋操作
/*对以p为根的二叉排序树作右旋处理，处理之后p指向新的树根结点，即旋转处理之前的左子树的根结点*/
void R_Rotate(BiTree *P)
{
BiTree L;
L=(*P)->lchild;//L指向P的左子树根结点
(*P)->lchild = L->rchild;//L的右子树接为P的左子树
L->rchild=(*P);
*P=L;//P指向新的结点
}
左旋操作
/*对以P为根的二叉排序树作左旋处理，处理之后P指向新的树根结点，即旋转处理之前的右子树的根结点0*/
void L_Rotate(BiTree *P)
{
BiTree R;
R = (*P)->rchild;//P指向P的右子树根结点
(*P)->rchild = R->lchild;//R的左子树挂接为P的右子树
R->lchild = (*P);
*P = R;//P指向新的根结点
}
下面是左平衡旋转处理的函数代码：
#define LH +1 //左高
#define EH 0 //等高
#define RH -1 //右高
/*对以指针T所指结点为根的二叉树作左平衡旋转处理，
本算法结束时，指针T指向新的根结点*/
void LeftBalance(BiTree *T)
{
BiTree L,Lr;
L = (*T)->lchild;//L指向T的左子树根结点
switch(L->bf)
{
//检查T的左子树的平衡度，并作相应平衡处理
case LH://新结点插入在T的左孩子的左子树上，要作单右旋转处理
(*T)->bf = L->bf = EH;
R_Rotate(T);
break;
case RH://新结点插入在T的左孩子的右子树上，要作双旋处理
Lr=L->rchild;//Lr指向T的左孩子的右子树的根
switch(Lr->bf)//修改T及其左孩子的平衡因子
{
case LH:(*T)->bf = RH;
L->bf=EH;
break;
case EH:(*T)->bf = L->bf = EH;
break;
case RH:(*T)->bf = EH;
L->bf=LH;
break;
}
Lr->bf=EH;
L_Rotate(&(*T)->lchild);//对T的左子树作左旋平衡处理
R_Rotate(T);//对T作右旋平衡处理
}
}
主函数：
/*若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个数据元素为e的结点并返回1，否则返回0。若因插入而使二叉排序树失去平衡，则作平衡旋转处理，布尔变量taller反映T长高与否。*/
Status InsertAVL(BiTree *T,int e,Status *taller)
{
if(!*T)
{
/*插入新结点，树“长高”，置taller为TRUE*/
*T = (BiTree)malloc(sizeof(BiTNode));
(*T)->data = e;
(*T)->lchild = (*T)->rchild = NULL;
(*T)->bf = EH;
*taller = TRUE;
}
else
{
if(e==(*T)->data;
{
/*树中已存在和e有相同关键字的结点则不再插入*/
*taller = FALSE;
return FALSE;
}
if(e<(*T)->data)
{
if(!InsertAVL(&(*T)->lchild,e,taller)) //未插入
return FALSE;
if(*taller) //已插入到T的左子树中且左子树“长高”
{
switch((*T)->bf) //检查T的平衡度
{
case LH://原本左子树比右子树高，需要作左平衡处理
LeftBalance(T);
*taller = FALSE;
break;
case EH://原本左右子树等高，现因左子树增高而树增高
(*T)->bf = LH;
*taller = FALSE;
break;
case RH://原本右子树比左子树高，现在左右子树等高
(*T)->bf = EH;
*taller = FALSE;
break;
}
}
}
else
{
//应继续在T的右子树中进行搜索
if(!InsertAVL(&(*T)->rchild,e,taller))//未插入
return FALSE;
if(*taller) //已插入到T的右子树且右子树“长高”
{
switch((*T)->bf) //检查T的平衡度
{
case LH://原本左子树比右子树高，现在左右子树等高
(*T)->bf = EH;
*taller = FALSE;
break;
case EH://原本左右子树等高，现因右子树增高而树增高
(*T)->bf = RH;
*taller = FALSE;
break;
case RH://原本右子树比左子树高，需要作右平衡处理
RightBalance(T);
*taller = FALSE;
break;
}
}
}
}
return TRUE;
}
构造一棵平衡二叉树的代码实现：
int i;
int a[10] = {3,2,1,4,5,6,7,10,9,8};
BiTree T = NULL;
Status taller;
for(i = 0;i<10;i++)
{
InsertAVL(&T,a[10],&taller);
}
查找的时间复杂度O(logn);
插入和删除也同样是O(logn).
多路查找树(B树)
多路查找树(muitl-way search tree)，其中每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。
---》》》其有四种特殊形式：
2-3树、2-3-4树、B树和B+树
--》》2-3树：
2-3树是这样的一棵多路查找树：其中每一个结点都具有两个孩子（我们称它为2结点）或三个孩子（我们称它为3个结点）。
一个2结点包含一个元素两个孩子（或没有孩子），且与二叉排序树类似，左子树包含的元素小于该元素，右子树包含的元素大于该元素。与二叉排序树的区别在于这个2结点要么没有孩子，要有就只能有两个，不能只有一个孩子。
一个3结点包含一小一大两个元素和三个孩子（或没有孩子），一个3结点要么没有孩子，要么具有3个孩子。如果某个3结点有孩子的话，左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素。
并且所有的2-3树中所有的叶子都在同一层次上。
2-3树复杂的地方就在于新结点的插入和已有结点的删除。
2-3树的插入实现：
2-3树插入可以分为三种情况：
1)对于空树，插入一个2结点即可。
2)插入结点到一个2结点的叶子上。应该说，由于其本身就只有一个元素，所以只需要将其升级为3的结点即可。
3)要往3结点中插入一个新元素。
因为3结点本身已经是2-3树的最大容量，因此就需要将其拆分，且将树中两元素或插入元素的 三者中选择其一向上移动一层。复杂的情况也正在于此。
2-3树删除实现：
2-3树的删除也分为三种情况：
1)所删除的元素位于一个3结点的叶子结点上，这非常简单，只需要在该结点处删除该元素即可，不会影响到整棵树的其它结点结构。
2)所删除元素位于一个2结点上，即要删除的是一个只有一个元素的结点。对于删除叶子是2结点的情况，需要分一下四种情形来讨论。
情形一，此节点的额双亲也是2结点，且拥有一个3结点的右孩子。
情形二，此结点的双亲是2结点，它的右孩子也是2结点。
情形三，此结点的双亲是一个3结点。
情形四，如果当前树是一个满二叉树的情况，此时删除任何一个叶子都会使得整棵树不能满足2-3树的定义。
3)所删除的元素位于非叶子的分支结点。此时我们通常是将树按中序遍历后得到此元素的前驱或后继元素，考虑让它们来补位即可。
2-3-4树：
2-3-4就是2-3树的概念扩展，包括4结点的使用。一个4结点包含小中大三个元素和四个孩子(或没有孩子)，一个4结点要门没有孩子，要么具有4个孩子。---》》》如果某个4结点有孩子的话，左子树包含小于最小元素的元素；第二子树包含大于最小元素，小于第二元素的元素；第三子树包含大于第二元素，小于最大元素的元素；右子树包含大于最大元素的元素。
B树：
B树(B-tree)是一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例。结点最大的孩子数目称为B树的阶(order)，因此，2-3树是3阶B树，2-3-4树是4阶B树。
一个m阶的B树具有如下属性：
--》如果根结点不是叶子结点，则其至少有两棵子树。
--》每一个非根的分支结点都有k-1个于是奶和k个孩子，其中【m/2】<=k<=m。每一个叶子结点n都有k-1个元素，其中【m/2】<=k<=m。
--》所有叶子结点都位于同一层次。
--》所有分支结点包含下列信息数据（n,A0,K1,A1,K2,A2,…,Kn,An），其中：Ki(i=1,2,…,n)为关键字，且Ki<K(i+1)(i=1,2,…，n-1);Ai(i=0,2,…,n)为指向子树根结点的指针，且指针A(i-1)所指子树中所有关键字均小于Ki(i=1,2,…，n),An所指子树所有结点的关键字均大于Kn,n(【m/2】-1<=n<=m-1)为关键字的个数(或n+1为子树的个数)。
在B树上查找的过程是一个顺直镇查找结点和在结点中查找关键字的交叉过程。
B+树：
B+树是应文件系统所需而出的一种B树的变形树，其实从严格意义上，它其实已经不是第六章定义的树了。在B树中，每个元素在该树中只出现一次，有可能在叶子结点上，也有可能在分支结点上。而在B+树中，出现在分支结点中的元素会被当做他们在该分支结点位置的中序后继者（叶子结点）中再次列出。另外，每一个叶子结点都会保留一个指向后一页子结点的指针。
：---》》》插图：
一棵m阶的B+树和m阶的B树的差异在于：
--》》有n棵子树的结点中包含有n个关键字
--》》所有叶子结点包含全部关键字的信息，以及指向含这些关键字记录的指针，叶子结点本身依关键字的大小自小而大顺序链接。
--》》所有分支结点可以看成是索引，结点中仅含有其子树中的最大（或最小）的关键字。
这样的数据结构的好处：如果是要随机查找，我们就从根结点出发，与B树的查找方式相同，只不过即使在分支结点找到了待查找的关键字，它也只是用来索引的，不能提供实际记录的访问，还是需要到达包含此关键字的终端结点。
B+树特别适合带有范围的查找。
散列表查找（哈希表）概述
散列表查找定义：
存储位置=f(关键字)
散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f使得每个关键字key对应一个存储位置f(key)。
--》》我们把这种对应关系f称为散列函数，又称为哈希（Hash）函数。
采用三列结束将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表(Hash table)。
散列表查找步骤：
整个散列过程其实就是两步》》》
1)在存储时，通过散列函数计算记录的散列地址，并按此散列地址存储该记录。--》》总之就是，不管是什么记录，我们都要用同一个散列函数计算出地址再存储。
2)当查找记录时，我们通过同样的散列函数计算记录的散列地址，按此三列地址访问该记录。
---》》》散列技术既是一种存储方法，也是一种查找方法。
散列技术的记录之间不存在什么逻辑关系，它只与关键字有关。故散列主要是面向查找的存储结构。
散列技术最适合的求解问题是查找与给定值相等的记录。
散列技术 “不适合” 以下情况：
1.那种相同的关键字，能够对应很多的记录的情况。
2.不适合反问查找。
另一个问题是冲突。理想的情况下，每一个关键字，通过散列函数计算出来的地址都是不一样的，可现实生活中，这只是一个理想。我们时常碰到以下情况：两个关键字key1≠key2，但却有f(key1)=f(key2)，这种现象我们称为冲突(collision)，并把key1和key2称为这个散列函数的同义词（synonym）。
--》出现冲突将造成查找错误。尽管可以通过尽心设计的散列函数让冲突尽可能的少，但不能完全避免。
散列函数的构造方法：
原则：
1)计算简单。散列函数的计算时间不应该超过其他查找技术与关键字的比较时间。
2)散列地址分布均匀。我们刚刚也谈到冲突带来的问题，最好的办法确实就是尽量让散列地址均匀地分布在存储空间中，这样可以保证存储空间的有效利用，并减少为处理冲突而耗费的时间。
以下是几种常用的散列函数的构造方法。
1.直接定址法：取关键字的某个线性函数值为散列地址，即
f(key) = a * key + b (a、b为常数)
这样的散列函数的优点就是简单、均匀，也不会产生冲突，但问题是这需要事先知道关键字的分布情况，适合查找表较小且连续的情况。--》由于这样的限制，在现实应用中，这种方法虽然简单，但是却并不常用。
2.数字分析法：
抽取方法是使用关键字的一部分来计算散列存储位置的方法，这在散列函数中是常常用到的手段。
数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀，就可以考虑用这个方法。
3.平方取中法：
假设关键字是1234，则其平方为1522756，抽取中间的3位就是227，用作散列地址。
平方取中法较适合于不知道关机子的分布，而位数又不是很大的情况。
4.折叠法：将关子健从左到右分割成位数相等的几部分（注意最后一部分位数不够时可以短些），然后将这几部分叠加求和，并按散列表表长，去最后几位作为散列地址。
例子：
比如我们的关键字时9876543210，散列表表长三位，我们将其分成四组，987|654|321|0，然后将它们叠加求和987+654+321+0 = 1962，再求后3位得到散列地址为962。
有时还不能够保证分布均匀，不妨从一端到另一端来回折叠后对齐相加。比如我们将987和321反转，再与654和0相加，变成789+654+123+0 = 1566，此时散列地址为566。
折叠法事先不需要知道关键字的分布，适合关键字位数较多的情况。
5.除留余数法
此方法为最常用的构造散列函数方法。对于散列表长为m的散列函数公式为;
f(key) = key mod p (p<=m)
本方法的关键在于选择合适的p,p如果选择得不好，就可能容易产生同义词。
--》》根据前人的经验，若散列表表长为m，通常p为小于或等于表长（最好接近m）的最小质数或不包含小于20的质因子的合数。
6.随机数法：
选择一个随机数，取关键字的随机函数值为它的散列地址。也就是f(key) = random(key)。
现实中，应该视不同的情况采用不同的散列函数。以下是一些考虑因素：
1.计算散列地址所需要的时间。
2.关键字的长度。
3.散列表的长度。
4.关键字的分布情况。
5.记录查找的频率。
处理散列冲突的方法：
1.开放定址法：是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。
它的公式是：
fi(key)=(f(key)+di) MOD m (di = 1,2,3,……,m-1)
---》》》线性探索法
---》》》本来不是同义词却需要争夺一个地址的情况，我们称这种现象为堆积。
改进di=1^2,-1^2,2^2,-2^2……,q^2,-q^2,(q<=m/2)，这就等于是可以双向寻找可能的空位置。对于34来说，我们取di=-1即可以找到空位置了。
增加平方运算的目的是为了不让关键字都聚集在某一块区域。我们称这种方法为二次探索法。
fi(key)=(f(key)+di) MOD m (di=1^2,-1^2,2^2,-2^2……,q^2,-q^2,q<=m/2)
还有一种方法是，在冲突时，对位移量di采用随机函数计算得到，我们称之为随机探测法。
fi(key)=(f(key)+di) MOD m (di是一个随机数列)
总之开放地址法只要在散列表未填满时，总能找到不发生冲突的地址，使我们常用的解决冲突的方法。
2.再散列函数法
事先准备多个散列函数。
fi(key) = RHi(key) (i=1,2,…,k)
这里RHi就是不同的散列函数，你可以把前面提到的除留余数、折叠、平方取中全部用上。每当发生散列地址冲突时，就换一个散列函数计算，相信总有一个可以吧冲突解决掉。这种方法能够使关键字不产生聚集，当然，相应地也增加了计算时间。
3.链地址法
将所有关键字为同义词的记录存储在一个单链表中，我们称这种表为同义词字表，在散列表中指存储所有同义词字表的头指针。
---》》连地址法对于可能会造成很多冲突的散列函数来说，提供了绝不会出现找不到地址的保障。当然，这也就带来了查找时需要遍历单链表的性能损耗。
4.公共溢出区法
将冲突的另外简历一个公共的溢出区来存放。
在查找时，对给定值通过散列函数计算出散列地址后，先与基本表的相应位置进行对比，如果相等，则查找成功，否则到溢出表去顺序查找。如果相对于基本表而言，有冲突的数据很少的情况下，公共溢出区的结构对于查找性能来说还是非常高的。
散列表查找实现：
散列表结构的定义，其中HashTable就是散列表结构。结构中elem为一个动态数组：
#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 12 //定义散列表长为数组的长度
#define UNLLKEY -32768
typedef struct
{
int *elem;//数据元素存储基址，动态分配数组
int count;//当前数据元素个数
}HashTable;
int m = 0;//散列表表长，全局变量
有了结构定义，以下对散列表进行初始化
/*初始化散列表*/
Status InitHashTable(HashTable *H)
{
int i;
m = HASHSIZE;
H->count = m;
H->elem = (int *)malloc(m*sizeof(int));
for(i = 0;i<m;i++)
H->elem[i] = UNLLKEY;
return OK;
}
为了插入时计算地址，我们需要定义散列函数，散列函数可以根据不同情况更改算法。
/*散列函数*/
int Hash(int key)
{
return key % m;//除留余数法
}
初始化完成后，我们可以对散列表进行插入操作。假设我们的关键字集合如下：
{12,67,56,16,25,37,22,29,15,47,48,34}
/*插入关键字进散列表*/
void InsertHash(HashTable *H,int key)
{
int addr = Hash(key);//求散列址
while(H->elem[addr]!=NULLKEY)//如果不为空，则冲突
addr = (addr+1)%m;//开放定址法的线性探测，也可以改用其他的方法
H->elem[addr] = key;//直到有空位后插入关键字
}
散列表存在后，我们再需要时就可以通过散列表查找要的记录
/*散列表查找关键字*/
Status SearchHash(HashTable H,int key, int *addr)
{
*addr = Hash(key);//求散列地址
while(H.elem[*addr]!=key)//如果不为空，则冲突
{
*addr = (*addr+1)%m;//开放定址法的线性探测
if(H.elem[*addr]==NULLKEY||*addr==Hash(key))
{//如果循环回到原点
return UNSUCCESS;//则说明关键字不存在
}
}
return SUCCESS;
}
查找的代码与插入的代码非常类似，只需要做一个不存在关键字的判断而已。
散列表的查找性能分析：
如果"没有冲突"则为O(1).
散列查找的平均查找长度取决于以下因素：
1.散列函数是否均匀--》》由于不同的散列函数对于同一组随机的关键字，产生的冲突的可能性是相同的，因此不考虑其对平均查找长度的影响。
2.处理冲突的方法--》》相同的关键字、相同的散列函数，但处理冲突的方法不同，会使得平均查找长度不同。比如线性探测处理冲突可能会昌盛堆积，显然没有二次探测法好，而链地址法处理冲突不会产生任何堆积，因而具有更佳的平均查找性能。
3.散列表的填装因子：
所谓填装因子α = 填入表中记录个数/散列表长度。α标志着散列表的装满的程度。当填入表中的记录越多，α越大，产生冲突的可能性越大。也就是说，散列表的平均查找长度取决于填装因子，而不是取决于查找集合中的记录个数。
不管记录个数n有多大，我们总可以选择一个合适的填装因子以便将平均查找长度限定在一个范围之内，此时我们散列查找的时间复杂度就真的是O(1)了。为此，我们通常间散列表的空间设置得比 号召集合大，此时虽然会浪费一定的空间，但是换来的查找效率大大的提升，总的来说，还是非常值得。 P c ch