一、线性结构查找

1、顺序查找
（1）无序的线性查找
基本思想：从线性表的一端开始，逐个检查关键字是否满足给定的条件。特点：当N比较大时，查找效率低。

（2）有序的线性查找：查效率比无序查找略高。

2、折半查找
基本思想：折半查找又称二分查找，仅适用于有序的顺序表。将给定的值与表中间位置的元素比较，相等则查找成功；不相等则继续在中间元素以外的前半部分或后半部分继续查找；如此重复，直到找到为止，若没有指定元素，则查找失败。

案例：

3、分块查找
基本思想：吸取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找。将表分为若干子块，块内元素可以无序，块之间必须是有序的。
案例：88、24、72、61、21、6、32、11、8、31、22、83、78、54

二、树形结构查找

1、B树
B树：又叫多路平衡查找树，B树种所有结点的孩子个数的最大值称为B树的阶，通常用m表示。B树也是所有结点的平衡因子均等于0的多路平衡查找树。

（1）m叉树的特性：

• 1）树中每个结点至多有m棵子树，即至多含有m-1个关键字；
• 2）若根节点不是终端结点，则至少有两棵子树；
• 3）除根结点外的所有非叶节点至少有m/2棵子树，至少有m/2-1个关键字；
• 4）所有非叶结点的结构如下：
  
• 5）所有的叶结点都出现在同一层次上，并且不带信息

案例：

（2）B树的高度范围：

（3）B树的用途
使用B-tree结构可以显著减少定位记录时所经历的中间过程，从而加快存取速度。这个数据结构一般用于数据库的索引，综合效率较高。

（4）B树的查找
B树的查找：类似二叉排序树的查找，不同的是B树每个结点上是有多个关键字的有序表，在到达某个结点时，先在有序表中查找，若找到，则查找成功；否则，到按照对应的指针信息指向的子树中去查找，当到达叶子结点时，则说明树中没有对应的关键码。
案例：

• 1）首先从根节点a开始，因为 a 节点中只有一个关键字35，且给定值47 > 关键字35，则若存在必在指针A1所指的子树内。
• 2）顺指针找到 c节点，该节点有两个关键字（43和 78），而43 < 47 < 78,若存在比在指针A1所指的子树中。
• 3）同样，顺指针找到 g节点，在该节点找到关键字47,查找成功。

（4）B树的插入（可能涉及结点的分裂）
案例：3阶B树，假设需依次插入关键字30，26，85。

• 1）首先通过查找确定插入的位置。由根节点a开始查找，确定30应插入的在d 节点中。由于d 中关键字数目不超过2（即m-1），故第一个关键字插入完成：如图（b）
  
• 2）同样，通过查找确定关键字26亦应插入 d， 由于d节点关键字数目超过2，此时需要将 d分裂成两个节点，关键字26及其前、后两个指针仍保留在 d 节点中。而关键字37 及其前、后两个指针存储到新的产生的节点 d中。同时将关键字30 和指示节点 d的指针插入到其双亲的节点中。由于 b节点中的关键字数目没有超过2，则插入完成.如图（c）(d)
  
  
• 3） (e) -(g) 为插入85后；
  
  
  

（5）B树的删除（可能涉及结点的合并操作）

• 1）被删关键字K不在终端结点，可以用K的前驱或后继k来替代K，然后在相应的结点中删除k，关键字k必定落在某个终端结点中。
  
• 2）被删的关键字在终端结点中，有三种情况：
  a、直接删除关键字：若被删关键字所在结点的关键字个数≥m/2，则可直接删除关键字；
  b、兄弟够借：若被删关键字所在结点的关键字个数=m/2-1，且与此节点相邻的兄弟结点的关键字个数≥m/2，则需要调整该结点、兄弟结点及其双亲结点，以达到新的平衡；
  
  c：兄弟不够借：若被删关键字所在结点的关键字个数=m/2-1，且与此节点相邻的兄弟结点的关键字个数均=m/2-1，则将关键字删除后与兄弟节点及其双亲节点中的关键字合并。
  

2、B+树

（1）B+树的特征以及与B树的差别

（2）每个叶子节点都有一个指针，指向下一个数据，形成一个有序链表。而只有叶子节点才会有data，其他都是索引。

（3）B+树的插入
案例：阶数为5。

• a）空树中插入5。
  

• b）依次插入8，10，15，16。
  
  插入16后产生分裂：
  

• c）插入17，18
  
  插入18后产生分裂：
  

• d) 插入几个数据后。
  

• e)再继续插入7。
  
  
  最终的分裂结果：
  

三、散列表