【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一般被转成如下的三种数据结构之一存在文件中：

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

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

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

　　跳表，正规网站优化代理顾名思义，是能在查找的时候能快速跳过很多元素，然后在一个相对小的范围内搜索给定的一个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.

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

　　注意由于按Hash值的值域进行分段跳跃，所以每个哈希值区间里面的元素个数是很可能是分布不均的，正规网站优化代理故每次二分查找的区间大小是不固定的。
以上信息由常州声谷信息科技有限公司整理编辑，了解更多网站优化,网站优化代理,单词优化,网站优化哪家好,单词优化代理,正规网站优化代理信息请访问http://www.shengguxinxi.com