数据结构查找

基本概念

顺序查找

折半查找

只适用有序顺序表

分块查找

先查找分块，再块内顺序查找。
也可以对分块进行折半查找，索引表不包括目标关键字，则折半查找索引表停留在low>high，要在low所指分块中查找。

B树

B树又称多路平衡查找树，是一种组织和维护外存文件系统非常有效的数据结构。

• 插入和删除：

  B+树

  类似于分块查找，块关键字最大值为父节点关键字。
  无论查找成功/失败，都需要查找到叶子结点。也可以进行顺序查找。
  经典应用于关系型数据库的索引如MySQL。
• 区别：
  B+树中n给关键字对应n个子树，而B树对应n+1个子树。
  B+树关键字限制和B树关键字限制不同。
  B+树中叶子结点包括了所有的关键字（非叶子结点的关键字也会出现在叶子结点中），而B树结点关键字不重复。
  B+树中叶子结点包含信息，所有非叶子结点仅仅起到索引作用，不含有该关键字对应记录的存储地址，而B树结点都包含了关键字对应的记录的存储地址。

  散列查找

  常见散列函数： 处理冲突：
• 开放定址法：
• 拉链法：
• 再散列法：
• 总结：