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

一、基本概念

检索:

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

检索的效率非常重要:

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

二、提高检索效率的方法

  • 预排序

    • 排序算法本身比较费时
    • 只是预处理(在检索之前已完成)
  • 建立索引

    • 检索事充分利用辅助索引信息
    • 牺牲一定的空间
    • 从而提高检索效率
  • 散列技术

    • 把数据组织到一个表中
    • 根据关键码的值确定表中记录的位置
    • 确定:不适合进行范围查询; 一般也不允许出现重复关键码

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

三、平均检索长度(ASL)

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

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

    • 检索过程中对关键码的平均比较次数
    • 衡量检索算法优劣的时间标准

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

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

四、思考

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

参考资料

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

个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn

Sam avatar
About Sam
专注生物信息 专注转化医学