WZX's blog 海滩上捡贝壳的孩子

线性表检索与静态索引检索


线性表检索与静态索引检索的实现与比较

评价指标

  • 平均检索长度 ASL (Average Search Length)
    • 检索过程中对关键码的平均比较次数
    • $ASL=\sum^n_{i=1}P_iC_i$
      • $P_i$ 为检索第 $i$ 个元素的概率
      • $C_i$ 为找到第 $i$ 个元素所需的关键码值与给定值的比较次数
  • 空间复杂度
  • 算法复杂度

线性表检索

顺序检索

想法非常简单,对线性表的所有元素逐个进行关键码的比较

成功的平均检索长度为 $ASL=\sum_{i=0}^{n-1}\frac{1}{n}(n-i)=\frac{n+1}{2}$

顺序检索的优点是插入元素的时间复杂度是 $O(1)$。缺点是检索时间太长,是 $O(n)$ 级别

二分检索

在关键码有序的基础上,从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

成功的平均检索长度为 $ASL=log_2(n+1)-1$

二分检索的优点是检索时间短 $O(1)$,缺点是元素修改后需要排序

分块检索

将线性表分成多个块,前一块最大关键码必须小于后一块最小关键码,每一块中的关键码不一定有序

在块间应用二分检索,在块内应用顺序检索,这是对顺序检索和二分检索的折中

静态索引检索

稠密索引与稀疏索引

  • 每个记录建立一个索引项,保存所有记录的主码与指向记录存储位置的指针,这是稠密索引
  • 在稠密索引的基础上,对一组记录建立一个索引项,这是稀疏索引,也是二级索引

应用多级索引时,使用多叉树(多路查找树)组织索引,尽量使每个结点的数据大小与磁盘块的大小一致,以在减少IO操作同时使树尽可能矮。多叉树就是每个结点可以存储多个元素且拥有多个孩子的树

倒排索引(Inverted Index)

倒排表由属性-指针(关键码或者记录的存储地址)对组成,适用于根据某个或若干个属性来检索记录的场景。一般的索引都是关键码为key,而这里反了过来,所以称为倒排索引。

使用词索引全文索引可以对文本内容快速检索。

  • 词索引:从所有文档中抽取关键词作为倒排索引的key,value保存文档编号和在文本中的位置。使用相对广泛。
  • 全文索引:把文档看作一个长的字符串,key为子串的开始位置,如果对每个字符建立索引,就可以查询所有子串

REFERENCE

[1]静态索引. 数据结构与算法[EB/OL].
[2]倒排索引 - 北京大学[EB/OL]. Coursera.
[3]线性表索引 - 北京大学[EB/OL]. Coursera.


Similar Posts

上一篇 哈希表检索

下一篇 B树与B+树

Comments