一、检索的基本概念和算法分类

1、检索概念：
    可以形式化地定义基于关键码的检索。假定k1、k2…kn是互不相同的关键码值，有一个包含n条记录的集合C，形式如下： (k1, R1)，(k2, R2)，…，(kn, Rn) 其中Rj是与关键码kj相关联的信息。给定某个关键码值K，检索问题( search problem )就是在C中定位记录(kj, Rj) ，使得kj = K。检索( searching )就是定位关键码值kj = K的记录的系统过程。

2、检索算法分类：
(1) 基于线性表的检索。例如，顺序检索、二分检索。
(2) 根据关键码值直接访问。例如，根据数组下标的直接检索、散列检索。
(3) 树索引方法。例如，二叉搜索树、字符树、B树。
(4) 基于属性的检索。例如，倒排表、倒排文件。