查找的基本概念
查找： 在数据集合中寻找满?某种条件的数据元素的过程称为查找 。查找结果只有两种：成功/失败。
查找表（查找结构）： 用于查找的数据集合称为查找表，它由同?类型的数据元素（或记录）组成，可以是一个数组或链表等数据类型。查找表的常见操作：①查找符合体条件的数据元素，②插入、删除某个数据元素。
静态查找表： 若一个查找表的操作不涉及到插入、删除操作，则无须动态地修改查找表。此类查找表称为静态查找表，反之为动态查找表
关键字： 数据元素中唯?标识该元素的某个数据项的值，使?基于关键字的查找，查找结果应该是唯?的。
查找长度： 在查找运算中，需要对?关键字的次数称为查找长度。
平均查找长度（ASL, Average Search Length）： 所有查找过程中进?关键字的?较次数的平均值。
适合静态查找表的查找方法：顺序查找、折半查找、散列查找等；
适合动态查找表的查找方法：二叉树排序树的查找、散列查找等。二叉平衡树和B树都是二叉排序树的改进。
顺序查找和折半查找
顺序查找
顺序查找，?叫 “线性查找”，通常?于线性表。
算法思想：从头到尾挨个找（或者反过来也OK）
**设立哨兵查找方式：**设置第一位置尾哨兵，从尾端往头部开始依次查找。查找成功，则返回元素下标；查找失败，则返回 0。
**有序表的顺序查找：**若在查找之前就已经知道表的关键字有序的，则查找失败时可以不用再比较到表的另一端就能返回查找失败的信息，从而降低顺序查找失败的平均查找长度。
折半查找
折半查找，?称 “?分查找”，仅适?于有序的顺序表。
分块查找
分块查找又称索引顺序查找，它吸取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找。
B树和B+树
B树的基本概念
B树，?称多路平衡查找树，B树中所有结点的孩?个数的最大值称为B树的阶，通常?m表示。?棵m阶B树
或为空树，或为满?如下特性的m叉树：
- 树中每个结点?多有m棵?树，即?多含有m-1个关键字。
- 若根结点不是终端结点，则?少有两棵?树。
- 除根结点外的所有?叶结点?少有 棵?树，即?少含有 -1个关键字。
- 所有?叶结点的结构如下：
- 所有的叶结点都出现在同?层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失
败结点，实际上这些结点不存在，指向这些结点的指针为空）。
m阶B树的核心特性：
- 根节点的?树数∈[2, m]，关键字数∈[1, m-1]。 其他结点的?树数∈[ , m]；关键字数∈[ -1, m-1]
- 对任?结点，其所有?树?度都相同
- 关键字的值：?树0<关键字1<?树1<关键字2<?树2<…. (类比?叉查找树 左<中<右)
B+树的高度
**最小高度：**让每个结点尽可能的满，有m-1个关键字，m个分叉，则有 n≤(m ? 1)(1 + m + m2 + m3 + . . . + mh?1) = mh ? 1， 因此 h ≥ logm(n + 1)
**最大高度：**让各层的分叉尽可能的少，即根节点只有2个分叉，其他结点只有[m/2]个分叉
各层结点?少有：第?层 1、第?层 2、第三层 2 … 第h层 2(?m/2?)h?2
第h+1层共有叶子结点（失败结点）2(?m/2?)h?1?个
B+树的基本概念
?棵m阶的B+树需满?下列条件：
- 每个分?结点最多有m棵?树（孩?结点）。
- 非叶根结点?少有两棵?树，其他每个分?结点?少有 棵?树。
- 结点的?树个数与关键字个数相等。
- 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。
- 所有分?结点中仅包含它的各个子结点中关键字的最大值及指向其?结点的指针。
m阶的B+树与m阶的B树的主要差异如下：
- 在B+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树；而在B树中，具有n个关键字的结点含有n+1棵子树。
- 在B+树中，每个结点(非根内部结点)的关键字个数n的范围是[m/27<n≤m(根结点:1<n<m)；在B树中，每个结点(非根内部结点)的关键字个数n的范围是1m/2-1<ns m-1(根结点:1<n<m-1)。
- 在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。
- 在B+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中；而在B树中，叶结点包含的关键字和其他结点包含的关键字是不重复的。