資源描述：
《Unique索引優(yōu)化實踐》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在工程資料-天天文庫。
1、Unique索引優(yōu)化實踐胡月軍(一浪)Unique索弓I,有時也稱PrimaryKey索引，顧名思義就是對于這個索引字段每個doc的值都是唯一的，如各種id字段：productid,customerid,campaignid和bidwordid等。這種類型的索引一般用來進行高效的查詢，最典型的應用場景就是進行附表join查詢，即對主表中查到的每一個dg,都在附表中查詢其對應的附表doc信息。所以，對這種類型的索引進行優(yōu)化會對整體查詢性能有很好的提升，特別是在主表查詢的結(jié)果很多的情況下。本文主要總結(jié)一下對于這種類型索引的優(yōu)化實踐，包括全塑和實時增量的情況。我
2、們知道，在全量建索引時，在內(nèi)存屮一般用開鏈的哈希表來存儲Token的Hash值及其倒排鏈的信息。假設有N個不同的tokens,那么這個hash數(shù)組的大小一般是取第一個大于N*(5/3)的質(zhì)數(shù)P。結(jié)構(gòu)如下圖所示：conflictinghashnodepostinglist圖1:全量索引在內(nèi)存中的開鏈哈希表結(jié)構(gòu)圖當一個段的索引建完以后，這個內(nèi)存中的Hash表里而的tokens的哈希值及包含其倒排璉和OCC鏈等元信息的keywordterms一般被轉(zhuǎn)成如下的三種數(shù)據(jù)結(jié)構(gòu)之一存在文件中：1.ClosedHashTable2.SkipList3.TieredDict
3、ionary這兒種數(shù)據(jù)結(jié)構(gòu)的目的都是為了在查詢時先mmap了這些文件以后，能對于一個給定的querykeyword,快速根據(jù)其哈希值找到其對應的keywordterm,進而泄位到相應的倒排鏈和occ鏈等信息。不同的數(shù)據(jù)結(jié)構(gòu)在不同的場景(數(shù)據(jù)特點)下對于內(nèi)存空間的使用以及查詢性能的影響也是不同的。下面先簡要分析一下以上這兒種常用數(shù)據(jù)結(jié)構(gòu)的特點，然后再談談對于Unique類型的索引所釆用的優(yōu)化數(shù)據(jù)結(jié)構(gòu)。為了便于分析，假設我們有100萬個不同的Tokens,每個Token的Hash值需用8個bytes表示(uint64_t)oTokens對應的keywordte
4、rms100萬個，同時在一般情況下,毎個keywordterm的第一個元素就是其對應的token的hash值。在內(nèi)存中建索引的時候，這個開鏈hash表數(shù)組的大小P収大于N*（5/3）的第一個質(zhì)數(shù)，即3145739cClosedHashTable（閉鏈哈希表）提到哈希表，不少人想到就是快，時間復雜度為0（“其實未必如此，這個在后面的優(yōu)化討論屮再深入。對于閉鏈hash,其大小一般也是取第一個大于屮（5/3）的質(zhì)數(shù)P來申請空間，所以空間占用一般會比較大。對于以上例子，即N=100萬，那么這個Hash數(shù)組大小為P,為原始keywordterms大小的3.15倍。閉
5、鏈Hash表事實上就是環(huán)形數(shù)組，如下圖所示：3145741100001000110002
6、o
7、???-A1210000100011000210003X31557393145738(3145739-1)圖2:閉鏈Hash表結(jié)構(gòu)圖當查詢一個token倒排鏈等信息的時候，首先計算其hash值，比如H,然后用H模P得到一個值作為下標，然后看這個閉鏈hash數(shù)組在這個下標下的元素是否是空值，如果為空（對于上圖來說，就是元素的hash值為0）,則直接返回表示沒有查到；若不為空，則看看這個元素的hash值是否和查詢值相等，若相等則找到返回，若不等則繼續(xù)跟這個元素的后而元
8、素依次進行比較，最后要么找到，要么碰到一個空元素說明沒有查找到。SkipList（跳表）跳表，顧名思義，是能在查找的時候能快速跳過很多元素，然后在一個相對小的范圍內(nèi)搜索給定的一個querykeyword的hash值對應的keywordterm信息=跳表的實現(xiàn)原理是：1.首先確定用一個小的數(shù)組，就叫做跳表數(shù)組吧，來存儲跳表信息，這個數(shù)組的size-般取為keywordterms個數(shù)N的1/64（假設此值為M）,或者稍微大點，數(shù)組屮每個元素的大小為4個字節(jié)（uint32_t）o2.然后，將keywordterms按token的hash值從小到大排好序存儲在一個
9、數(shù)組中，假設這個數(shù)組叫K,同時根據(jù)最大和最小的兩個token的hash值將所有的hash值值域均分成M個區(qū)間。3.讓跳表數(shù)組的笫i個元素存儲hash值的第i個區(qū)I'可里面的最小的一個hash值對應的keywordterm在數(shù)組K中的下標值（哈，這句話有點繞），若hash值第i個區(qū)間里面沒有值，則存一個無效的下標值所以一個跳表的結(jié)構(gòu)如下圖所示:keywordtermsarray((i-l)eStep4eStep)((hl)0Step,(k2)eStep)1indicatesthereisnotokenwhosehashvalueIslocatedin『Ste
10、p,(i?l)?Step^whereStep■(Hmax-Hmln
