【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值的值域进行分段跳跃，所以每个哈希值区间里面的元素个数是很可能是分布不均的，故每次二分查找的区间大小是不固定的。
