? ? 最近接觸了公司一個內(nèi)部后臺的產(chǎn)品設(shè)計需求焦履，其中有部分?jǐn)?shù)據(jù)存儲在Elastic search數(shù)據(jù)庫中（下文簡稱ES庫）乔外，這種Nosql的數(shù)據(jù)庫，以往只是進行簡單的增刪改查酥泛，沒深入了解過，接觸最多的還是關(guān)系型數(shù)據(jù)庫比如MSSQL Server嫌拣、Mysql之類的柔袁。接觸ES庫給我最大的感覺就是一個字『快』，特別是多條件聯(lián)合查詢异逐，在數(shù)據(jù)量過10億的情況下捶索，可明顯感知搜索速度的差異。本次正好借本文介紹一下ES庫的基本原理应役。
? 介紹
? ? ES庫是一個分布式可擴展的數(shù)據(jù)庫情组，主要用于大并發(fā)的大數(shù)據(jù)量的實時數(shù)據(jù)檢索÷嵯椋快速的檢索是有代價的，代價就是不支持類似事務(wù)管理肆氓，不支持回滾袍祖，刪除數(shù)據(jù)可就真刪除了。任何事情都有代價的谢揪，要想速度快就要減少一切非必要的操作蕉陋。ES的這種特點決定了它不適合做OLTP類型的數(shù)據(jù)存儲捐凭，因為不支持事務(wù)這一條就pass掉了。
? 基本概念
? ? 對于一個數(shù)據(jù)庫產(chǎn)品凳鬓，按照慣例茁肠，首先要了解一下這個數(shù)據(jù)庫的組成，比如表結(jié)構(gòu)缩举、表字段啥的垦梆，ES庫比較特殊，他是Nosql數(shù)據(jù)庫仅孩，是非結(jié)構(gòu)化存儲的托猩，它是面向文檔型的數(shù)據(jù)庫，一條數(shù)據(jù)就是一個文檔辽慕。下圖為關(guān)系型數(shù)據(jù)庫與es庫的結(jié)構(gòu)對比京腥。
可以看到，ES庫在層次上和關(guān)系型數(shù)據(jù)庫類似溅蛉，不過在物理存儲結(jié)構(gòu)上就不同了公浪，ES的數(shù)據(jù)通過Json格式存儲。與ES交互船侧，通過HTTP的Restful API方式因悲，比如我想往ES中插入一條數(shù)據(jù)，可以通過：PUT? /project/contract/129001勺爱，來實現(xiàn)晃琳，PUT后邊的路徑分別表示的是：索引名，類型名琐鲁，文檔ID
{
? ? "ID" :? ? 7892,
? ? "city_name" :? ? ? "beijing",
? ? "project_name" :? ? ? "KMlop",
? ? "create_date": "2019-08-25",
? ? "detail" :? ? "this is fist pj"
}
對于ES的增刪改操作卫旱，本次不去詳細(xì)描述，本文主要是分享ES的快速搜索的原理围段，下面我們開始了解ES快速搜索數(shù)據(jù)的原理顾翼。
索引
讓我們回想一下，對于關(guān)系型數(shù)據(jù)庫奈泪，如何加快速度訪問的呢适贸？第一反應(yīng)就是：上索引。不管上的是聚集索引還是非聚集索引涝桅，總之拜姿，我給需要檢索的列上了索引，搜索速度就上去了冯遂，那么同理蕊肥，ES想要快速訪問數(shù)據(jù)，也要有索引蛤肌，不過ES的索引的原理和關(guān)系型的不同了壁却，原因是上文我們提到批狱，ES是非結(jié)構(gòu)化存儲，數(shù)據(jù)以JSon存儲展东，關(guān)系型數(shù)據(jù)庫的B+tree索引沒辦法用在這種的數(shù)據(jù)結(jié)構(gòu)上赔硫，ES用的索引是倒排索引。
那什么是倒排索引呢盐肃？
倒排索引的思路是不去索引列值而是索引關(guān)鍵字爪膊。比如對于一個存儲網(wǎng)站內(nèi)容的列，如果索引的是這個列的內(nèi)容恼蓬，那么如果檢索一個關(guān)鍵字惊完，就需要索引全掃描，索引量如果很大或者多個關(guān)鍵字聯(lián)合搜索就會很慢处硬，如果索引的是關(guān)鍵字小槐，那么對于這種關(guān)鍵字類型的查詢速度就就會非常快荷辕，因為索引存的是關(guān)鍵字對應(yīng)的記錄ID凿跳。倒排索引，建立索引之前需要對內(nèi)容先進行切詞疮方。
舉個例子控嗜，比如有以下三條記錄：
ID? ? name? ? ? ? ? ? ? age
1? ? ? micah latin? ? ? 23
2? ? ? Jones? ? ? ? ? ? ? 23
3? ? ? pink? ? ? ? ? ? ? ? 56
4? ? ? robotic? ? ? ? ? ? 63
假設(shè)切詞直接按照單個字切分，那么nane列的切分結(jié)果為：
ID? ? ? ? name
1? ? ? micah/ latin
2? ? Jones
3? ? pink?
4? ? robotic
age列切分結(jié)果：
ID? ? ? ? age
1? ? ? ?23
2? ? ? ?23
3? ? ? ?56
4? ? ? ?63
其中的ID是文檔ID骡显，斜杠表示的是切分位置疆栏。? 切分后就可以組織倒排索引了，
對于name列惫谤，倒排索引結(jié)果為：
Term Dictionary? ? Posting List
Jones? ? ? ? ? ? ? ? ? ? [2]
latin? ? ? ? ? ? ? ? ? ? ? ? [1]
micah? ? ? ? ? ? ? ? ? ? ? [1]
pink? ? ? ? ? ? ? ? ? ? ? ? [3]
robotic? ? ? ? ? ? ? ? ? ? [4]
對于age列壁顶，倒排索引結(jié)果：
Term Dictionary? ? Posting List
23? ? ? ? ? ? ? ? ? ? ? ? ? ? [1，2]
56? ? ? ? ? ? ? ? ? ? ? ? ? ? [3]
63? ? ? ? ? ? ? ? ? ? ? ? ? ? [4]?
其中溜歪，Term Dictionary是切分后的結(jié)果若专，可簡單理解為關(guān)鍵字，Posting List為包該含關(guān)鍵字的文檔ID蝴猪。建立倒排索引之后调衰，檢索包含關(guān)鍵字的記錄就非常容易了，比如檢索age=23的記錄自阱，就可以很快得出是記錄ID為1和2的嚎莉。我們從例子上看，Term Dictionary 是有序的动壤，因為如果不排序萝喘，那么檢索索引的時間復(fù)雜度就是O(n)，如果是有序的琼懊，就可以通過二分法查找阁簸，復(fù)雜度就變成LogN了，檢索效率進一步提升哼丈。ES是面相大數(shù)據(jù)量檢索的启妹，如果Term Dictionary 非常大，幾十億醉旦，如果索引放不進內(nèi)存饶米，查找效率又會減下來，有沒有辦法呢车胡？想一下檬输，這時候的數(shù)據(jù)結(jié)構(gòu)是不是就可以通過B+tree索引再索引一次？這就組成了二級索引匈棘，B+tree索引用來索引Term Dictionary 丧慈，而Term Dictionary 索引posting list。
壓縮算法
? 考慮這樣一種情況主卫，索引列是性別逃默，那么假設(shè)性別就兩種，那么每一個性別下索引的記錄ID會非常多簇搅，這時候就需要對索引進行壓縮完域。因為記錄ID是整形的，就可以想到存儲的時候只需要第一個記錄的完整ID瘩将，其余的記錄只需要記錄與前一個記錄的差值就可以吟税，這樣就實現(xiàn)了對記錄ID的壓縮存儲，而用這種方式存儲數(shù)據(jù)姿现，就需要存儲的數(shù)據(jù)結(jié)構(gòu)是變化的肠仪，因為很明顯，存儲數(shù)字100000建钥，和存儲10不能用一個數(shù)據(jù)結(jié)構(gòu)藤韵，這樣會造成空間的浪費。那么怎么實現(xiàn)變長的數(shù)據(jù)存儲呢熊经？把需要存儲的posting list進行分組泽艘，每組用一段bit存儲。每段bit開頭給出這段bit中用幾個bit存儲一個數(shù)字镐依。
壓縮的步驟為：
1匹涮、通過delta編碼算法，把posting list中的整數(shù)進行增量編碼槐壳。編碼的步驟為：
1）用Elisa?Gamma?Code的方式編碼x的長度：Cr?(floor(log(x))?+?1);
2）求出x的二進制表示然低，并且用Cr做前綴
3）去掉x二進制表示中的第一個1
2、將第一步得到的增量編碼進行分塊（一塊128個數(shù)據(jù)，上圖為了解釋原理雳攘，3個數(shù)字一個塊）带兜。
3、對每個分塊統(tǒng)計其中最大的數(shù)需要多少個bit吨灭，把這個數(shù)放到數(shù)據(jù)塊頭部刚照，讀取數(shù)據(jù)時用于判斷多少位表示一個數(shù)據(jù)。
總結(jié)
ES為了極致的查詢速度喧兄，舍棄了一切不必要的操作（事務(wù)管理）无畔。通過倒排全文索引配合使用二級索引，進一步提高檢索效率吠冤，對于索引數(shù)據(jù)進行增量壓縮浑彰，以便索引可以放入內(nèi)存，這是CPU時間換內(nèi)存空間的策略拯辙。根據(jù)壓縮策略算法可知郭变，如果記錄ID是隨機的，那么壓縮效率就會很低薄风，所以記錄的ID最好是連續(xù)的饵较，這樣壓縮效率最好。
