四 搜索引擎的索引系统

目标:存的下,查的块

1.1 信息

信息是能够被传达和理解的信息.

1.2索引

索引也是一种信息,是信息的信息,描述信息的信息.eg目录

1.3倒排索引,倒排表,临时倒排文件,最终倒排文件

倒排表是指存放在内存中的能够追加倒排记录的倒排索引。倒排表是迷你的倒排索引。

临时倒排文件是指存放在磁盘中，以文件的形式存储的不能够追加倒排记录的倒排索引。临时倒排文件是中等规模的倒排索引。

最终倒排文件是指由存放在磁盘中，以文件的形式存储的临时倒排文件归并得到的倒排索引。最终倒排文件是较大规模的倒排索引。

倒排索引作为抽象概念，而倒排表、临时倒排文件、最终倒排文件是倒排索引的三种不同的表现形式。

1.4 其他概念

索引部分概念很多，因此本章4.2~4.4 节分别介绍全文检索、文档编号、正排索引、倒排索引的基本概念。在集中理解索引系统的主要概念后，接下来再了解索引创建中的一些计算细节。

2 全文检索

全文检索（full-text retrieval）技术的出现是信息检索领域的一场革命，它细化了信息检索的粒度，提供了实现多角度，多侧面且全新的信息检索体验。因此搜索引擎全面采用了这种崭新的技术，并使之成为主流的检索方法。

早期的信息检索主要通过检索数据信息的外部特征，例如标题、作者、摘要、附录及资料的编号等。这样的检索系统常见于图书馆的馆藏图书检索中，它主要存在如下两个大问题。

（1）检索结果排序不理想。
（2）只能对标题进行检索。

出现这些问题是因为没有考虑到文档内容（本章使用文档笼统地代表书籍或者网页）。全文检索顾名思义，是对文档的全部信息进行检索，这些信息包括标题和正文等。简单地说，全文检索的内在本质归纳起来就是如下两条。

（1）文档的全部文字参与索引。
（2）检索结果能够提供检索词出现的实际位置。

在全文检索的过程中，只需要用户提供一个或多个检索关键词,不仅能检索出命中文本,还能提供关键词出现在文本中的位置.

3.1 文档编号

一个唯一描述文档的Id.

检索在索引的基础上完成,得到一组匹配关键词的文档编号.继而文档编号在文档信息库中取出,通过一系列计算战士出来,文档编号发挥重要作用.

3.2 文档编号的方法

文档编号需要满足条件:
(1) 任何一个文档在其生命周期只有一个编号.
(2) 任何两个不同文档编号不同
(3) 编号在计算中尽可能高效,并且便于存储,越短越好

3.3 游戏编码

使用这种方法进行编号长度压缩.对于单调递增的文件编码,采用增量整数序列变为"差分编码"
eg: 1, 16, 17, 35, 420, 23, 2944 表示的文档编号分别为  前n项和.

好处:序列中的数字都比较小,便于存储
坏处:获取某个编码需要从头累加,且一旦却是数据块,那么后边的编码将无法计算

另一种变长编码(ariable Byte Coding)

这时一种字节对齐的编码方式,将整数转化为二进制后,以7位为单位分段.每段段尾增加一位0表示最后一段,1表示还有后续段.
采用这种方式的好处是字节对齐,编码和解码都比较容易.

所以最终编码方式为游戏编码结合变长编码处理文档编号.
ps:变长编码的好处在于,将原先的差分编码进行优化压缩,减少小数字占用空间.

4 倒排索引

4.1 经典的倒排索引

经典倒排索引

索引中的三个概念

命中率(Hit) 表示索引词在文章中出现的位置和字体等信息
正排索引(Forward Index)
倒排索引(Inverted Index)

4.2 正排索引(前向索引)

正排索引 正排索引实例 冗余DocId的正排索引

正排索引是创建倒排索引的基础.具有以下字段

(1) LocalId表示文档的局部编号
(2) WordId表示文档分词后的编号,也称"索引词编号"
(3)NHits表示某个索引词在文档中出现的次数
(4)HitList表示某个索引词在文档出现的位置,相对于正文的偏移量(基于游戏编码的差分序列,采用变长编码的方式处理)

正排索引以文档编号为视角看待索引词,也就是通过文档编号找索引词.
然而全文检索的特性是通过关键词来检索,而不是通过文档编号来检索,因此正排不能满足全文索引要求,但是却为倒排索引创造了有力条件

4.3 倒排索引

倒排索引字典-记录表

倒排索引是一种以关键字和文件编号结合,并以关键词作为主键的索引结构

倒排索引两部分:
(1)由不同索引词组成索引表,称为 "词典"
(2)由每个索引词出现过的文档以及命中位置等信息组成,称为"记录表"

倒排索引中的DocId存放顺序问题.

三种策略
(1) 按照DocId升序
(2) 按照索引词出现次数降序
(3) 记录表分块存放,块内按照DocId升序,块间按照PageRank存放

第三种方案既照顾了(1) 的有序压缩问题,又照顾了重要文档优先检索的需要.

总结:正排索引和倒排索引的关系
本质讲,存在这样两个空间,一个称为索引词空间,一个称为文档空间
正排索引理解为定义在文档空间到索引空间的一个映射.任意一个文档对应唯一的一组索引词
倒排索引理解为定义在索引空间到文档空间的一个映射.任意一个索引词对应唯一命中文档
因此,从文档到正排索引,从正排索引到倒排索引可以理解为这种关系,给出一个索引词,就可以通过倒排索引得到命中文档及位置信息

5 数据规模的估计

对于tb数量级的文档,单纯的保存文档编号,就需要很大一部分空间,家生Hit等信息,那么就问题更大了.所以下边主要涉及"

6 设计存储规模的一些计算

6.1 正排表和倒排表的合并

下载系统将抓取的网页存放在网页库中,分析系统在分析后得到网页对象发送给索引系统.因此,索引系统一直得到这样的网页对象

正排表 倒排表 正排表与倒排表合并的结构

注:正排表和倒排表合并就是将正排表的数据追加到倒排表的数据过程,追加后,正排表不保留.而倒排在内存中存储一定的记录后,成批顺序写入磁盘,成为临时倒排文件

临时倒排文件

6.2 多个临时倒排文件的归并

方法:
(1) 拉链法和二路归并
(2) 拉链法和多路归并

归并的方法:
(1) 从头开始读取两个临时倒排文件的一部分(eg每次读取10MB)
(2) 分别对DocId进行解压,将解压的差分序列还原成原始差分序列
(3) 进行归并操作
(4) 归并结果进行压缩
(5) 写入归并后的临时倒排文件1&2中

这种开链法采用的是处理大文件的一种通用思路,即每次仅取出大文件的一部分在内存中进行计算.

注:对于2路归并,需要log(2)64,这样对于一个大文件,会有太多的临时文件产生.所以影响效率.于是使用多路归并更好点

6.3 倒排索引分布式存储

两种方案
多索引节点(多主机)方法:加快倒排文件创建速度;提高检索效果

按照DocId进行划分结果称为"局部倒排文件"
按照WordId 进行划分结果称为"全局倒排文件"

注:全局/局部都是相对于索引词来讲的.

局部方案 全局方案

全局方案好处:索引一个词,可能只需要访问全部包含索引词的节点,

减少了磁盘I/O,当检索两个词时,那么可以做到并发执行(两个节点),如果将索引看作是服务,那么可以做到64个窗口同时提供服务,局部方案则需要单窗口排队服务

;局部方案则需要访问所有部分包含索引词的节点.

缺点:一蹦全崩;等待索引节点全部传输,速度慢,低效

局部方案:相对有利点:(1)可靠性高,(2)降低网路负载,提高查询效率
充分利用网络宽带,对于一个索引,并发传输
缺点:单窗口排队

所以:局部方案有利于并发获取索引节果;全局方案有利于查询.so 局部方案在查询结果获取方面是有优势的,且可靠性保证,因此业界使用.但当检索词相对均匀分布时,那么全局方式在性能上是最佳的

6.4 倒排文件缓存

6.5 倒排索引词典统计信息的计算

在索引系统中,关于索引词出现文档数的统计是在查询请求发生之前预先计算好的,是倒排表的词典部分不可分割的一部分.--统计员(全局的)

7 倒排索引文件的创建过程

7.1 创建倒排表 单个索引节点倒排文件的创建过程

计算角度讲,临时倒排文件创建过程包括磁盘读取(从网页库读取一个文档),计算(正排计算,归并),写入磁盘(写入临时倒排文件)

所以可以使用两个线程并发处理,流水线方式

两个线程进行并发处理

7.2 计算统计信息

方法1:从正排表开始统计;(耗费一定的内存空间)

方法1,基于全局索引词出现文档次数的统计方法

方法2:从临时文件开始统计;(需要等待最慢的索引节点计算完成后开始计算)