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

评价指标

• 平均检索长度 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.