知识要点：
线性索引结构、倒排表、静态搜索树的结构和特点；
B树的结构；（B-树，B+树）
散列的实现原理和各种操作的实现算法。（Hash表，平均查找长度（成功、失败））
1.散列函数和散列地址：记录存取位置P和关键字Key之间的对应关系，有P=Function(Key),这个对应关系Function称为散列函数
通过此函数得出的P称为散列地址。
2.散列表：一个有限的连续的地址空间。（通常采用以为数组存取，此时的散列地址对应的就是数组的下标，数组内
保存的值就是关键字Key。）
3.冲突和同义词：由于散列函数的缺陷不同的关键字Key可能对应到同一散列地址上，这种现象称为冲突。发生冲突的关键字互
称为当前散列函数Function的同义词。（散列函数的缺陷引发冲突，发生冲突的关键词互为同义词）
☆散列函数的构造方法：（数字分析法、平方取中法、折叠法、除留余数法）
常用的就是除留余数法，Function(Key)=Key%p
Key为所要保存的关键字、p为一个不大于散列表长度的数，一帮情况下p取不大于表长的最大质数。
优点：保证了关键字所对应的散列地址一定在散列表所对应的地址空间中。
☆冲突的处理方法：（开放地址法：线性探测法、二次探测法、伪随机探测法；链地址法）
开放地址法：以空间为代价，散列表大小固定
函数原型：Function(Key)=(Function(Key)+d)%m，Key为关键字、m为散列表长、d为递增量
当d=1时--》线性探测法，当d=1,-1,4,-4,...k*k,-k*k(k<=m/2)时--》二次探测法，当d=伪随机数时--》伪随机探测法
二次聚集（堆积）：处理同义词冲突过程中有增添了非同义词冲突。（处理冲突时的方法缺陷引起了聚集现象）
链地址法：散列表动态增长（不会发生二次聚集现象）
思想把具有相同散列地址的关键字放在同一个链表中。m个散列地址对应着m个单链表。
☆☆☆散列表查找性能的分析以及平均查找长度：
查找的影响因素（散列函数、处理冲突的方法、散列表的填装因子）
1.填装因子A的定义（散列表装满的程度）：
A=已填充的记录数/散列表长度，A越小发生冲突的可能性就越小、A越大发生冲突的可能性就越大。
（记忆）不同处理冲突方法的平均查找长度：平均查找长度的大小与记录个数n无关，散列列表的填装因子有关。
线性探测法：增量为1；成功：1/2 (1+1/(1-A)) 失败：1/2 (1+1/(1-A)^2)
二次探测法：增量正负交替，按照平方进行；成功：-1/A ln(1-A) 失败：1/(1-A)
链地址法：无增量，在同一链式地址下面；成功：1+A/2 失败：A+e^-A
（在已知平均查找成功长度和查找表的存储元素个数可以求出散列表长度）
2.平均查找长度：（在查找概率相同的情况下）
查找成功：
查找成功平均比较次数=各个关键字的比较次数之和/关键字个数，
ASL(success)=1/n(C1+C2+.....+Cn) Cn为查找到第n个记录所需要进行比较的次数,n为表中记录个数。
查找失败：
查找失败对应的两种情况。1）查找单元为空NULL。2）按照处理冲突的方法探测一遍之后仍未找到。
假设散列函数取值的个数为r,则0--r-1相当于有r个查找失败的入口，从每个入口进入到失败为止，其关键字的比较次数
就是与该入口对应的查找失败的查找长度。
ASL(default)=1/r(C1+C2+.....+Cr) Cr为散列函数取值为r时查找失败比较次数,r为散列函数取值个数。
例题：使用散列函数H(key)-key%11，将数据{1，13，12，34，38，33，27，22}加入散列表中,
采用线性探测法（增长因子d为1）：
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 散列值 | 33 | 1 | 13 | 12 | 34 | 38 | 27 | 22 | |||
| 比较次数 | 1 | 1 | 1 | 3 | 4 | 1 | 2 | 8 |
查找成功的平均比较次数：（1*4+3+4+2+8）/8=21/8；
查找失败的比较次数：(3+(2+9)*4)/11=47/11；（散列地址空间内的元素查找）
B-树定义：要么为空树、要么为满足下列性质的m叉树；
1）树中至多每个结点有m个子树；
2）如果根结点不是叶子结点，则根结点至少有两颗子树；
3）除了根结点以外的其他非终端结点至少有m/2上取整颗子树；
4）所有的叶子结点必然在同一层次上，而且不携带有信息，通常称为失败结点；
5）所有非终端结点至多有m-1个关键字；
性质：平衡（所有叶子结点均在同一层次上）、有序（结点内部关键字大小有序）、多路（m叉树）；
总结：m叉树，每个结点最多有m-1个关键字；至少有m/2上取整-1个关键字；
（结点数k，(m/2)-1<=k<=m-1）
树的最大分支数（关键字的个数+1）决定了该树的阶数；
B-树的查找类似于分块查找和顺序查找：查找顺序从根结点开始，由上至下查找关键字所在结点的位置，在每个结点内部
采用顺序查找的方式查找关键字，如果查到叶子结点则表明查找失败。
B-树的插入：（由上到下查找插入结点位置）
在最底层某个非终端结点添加一个关键字，如果插入后此结点关键字个数小于等于m-1则插入成功；
如果大于m-1则将此结点以中间关键字为界限一分为二，并将中间关键字移入双亲结点上，如果双亲结点已满，
则按照同样的方法进行分裂；
B-树的删除：1）被删关键字所在结点内关键字数目不小于m/2上取整，则直接去掉与其对应的指针即可（直接删除）
2）被删关键字所在结点关键字数目等于m/2上取整减1，而与其相邻的右（左）兄弟结点中的关键字个数
大于m/2上取整减1，则将其兄弟结点中的最大（最小）的关键字上移至双亲结点中，而将双亲节点中
而将双亲结点中大于（小于）且紧靠该上移关键字的关键字下移至被删关键字所在的结点位置。
3）被删关键字所在结点和其相邻兄弟结点的关键字数目均小于m/2上取整减1。假设该结点有左右兄弟，
且其右兄弟结点地址由双亲结点中的指针P所指，则在删除关键字之后，它所在结点中剩余关键字
和指针，加上双亲结点中的关键字K一起合并到，P所指的兄弟结点中去（若没有右兄弟，则合并到左兄弟中）
B-树的应用：磁盘管理系统的目录管理、数据库系统中的索引组织管理；
B+树的定义：1）有n颗子树结点含有n个关键字；
2）所有叶子结点中包含了全部关键字信息，以及指向含这些关键字记录的指针，且叶子结点本身
关键字的大小自小而大顺序连接；
3）非终端结点可以看成索引部分，结点中仅含有其子树（根结点）中最大（最小）的关键字；