技术开发 频道

搜索引擎优化:唯一性索引优化实践

  【IT168 技术】唯一性索引(Unique Index),有时也称Primary Key索引,顾名思义就是对于这个索引字段每个doc的值都是唯一的,如各种id字段:product id,customer id, campaign id和bidword id等。这种类型的索引一般用来进行高效的查询,最典型的应用场景就是进行附表join查询,即对主表中查到的每一个doc,都在附表中查询其对应的附表doc信息。所以,对这种类型的索引进行优化会对整体查询性能有很好的提升,特别是在主表查询的结果很多的情况下。本文主要总结一下对于这种类型索引的优化实践,包括全量和实时增量的情况。

  我们知道,在全量建索引时,在内存中一般用开链的哈希表来存储Token的Hash值及其倒排链的信息。假设有N个不同的tokens,那么这个hash数组的大小一般是取第一个大于N*(5/3)的质数P。结构如下图所示:

唯一性索引优化实践
▲全量索引在内存中的开链哈希表结构图

  当一个段的索引建完以后,这个内存中的Hash表里面的tokens的哈希值及包含其倒排链和occ链等元信息的keyword terms一般被转成如下的三种数据结构之一存在文件中:

  1.Closed Hash Table

  2.Skip List

  3.Tiered Dictionary

  这几种数据结构的目的都是为了在查询时先mmap了这些文件以后,能对于一个给定的query keyword,快速根据其哈希值找到其对应的keyword term,进而定位到相应的倒排链和occ链等信息。不同的数据结构在不同的场景(数据特点)下对于内存空间的使用以及查询性能的影响也是不同的。下面先简要分析一下以上这几种常用数据结构的特点,然后再谈谈对于Unique类型的索引所采用的优化数据结构。

  为了便于分析,假设我们有100万个不同的Tokens,每个Token的Hash值需用8个bytes表示(uint64_t)。Tokens对应的keyword terms 100万个,同时在一般情况下,每个keyword term的第一个元素就是其对应的token的hash值。在内存中建索引的时候,这个开链hash表数组的大小P取大于N*(5/3)的第一个质数,即3145739。

  Closed Hash Table(闭链哈希表)

  提到哈希表,不少人想到就是快,时间复杂度为O(1), 其实未必如此,这个在后面的优化讨论中再深入。对于闭链hash,其大小一般也是取第一个大于N*(5/3)的质数P来申请空间,所以空间占用一般会比较大。对于以上例子,即N=100万,那么这个Hash数组大小为P,为原始keyword terms大小的3.15倍。闭链Hash表事实上就是环形数组,如下图所示:

唯一性索引优化实践
▲ 闭链Hash表结构图

  当查询一个token倒排链等信息的时候,首先计算其hash值,比如H,然后用H模P得到一个值作为下标,然后看这个闭链hash数组在这个下标下的元素是否是空值,如果为空(对于上图来说,就是元素的hash值为0),则直接返回表示没有查到;若不为空,则看看这个元素的hash值是否和查询值相等,若相等则找到返回,若不等则继续跟这个元素的后面元素依次进行比较,最后要么找到,要么碰到一个空元素说明没有查找到。

  Skip List(跳表)

  跳表,顾名思义,是能在查找的时候能快速跳过很多元素,然后在一个相对小的范围内搜索给定的一个query keyword的hash值对应的keyword term信息。跳表的实现原理是:

  1.首先确定用一个小的数组, 就叫做跳表数组吧,来存储跳表信息,这个数组的size一般取为keyword terms个数N的1/64 (假设此值为M),或者稍微大点,数组中每个元素的大小为4个字节(uint32_t)。

  2.然后,将keyword terms按token的hash值从小到大排好序存储在一个数组中,假设这个数组叫K,同时根据最大和最小的两个token的hash值将所有的hash值值域均分成M个区间。

  3.让跳表数组的第i个元素存储hash值的第i个区间里面的最小的一个hash值对应的keyword term在数组K中的下标值(哈,这句话有点绕), 若hash值第i个区间里面没有值,则存一个无效的下标值-1.

  所以一个跳表的结构如下图所示:

唯一性索引优化实践
▲跳表结构图

  在查询的时候,执行如下步骤:

  1.先计算出query keyword的Hash值H,然后用(H-Hmin)/Step得到skip list数组中的下标i。

  2.查看下标i里面的元素值是否为-1,若为-1,则说明没有查到直接返回,若不为-1,就记录此元素值,假设为j;然后继续在skip list数组中查找i下标以后的元素中第一个不为-1的元素值,若找到则记录此元素值为k,如找不到则将k值设为N,即keyword terms数组的最后一个元素下标位置+1。

  3.最后在keyword terms数组K的[j,k]位置中二分查询hash值为H的keyword item。

  注意由于按Hash值的值域进行分段跳跃,所以每个哈希值区间里面的元素个数是很可能是分布不均的,故每次二分查找的区间大小是不固定的。

0
相关文章