欢迎大家访问我的个人博客：endeavorchuan.com

静态查找表：若一查找表的操作只涉及查询及检索，则称为静态查找表。（顺序查找、折半查找、散列查找）

动态查找表：需要动态的插入或删除的查找表，称为动态查找表。（二叉排序树的查找、散列查找）

平均查找长度：所有查找过程中进行关键字的比较次数的平均值。

n为查找表的长度；Pi是查找第i个数据元素的概率，Pi=1/n；Ci是找到第i个数据元素所需进行的比较次数。

顺序查找

一般线性表的顺序查找：

从线性表一端开始，逐个检查关键字是否满足给定条件。若查找到某个元素的关键字满足给定条件，则查找成功，返回元素在线性表中的位置；若已查到表的另一端，还未有符合给定条件的元素，则查找失败。

引入哨兵元素为ST.elem[0]，采用从后向前的查找方式，若在查找表中没有找到符合条件的数据元素，则最后一个查找的位置为0号节点，即哨兵节点，最后返回值即为0，表示查找失败，不必再使用判断语句进行查找失败提示。

缺点：当n较大时，平均查找长度较大；优点：对数据元素存储没有要求。

有序表的顺序查找：

若查找之前就已知表的关键字有序，查找失败时不必比较到表的另一端，就可返回查找失败的信息，可降低顺序查找失败的平均查找长度。

查找顺序从前往后，待查找关键字为key，查找到第i个元素时，i＜key，但i+1>key，此时可返回查找失败。

折半查找（二分查找）

仅适用于有序的顺序表。

将key的值与查找表中间的关键字进行比较，若大于中间关键字，则在后半部分继续比较；若小于中间关键字，则在前半部分比较。依次比较后半部分或前半部分的中间元素，直到查找成功为止。

例如：已知11个元素的有序表，查找值为32的元素。
①

②

③



平均情况下比顺序查找的效率高。

分块查找（索引顺序查找）

将查找表分成若干子块。块内元素无序，但是块间有序。

即第一个块中最大的关键字，小于第二个块中的所有关键字，依次类推。

再建立一个索引表，存储各块中最大关键字和各块中第一个元素的地址。

查找步骤：

1. 在索引中确定待查记录所在的块，顺序查找或折半查找索引表；
2. 在子块内顺序查找。

查找表：

索引表：

分块查找的平均查找长度为索引查找(LI)和块内查找(LS)的平均长度之和。

B树（多路平衡查找树）

平衡二叉树：①必须是二叉查找树；②每个节点的左子树和右子树高度差至多为1。

B树的阶：B树中所有结点的孩子结点数的最大值，用m表示。

B树特性：

• 树中每个结点至多有m棵子树；
• 若根节点不是终端结点，则至少有两棵子树；
• 除根节点外的所有非叶结点至少有m/2棵子树；
• 所有叶结点都出现在同一层次上，并且不带信息；
• B树是所有结点的平衡因子均等于0的多路查找树。

B树的高度

B树的高度不包括最后的不带任何信息的叶节结点所处的那一层。

对于n个关键字，高度为h，阶数为m的B树：

• 树中关键字的个数应该满足：n≤m^h-1。
• 树的高度logm(n+1)≤h≤logm/2[(n+1)/2]+1
• 若每个结点中关键字个数达到最少，则容纳同样多关键字的B树的高度达到最大。

例如，一棵3阶B树共有8个关键字，则其高度为2≤h≤3.17。

B树的查找

B树常存储在磁盘上。

①在B树中找结点：在磁盘上进行查找。

②在结点内找关键字k：在内存中进行。在找到目标结点后，先将结点信息读如内存，再查找等于k的关键字。

在B树上查找到某个结点后，先在有序表中进行查找，查找到叶结点时，则说明树中没有对应的关键字，查找失败。

B树的插入

①定位：利用B树查找算法，找出插入这个关键字的最低层中的某个非叶结点（B树中插入关键字一定插入在最低层非叶结点内）。

②插入：在B树中，关键字个数存在限制，若插入后关键字个数小于m，则可以直接插入；若插入后关键字个数大于m-1，则必须对结点进行分裂。
结点分裂：

B树的删除

由于B树节点中关键字个数存在限制，所以删除结点后，要使得关键字个数≥(m/2)-1。

k不在最低层非叶结点时：

• 若小于k的子树中关键字个数大于(m/2)-1，找出k的前驱k’，用k’代替k，并递归删除k’。
• 若大于k的子树中关键字个数大于(m/2)-1，找出k的后继k’，用k’代替k，并递归删除k’。
• 若前后两个子树中的关键字个数均为(m/2)-1，则直接将两个子结点合并，直接删除k即可。

k在最低层非叶结点时：

• 直接删除关键字：若被删除关键字所在结点关键字个数大于(m/2)-1，说明删除后仍满足B树的定义，可以直接删去。
• 兄弟够借：被删除关键字所在的结点删除前的关键字个数等于(m/2)-1，且与此结点相邻的左右兄弟结点的关键字个数大于等于(m/2)-1，则需调整该结点、左右兄弟结点及其双亲结点，从而达到新的平衡。
• 兄弟不够借：若被删除的关键字所在的结点删除前的关键字个数等于(m/2)-1，且此时与该结点相邻的左右关键字数都等于(m/2)-1，则将关键字删除后与左右兄弟结点及双亲结点进行合并。

在关键字合并的过程中，需要对树不断调整，直至符合B树的要求为止。

B+树

一棵m阶B+树应该满足：

• 每个分支结点最多有m棵子树；
• 非叶根结点至少有两棵子树，其他每个分支结点至少有m/2棵子树；
• 结点的子树个数与关键字的个数相等；
• 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小排列，且相邻叶结点按大小顺序相互链接；
• 所有分支结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针。
  

B+树中通常有两个头指针：①指向根节点；②指向关键字最小的叶结点。

故可对B+树进行两种查找：①从最小关键字起顺序查找；②从根结点起多路查找。

B+树在查找过程中，非叶结点上的关键字值等于给定值时不终止，而是继续向下查找，直到叶结点上的该关键字为止。