【10.1】检索--检索基本概念

一、基本概念

检索:

在一组记录集合中找到关键码值等于 给定值的某个记录，戒者找到关键码 值符合特定条件的某些记录的过程

检索的效率非常重要:

• 尤其对于大数据量
• 需要对数据进行特殊的存储处理

二、提高检索效率的方法

• 预排序

• 排序算法本身比较费时

• 只是预处理（在检索之前已完成）

• 建立索引

• 检索事充分利用辅助索引信息

• 牺牲一定的空间

• 从而提高检索效率

• 散列技术

• 把数据组织到一个表中

• 根据关键码的值确定表中记录的位置

• 确定：不适合进行范围查询； 一般也不允许出现重复关键码

当散列方法不适合于基于磁盘的应用 程序时，我们可以选择 B 树方法

三、平均检索长度(ASL)

• 关键码的比较:检索运算的主要操作

• 平均检索长度(Average Search Length)

• 检索过程中对关键码的平均比较次数

• 衡量检索算法优劣的时间标准

四、检索算法评估的其他问题

• 衡量一个检索算法还需要考虑
• 算法所需的存储量
• 算法的繁杂性
• …

四、思考

• 假设线性表为(a, b, c)检索 a、b、c 的概率分别为 0.4、0.1、0.5
• 顺序检索算法的平均检索长度是多少?(即 平均需要多少此次比较给定值与表中关键码 值才能找到待查元素)

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾