1 倒排索引建立与存储
倒排索引的建立在内存中进行，由于索引的建立的过程是动态的，随时需要新增词典项或倒排表项，并不能确定最终索引结构的大小，所以索引建立的过程一般采用基于链表的内存数据结构。（需要建立索引的文档内容较少时，也可以采用分配固定大小内存的方式来建立相应索引结构）。
索引建立完成后，需要对其进行序列化存储。通常我们需要将基于链表（基于指针）的数据结构转换成基于连续存储空间的数据结构，再保存到文件中。因为本地文件中无法保存指针信息，当文件重新读回内存时，地址都将发生变化，原来结构记录的指针信息也都无效了。而顺序存储的数据结构则无此问题，通过mmap映射到内存后，存储结构不受影响。
2 唯一性索引优化
这里所谓的唯一性索引，指的是关键词的索引，也就是我们所谓的词典，在词典中关键词是不容许重复。由于查询第一步就是先去索引结构的词典中查找到对应的关键词，接下来才能得到对应的倒排列表以及相关文档的信息，所以对词典（关键词的唯一性索引）的优化，对于搜索引擎查询效率有着很大的影响。
前面已经说到，索引过程中的词典一般可以采用链式哈希的方式进行存储，但实际存储到文件中，词典必须转化成顺序存储的数据结构，而查询时，也是将该顺序结构mmap到内容进行操作。所以词典的优化主要就是如何选择一种顺序存储的方式来表示原有的链式哈希。
这里首先要明白对于哈希选择和建立过程中几个比较重要的度量：
1） N：关键词的个数，即有多少个不同的切实际存在的关键词。例如，英语常用单词有5000个。
2） R：关键词的跨度，即最大序的关键词和最小序的关键词之间理论上可能有多少种可能的词。例如关键词有5000个，关键词对应的hash值也有5000个，hash值用64位表示，那可能hash跨度就是2的64次方(前提是0和2^64都可能出现，当实际关键词数值已知时，如最大值为15666，最小值为13，则实际跨度为15666 - 13)。
3） P：哈希数组的长度，即实际分配的用于存放关键词的hash数组的长度。hash数组越长，当然可能发生冲突的概率就越低。当P大于R时，即hash数组的长度超过实际关键词的跨度时，我们取N%P作为hash数组下标，这时几乎可以确定不会有任何冲突。但几乎没有人会这样做，除非N和R非常接近的前提，但多数情况下R要比N大很多。所以P的选择需要一定技巧，即不至于浪费空间，又能在空间上保证冲突的概率尽可能低。实际中我们P一般取值为大于(5/3)N的最小质数，以在查询性能和占用空间上取得平衡。
优化的词典结构一般有如下几种：
1）Closed Hash Table(闭链哈希表)，事实上这是一个循环数组，它的长度为P = 大于(5/3)N的最小质数，hash数组的长度远超过实际的关键词数，解决冲突的方式为直接在对应hash位置之后，找到一个空白位置（用0或-1标识）写入，查找时也是如此，直接从对应的hash位置开始比较，若找到对应的关键词（hash值）则返回相应结果，若碰到某一个空白位置仍没发现对应的关键词则表明该关键词不在索引结构中。
2）Skip List(跳表)，跳表相当于对于一般的顺序哈希表的改进，改进的方式主要是在“词典数组”的前面附加一个跳表数组。这里的“词典数组”加了引号，是为了形式上更好地与上一种闭链哈希表对比，但必须说明的是，这里的“词典数组”完全不是hash数组了（类似于现实中的词典，查找目录我们不知道某个单词在具体的那一页，但可以知道它在多少页开始后的一个章节内，章节内类似二分法进行查找），hash数组在没有冲突发生时，其查找复杂度为O（1）。这里的“词典数据”是根据实际最大关键词和最小关键词的跨度划分为R/64个块，每个块长度为64，内含不等个关键词，块内关键词完全按照相对词序顺序（请注意是顺序存放，而不是按hash方式）存放，查找时按二分法查找，最恶劣情况下复杂度为O（log block_length）这里block_length = 64。跳表数组的长度即为R/64，每个跳表数组项纪录对应序号的块中最小关键词的值，若该块中无关键词存放时，可用（0或-1标识）。查询时先查跳表部分（hash_of_keyword/64作为下标），可以快速判读一个关键词是否在hash数组中，若存在则可以快速定位相应的块，在相应的块中（块中按序连续存放的）进行二分法查找。
3）Tiered Dictionary(分层词典)，分层词典形式与跳表很相近，但在空间利用率上更为节省。它顺序地把所有关键词放入一个“词典数组”中（注意，这里是所有关键词顺序放入，因此没有跳表中存在空闲空间），然后也是采用分块的方式，每个块为64，总块数为N/64（注意因为前面已经提到是将所有关键词顺序放入“词典数组”中，词典数组的长度就是关键词的个数N，而非跨度R），每个块中都存放有64个关键词（除最后一个块外）。然后同样在数组的一端放置一个目录数组（类似于跳表，但为了区别于跳表，一般是置于数组尾部），目录数组的长度为N/64，每个数组项存放的是对应块中最大关键词的值。查找时，现在目录数组中找到第一个大于或等于目标关键词的值，若没找到则表明现在存放所有关键词的值都比目标关键词小，目标关键词不在当前索引结构中。所找到则跳跃到该目录数组项对应的块进行二分查找。需要说明的是，分层词典有着最高的空间利用率，但代价是查找性能相对也降低了一些，因为在快表中一些空间的区间，即不存在关键词区间，我们也通过相应的块的跳表项（0 或 -1）表示出来了。所以很多时候当查询词不在索引中时，我们很容易知道。但分层词典却做不到这一点，只要查询关键词的值在跨度范围内，我们无法预判该关键词是否存在于索引中，都要去跳跃到“词典数组中”查找（事实上，当目标关键词不存在时，我们在相应块中进行二分查找的复杂度是最高）。
4）开链哈希，相对循环数组形式的闭链哈希，开链哈希主要是为了解决闭链哈希（顺序查找空闲位置存放关键词来解决冲突）中关键词簇拥成片所带来的查找次数显著增加的问题而引进的。他解决冲突的方式是，统一将冲突链表序列化到主哈希数组之后。整个结构分为主哈希数组和冲突数组，冲突数组是顺序存放个关键词冲突队列的部分，主哈希数组中每一个像都有一个指针指向它的冲突队列在冲突数组中的位置，而冲突数组中每一项都有一个标志位，标志该项是不是某个冲突队列的最后一项。
5）开链哈希的内存优化形式，开链哈希中实际主哈希数组项和冲突数组项结构是一致的，所以每一项都至少有一个条约指针和一个终止标识，但实际很多关键词对应的项并没有使用这两个成员。所以一种进一步的优化形式是，主数组（类似于冲突数组）完全按序存放每一个hash值对应的冲突队列，另设一个不同类型的简洁查找数组，里面用于存放关键词hash值和其冲突队列在主数组位置关系的映射。查找时，和一般hash查找一样，先通过hash函数在查找数组中找到对应的项，该项存放的不是实际的关键词，而是关键词（含冲突关键词）在主数组中偏移位置，0标识该hash值不存在相应关键词。同时，冲突数组中存放的关键词值（或其它数据内容）中可以拿出一个比特用于表示是否为某一个冲突队列的最后一项。
6）实时增量索引中用于避免簇拥的闭式哈希，避免簇拥的方式很简单，一般是将hash数组有条件的放大，比如由P改为3P，实际上结果是每个关键词（每个hash值）对应的表现由一个变为了三个。hash函数也相应的改为index = 3*（keyword_value%P），通过加大hash数组的长度，使得关键词的物理存放位置更加离散化。
总结，索引的优化过程实际上是一个，空间和时间的tradeoff的过程。所谓空间是指的存放相应结构所需的物理内存（或磁盘空间）大小，所谓时间就是查找的效率或复杂度。
效率最高的方式，无疑是，通过扩展空间方式实现避免簇拥的闭式哈希，它的查找效率最高，几乎总能保证是O（1），但内存耗费也最大，长度P = 大于(5/3)N的最小质数时已经有很多的空闲空间，为了实现避免簇拥，扩展为3P，这种浪费无疑进一步变大。
空间最节省的方式，无疑是，分层词典，它类似于跳表方式，核心是完全没有任何空间浪费。但查找效率相比于扩展空间后的闭式哈希也降低了很多。特别是关键词在索引结构中是，最为恶劣（log block_length）。
3 索引更新策略
当有新的文档内容需要建立索引时，我们需要将新建立的索引和老的索引合并。合并的一般方式有如下几种：
a 完全重建：放弃老的索引，将原始的文档和新入的文档归并在一起，完全重新建立一个完整的新索引。
b 再合并：对新入文档内容建立索引结构（链式），与已有的索引结构（顺序存储），通过归并算法，合并写入一个新的索引文件。
c 本地更新策略：每个倒排列表最后都预留一定冗余磁盘空间，新的索引对应的倒排项直接在已有索引文件中写入相应的位置。当没有冗余位置不足时，需对该倒排列表做迁移。由于可能发生迁移的关键词及其倒排列表比较多，我们需要另一个映射表来表明，一个关键词和其倒排链表磁盘位置的对应关系。这时，原来按照词典序顺序存储的各条倒排列表，可能就被打乱了，因为部分倒排列表被迁移到其它位置了。
阅读(4611) | 评论(0) | 转发(0) |
