资源描述：
《Unique索引优化实践》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、Unique索引优化实践胡月军(一浪)Unique索弓I,有时也称PrimaryKey索引，顾名思义就是对于这个索引字段每个doc的值都是唯一的，如各种id字段：productid,customerid,campaignid和bidwordid等。这种类型的索引一般用来进行高效的查询，最典型的应用场景就是进行附表join查询，即对主表中查到的每一个dg,都在附表中查询其对应的附表doc信息。所以，对这种类型的索引进行优化会对整体查询性能有很好的提升，特别是在主表查询的结果很多的情况下。本文主要总结一下对于这种类型索引的优化实践，包括全塑和实时增量的情况。我
2、们知道，在全量建索引时，在内存屮一般用开链的哈希表来存储Token的Hash值及其倒排链的信息。假设有N个不同的tokens,那么这个hash数组的大小一般是取第一个大于N*(5/3)的质数P。结构如下图所示：conflictinghashnodepostinglist图1:全量索引在内存中的开链哈希表结构图当一个段的索引建完以后，这个内存中的Hash表里而的tokens的哈希值及包含其倒排琏和OCC链等元信息的keywordterms一般被转成如下的三种数据结构之一存在文件中：1.ClosedHashTable2.SkipList3.TieredDict
3、ionary这儿种数据结构的目的都是为了在查询时先mmap了这些文件以后，能对于一个给定的querykeyword,快速根据其哈希值找到其对应的keywordterm,进而泄位到相应的倒排链和occ链等信息。不同的数据结构在不同的场景(数据特点)下对于内存空间的使用以及查询性能的影响也是不同的。下面先简要分析一下以上这儿种常用数据结构的特点，然后再谈谈对于Unique类型的索引所釆用的优化数据结构。为了便于分析，假设我们有100万个不同的Tokens,每个Token的Hash值需用8个bytes表示(uint64_t)oTokens对应的keywordte
4、rms100万个，同时在一般情况下,毎个keywordterm的第一个元素就是其对应的token的hash值。在内存中建索引的时候，这个开链hash表数组的大小P収大于N*（5/3）的第一个质数，即3145739cClosedHashTable（闭链哈希表）提到哈希表，不少人想到就是快，时间复杂度为0（“其实未必如此，这个在后面的优化讨论屮再深入。对于闭链hash,其大小一般也是取第一个大于屮（5/3）的质数P来申请空间，所以空间占用一般会比较大。对于以上例子，即N=100万，那么这个Hash数组大小为P,为原始keywordterms大小的3.15倍。闭
5、链Hash表事实上就是环形数组，如下图所示：3145741100001000110002
6、o
7、•••-A1210000100011000210003X31557393145738(3145739-1)图2:闭链Hash表结构图当查询一个token倒排链等信息的时候，首先计算其hash值，比如H,然后用H模P得到一个值作为下标，然后看这个闭链hash数组在这个下标下的元素是否是空值，如果为空（对于上图来说，就是元素的hash值为0）,则直接返回表示没有查到；若不为空，则看看这个元素的hash值是否和查询值相等，若相等则找到返回，若不等则继续跟这个元素的后而元
8、素依次进行比较，最后要么找到，要么碰到一个空元素说明没有查找到。SkipList（跳表）跳表，顾名思义，是能在查找的时候能快速跳过很多元素，然后在一个相对小的范围内搜索给定的一个querykeyword的hash值对应的keywordterm信息=跳表的实现原理是：1.首先确定用一个小的数组，就叫做跳表数组吧，来存储跳表信息，这个数组的size-般取为keywordterms个数N的1/64（假设此值为M）,或者稍微大点，数组屮每个元素的大小为4个字节（uint32_t）o2.然后，将keywordterms按token的hash值从小到大排好序存储在一个
9、数组中，假设这个数组叫K,同时根据最大和最小的两个token的hash值将所有的hash值值域均分成M个区间。3.让跳表数组的笫i个元素存储hash值的第i个区I'可里面的最小的一个hash值对应的keywordterm在数组K中的下标值（哈，这句话有点绕），若hash值第i个区间里面没有值，则存一个无效的下标值所以一个跳表的结构如下图所示:keywordtermsarray((i-l)eStep4eStep)((hl)0Step,(k2)eStep)1indicatesthereisnotokenwhosehashvalueIslocatedin『Ste
10、p,(i♦l)•Step^whereStep■(Hmax-Hmln
