ES - 基礎(chǔ)
ES簡(jiǎn)介篇
ES介紹
ElasticSearch是一種分布式全文搜索引擎，基于Lucene(全文搜索框架)開(kāi)發(fā)而來(lái)。
Lucene是公認(rèn)的迄今為止的最好用的搜索引擎庫(kù)，但是他所提供的API對(duì)于我們使用者來(lái)說(shuō)，是非?？鄲赖模ＲㄙM(fèi)大量時(shí)間去熟悉學(xué)習(xí)。ES的出現(xiàn)就很好的解決了這個(gè)問(wèn)題，良好的封裝，易用的API，鏈?zhǔn)綍?shū)寫(xiě)方式，開(kāi)瓶即飲。
Lucene與es的關(guān)系
處理分詞，構(gòu)建倒排索引，等等，都是這個(gè)叫l(wèi)ucene的做的。那么能不能說(shuō)這個(gè)lucene就是搜索引擎呢？ 還不能。lucene只是一個(gè)提供全文搜索功能類(lèi)庫(kù)的核心工具包，而真正使用它還需要一個(gè)完善的服務(wù)框架搭建起來(lái)的應(yīng)用。 好比lucene是類(lèi)似于發(fā)動(dòng)機(jī)，而搜索引擎軟件（ES,Solr）就是汽車(chē)。 目前市面上流行的搜索引擎軟件，主流的就兩款，elasticsearch和solr,這兩款都是基于lucene的搭建的，可以獨(dú)立部署啟動(dòng)的搜索引擎服務(wù)軟件。由于內(nèi)核相同，所以?xún)烧叱朔?wù)器安裝、部署、管理、集群以外，對(duì)于數(shù)據(jù)的操作，修改、添加、保存、查詢(xún)等等都十分類(lèi)似。就好像都是支持sql語(yǔ)言的兩種數(shù)據(jù)庫(kù)軟件。只要學(xué)會(huì)其中一個(gè)另一個(gè)很容易上手。 從實(shí)際企業(yè)使用情況來(lái)看，elasticSearch的市場(chǎng)份額逐步在取代solr，國(guó)內(nèi)百度、京東、新浪都是基于elasticSearch實(shí)現(xiàn)的搜索功能。國(guó)外就更多了 像維基百科、GitHub、Stack Overflow等等也都是基于ES的。
ES使用場(chǎng)景
Elasticsearch 在速度和可擴(kuò)展性方面都表現(xiàn)出色，而且還能夠索引多種類(lèi)型的內(nèi)容
為用戶(hù)提供按關(guān)鍵字查詢(xún)的全文搜索功能。例如：一個(gè)在線網(wǎng)上商店，您可以在其中允許客戶(hù)搜索您出售的產(chǎn)品。在這種情況下，您可以使用Elasticsearch 存儲(chǔ)整個(gè)產(chǎn)品目錄和庫(kù)存，并為它們提供搜索和自動(dòng)完成建議
實(shí)現(xiàn)企業(yè)海量數(shù)據(jù)的處理分析的解決方案。大數(shù)據(jù)領(lǐng)域的重要一份子，如著名的ELK框架(ElasticSearch,Logstash,Kibana)，收集日志或交易數(shù)據(jù)，并且要分析和挖掘此數(shù)據(jù)以查找趨勢(shì)，統(tǒng)計(jì)信息，摘要或異常。
ES的特點(diǎn)
-
天然分片，天然集群
es 把數(shù)據(jù)分成多個(gè)shard，多個(gè)shard可以組成一份完整的數(shù)據(jù)，這些shard可以分布在集群中的各個(gè)機(jī)器節(jié)點(diǎn)中。隨著數(shù)據(jù)的不斷增加，集群可以增加多個(gè)分片，把多個(gè)分片放到多個(gè)機(jī)子上，已達(dá)到負(fù)載均衡，橫向擴(kuò)展。
在實(shí)際運(yùn)算過(guò)程中，每個(gè)查詢(xún)?nèi)蝿?wù)提交到某一個(gè)節(jié)點(diǎn)，該節(jié)點(diǎn)必須負(fù)責(zé)將數(shù)據(jù)進(jìn)行整理匯聚，再返回給客戶(hù)端，也就是一個(gè)簡(jiǎn)單的節(jié)點(diǎn)上進(jìn)行Map計(jì)算，在一個(gè)固定的節(jié)點(diǎn)上進(jìn)行Reduces得到最終結(jié)果向客戶(hù)端返回。
-
天然索引
ES 所有數(shù)據(jù)都是默認(rèn)進(jìn)行索引的，這點(diǎn)和mysql正好相反，mysql是默認(rèn)不加索引，要加索引必須特別說(shuō)明，ES只有不加索引才需要說(shuō)明。 而ES使用的是倒排索引和Mysql的B+Tree索引不同。
傳統(tǒng)關(guān)系性數(shù)據(jù)庫(kù)
弊端：
對(duì)于傳統(tǒng)的關(guān)系性數(shù)據(jù)庫(kù)對(duì)于關(guān)鍵詞的查詢(xún)，只能逐字逐行的匹配，性能非常差。
匹配方式不合理，比如搜索“小密手機(jī)” ，如果用like進(jìn)行匹配， 根本匹配不到。但是考慮使用者的用戶(hù)體驗(yàn)的話，除了完全匹配的記錄，還應(yīng)該顯示一部分近似匹配的記錄，至少應(yīng)該匹配到“手機(jī)”。
ES的工作原理
[圖片上傳失敗...(image-ebc3db-1658974200412)]
ES寫(xiě)入
客戶(hù)端選擇一個(gè)node發(fā)送請(qǐng)求過(guò)去，這個(gè)node就是coordinating node（協(xié)調(diào)節(jié)點(diǎn)）
coordinating node，對(duì)document進(jìn)行路由（根據(jù)documentID路由），將請(qǐng)求轉(zhuǎn)發(fā)給對(duì)應(yīng)的node（有primary shard）
實(shí)際的node上的primary shard處理請(qǐng)求，然后將數(shù)據(jù)同步到replica node
coordinating node，如果發(fā)現(xiàn)primary node和所有replica node都搞定之后，就返回響應(yīng)結(jié)果給客戶(hù)端
ES讀出
查詢(xún)，GET某一條數(shù)據(jù)，寫(xiě)入了某個(gè)document，這個(gè)document會(huì)自動(dòng)給你分配一個(gè)全局唯一的id，doc id，同時(shí)也是根據(jù)doc id進(jìn)行hash路由到對(duì)應(yīng)的primary shard上面去。也可以手動(dòng)指定doc id，比如用訂單id，用戶(hù)id。
你可以通過(guò)doc id來(lái)查詢(xún)，會(huì)根據(jù)doc id進(jìn)行hash，判斷出來(lái)當(dāng)時(shí)把doc id分配到了哪個(gè)shard上面去，從那個(gè)shard去查詢(xún)
客戶(hù)端發(fā)送請(qǐng)求到任意一個(gè)node，成為coordinate node
coordinate node對(duì)document進(jìn)行路由，將請(qǐng)求轉(zhuǎn)發(fā)到對(duì)應(yīng)的node，此時(shí)會(huì)使用round-robin隨機(jī)輪詢(xún)算法，在primary shard以及其所有replica中隨機(jī)選擇一個(gè)，讓讀請(qǐng)求負(fù)載均衡
接收請(qǐng)求的node返回document給coordinate node
coordinate node返回document給客戶(hù)端
ES搜索
es最強(qiáng)大的是做全文檢索，就是比如你有三條數(shù)據(jù)
1.java真好玩兒啊
2.java好難學(xué)啊
- j2ee特別牛
你根據(jù)java關(guān)鍵詞來(lái)搜索，將包含java的document給搜索出來(lái)。
客戶(hù)端發(fā)送請(qǐng)求到一個(gè)coordinate node(隨意選擇的)
協(xié)調(diào)節(jié)點(diǎn)將搜索請(qǐng)求轉(zhuǎn)發(fā)到所有的shard對(duì)應(yīng)的primary shard或replica shard也可以
query phase：每個(gè)shard將自己的搜索結(jié)果（其實(shí)就是一些doc id），返回給協(xié)調(diào)節(jié)點(diǎn)，由協(xié)調(diào)節(jié)點(diǎn)進(jìn)行數(shù)據(jù)的合并、排序、分頁(yè)等操作，產(chǎn)出最終結(jié)果
fetch phase：接著由協(xié)調(diào)節(jié)點(diǎn)，根據(jù)doc id去各個(gè)節(jié)點(diǎn)上拉取實(shí)際的document數(shù)據(jù)，最終返回給客戶(hù)端。
寫(xiě)入原理
-
elasticsearch寫(xiě)入數(shù)據(jù)時(shí)涉及到的核心概念講解：
segment file: 存儲(chǔ)倒排索引的文件，每個(gè)segment本質(zhì)上就是一個(gè)倒排索引，每秒都會(huì)生成一個(gè)segment文件，當(dāng)文件過(guò)多時(shí)es會(huì)自動(dòng)進(jìn)行segment merge（合并文件），合并時(shí)會(huì)同時(shí)將已經(jīng)標(biāo)注刪除的文檔物理刪除
commit point（重點(diǎn)理解）: 記錄當(dāng)前所有可用的segment，每個(gè)commit point都會(huì)維護(hù)一個(gè).del文件，即每個(gè).del文件都有一個(gè)commit point文件（es刪除數(shù)據(jù)本質(zhì)是不屬于物理刪除），當(dāng)es做刪改操作時(shí)首先會(huì)在.del文件中聲明某個(gè)document已經(jīng)被刪除，文件內(nèi)記錄了在某個(gè)segment內(nèi)某個(gè)文檔已經(jīng)被刪除，當(dāng)查詢(xún)請(qǐng)求過(guò)來(lái)時(shí)在segment中被刪除的文件是能夠查出來(lái)的，但是當(dāng)返回結(jié)果時(shí)會(huì)根據(jù)commit point維護(hù)的那個(gè).del文件把已經(jīng)刪除的文檔過(guò)濾掉
translog日志文件: 為了防止elasticsearch宕機(jī)造成數(shù)據(jù)丟失保證可靠存儲(chǔ)，es會(huì)將每次寫(xiě)入數(shù)據(jù)同時(shí)寫(xiě)到translog日志中(圖中會(huì)有詳解)。
os cache的理解：操作系統(tǒng)里面，磁盤(pán)文件其實(shí)都有一個(gè)東西，叫做os cache，操作系統(tǒng)緩存，就是說(shuō)數(shù)據(jù)寫(xiě)入磁盤(pán)文件之前，會(huì)先進(jìn)入os cache，先進(jìn)入操作系統(tǒng)級(jí)別的一個(gè)內(nèi)存緩存中去
-
寫(xiě)數(shù)據(jù)的過(guò)程
先寫(xiě)入buffer，在buffer里的時(shí)候數(shù)據(jù)是搜索不到的；同時(shí)將數(shù)據(jù)寫(xiě)入translog日志文件
-
如果buffer快滿了，或者到一定時(shí)間，就會(huì)將buffer數(shù)據(jù)refresh到一個(gè)新的segment file中，但是此時(shí)數(shù)據(jù)不是直接進(jìn)入segment file的磁盤(pán)文件的，而是先進(jìn)入os cache的。這個(gè)過(guò)程就是refresh
每隔1秒鐘，es將buffer中的數(shù)據(jù)寫(xiě)入一個(gè)新的segment file，每秒鐘會(huì)產(chǎn)生一個(gè)新的磁盤(pán)文件，segment file，這個(gè)segment file中就存儲(chǔ)最近1秒內(nèi)buffer中寫(xiě)入的數(shù)據(jù)
但是如果buffer里面此時(shí)沒(méi)有數(shù)據(jù)，那當(dāng)然不會(huì)執(zhí)行refresh操作咯，每秒創(chuàng)建一個(gè)空的segment file，如果buffer里面有數(shù)據(jù)，默認(rèn)1秒鐘執(zhí)行一次refresh操作，刷入一個(gè)新的segment file中。
只要buffer中的數(shù)據(jù)被refresh操作，刷入os cache中，就代表這個(gè)數(shù)據(jù)就可以被搜索到了。
為什么叫es是準(zhǔn)實(shí)時(shí)的？NRT，near real-time，準(zhǔn)實(shí)時(shí)。默認(rèn)是每隔1秒refresh一次的，所以es是準(zhǔn)實(shí)時(shí)的，因?yàn)閷?xiě)入的數(shù)據(jù)1秒之后才能被看到。
可以通過(guò)es的restful api或者java api，手動(dòng)執(zhí)行一次refresh操作，就是手動(dòng)將buffer中的數(shù)據(jù)刷入os cache中，讓數(shù)據(jù)立馬就可以被搜索到。
只要數(shù)據(jù)被輸入os cache中，buffer就會(huì)被清空了，因?yàn)椴恍枰Ａ鬮uffer了，數(shù)據(jù)在translog里面已經(jīng)持久化到磁盤(pán)去一份了
只要數(shù)據(jù)進(jìn)入os cache，此時(shí)就可以讓這個(gè)segment file的數(shù)據(jù)對(duì)外提供搜索了。
-
重復(fù)1~3步驟，新的數(shù)據(jù)不斷進(jìn)入buffer和translog，不斷將buffer數(shù)據(jù)寫(xiě)入一個(gè)又一個(gè)新的segment file中去，每次refresh完buffer清空，translog保留。隨著這個(gè)過(guò)程推進(jìn)，translog會(huì)變得越來(lái)越大。當(dāng)translog達(dá)到一定長(zhǎng)度的時(shí)候，就會(huì)觸發(fā)commit操作。
buffer中的數(shù)據(jù)，倒是好，每隔1秒就被刷到os cache中去，然后這個(gè)buffer就被清空了。所以說(shuō)這個(gè)buffer的數(shù)據(jù)始終是可以保持住不會(huì)填滿es進(jìn)程的內(nèi)存的
每次一條數(shù)據(jù)寫(xiě)入buffer，同時(shí)會(huì)寫(xiě)入一條日志到translog日志文件中去，所以這個(gè)translog日志文件是不斷變大的，當(dāng)translog日志文件大到一定程度的時(shí)候，就會(huì)執(zhí)行commit操作。
commit操作發(fā)生第一步，就是將buffer中現(xiàn)有數(shù)據(jù)refresh到os cache中去，清空buffer
將一個(gè)commit point寫(xiě)入磁盤(pán)文件，里面標(biāo)識(shí)著這個(gè)commit point對(duì)應(yīng)的所有segment file
強(qiáng)行將os cache中目前所有的數(shù)據(jù)都fsync到磁盤(pán)文件中去
-
translog日志文件的作用是什么？就是在你執(zhí)行commit操作之前，數(shù)據(jù)要么是停留在buffer中，要么是停留在os cache中，無(wú)論是buffer還是os cache都是內(nèi)存，一旦這臺(tái)機(jī)器死了，內(nèi)存中的數(shù)據(jù)就全丟了。
所以需要將數(shù)據(jù)對(duì)應(yīng)的操作寫(xiě)入一個(gè)專(zhuān)門(mén)的日志文件，translog日志文件中，一旦此時(shí)機(jī)器宕機(jī)，再次重啟的時(shí)候，es會(huì)自動(dòng)讀取translog日志文件中的數(shù)據(jù)，恢復(fù)到內(nèi)存buffer和os cache中去。
commit操作：1、寫(xiě)commit point；2、將os cache數(shù)據(jù)fsync強(qiáng)刷到磁盤(pán)上去；3、清空translog日志文件
translog其實(shí)也是先寫(xiě)入os cache的，默認(rèn)每隔5秒刷一次到磁盤(pán)中去，所以默認(rèn)情況下，可能有5秒的數(shù)據(jù)會(huì)僅僅停留在buffer或者translog文件的os cache中，如果此時(shí)機(jī)器掛了，會(huì)丟失5秒鐘的數(shù)據(jù)。但是這樣性能比較好，最多丟5秒的數(shù)據(jù)。也可以將translog設(shè)置成每次寫(xiě)操作必須是直接fsync到磁盤(pán)，但是性能會(huì)差很多。
刪除
如果是刪除操作，commit的時(shí)候會(huì)生成一個(gè).del文件，里面將某個(gè)doc標(biāo)識(shí)為deleted狀態(tài)，那么搜索的時(shí)候根據(jù).del文件就知道這個(gè)doc被刪除了
如果是更新操作，就是將原來(lái)的doc標(biāo)識(shí)為deleted狀態(tài)，然后新寫(xiě)入一條數(shù)據(jù)
buffer每次refresh一次，就會(huì)產(chǎn)生一個(gè)segment file，所以默認(rèn)情況下是1秒鐘一個(gè)segment file，segment file會(huì)越來(lái)越多，此時(shí)會(huì)定期執(zhí)行merge。
每次merge的時(shí)候，會(huì)將多個(gè)segment file合并成一個(gè)，同時(shí)這里會(huì)將標(biāo)識(shí)為deleted的doc給物理刪除掉，然后將新的segment file寫(xiě)入磁盤(pán)，這里會(huì)寫(xiě)一個(gè)commit point，標(biāo)識(shí)所有新的segment file，然后打開(kāi)segment file供搜索使用，同時(shí)刪除舊的segment file
ES倒排索引
Elasticsearch 索引指相互關(guān)聯(lián)的文檔集合。Elasticsearch 會(huì)以 JSON 文檔的形式存儲(chǔ)數(shù)據(jù)。每個(gè)文檔都會(huì)在一組鍵 ( 字段或?qū)傩缘拿Q(chēng) ) 和它們對(duì)應(yīng)的值 ( 字符串、數(shù)字、布爾值、日期、數(shù)值組、地理位置或其他類(lèi)型的數(shù)據(jù) ) 之間建立聯(lián)系。
Elasticsearch 使用的是一種名為倒排索引的數(shù)據(jù)結(jié)構(gòu)，這一結(jié)構(gòu)的設(shè)計(jì)可以允許十分快速地進(jìn)行全文本搜索。倒排索引會(huì)列出在所有文檔中出現(xiàn)的每個(gè)特有詞匯，并且可以找到包含每個(gè)詞匯的全部文檔。
在索引過(guò)程中，Elasticsearch 會(huì)存儲(chǔ)文檔并構(gòu)建倒排索引，這樣用戶(hù)便可以近實(shí)時(shí)地對(duì)文檔數(shù)據(jù)進(jìn)行搜索。索引過(guò)程是在索引 API 中啟動(dòng)的，通過(guò)此 API 您既可向特定索引中添加 JSON 文檔，也可更改特定索引中的 JSON 文檔。
倒排索引（Inverted Index）也叫反向索引，有反向索引必有正向索引。通俗地來(lái)講，正向索引是通過(guò)key找value，反向索引則是通過(guò)value找key。
[圖片上傳失敗...(image-ff6b17-1658972353472)]
倒排索引的生成過(guò)程
下面通過(guò)一個(gè)例子來(lái)說(shuō)明下倒排索引的生成過(guò)程
假設(shè)目前有以下兩個(gè)文檔內(nèi)容：
<pre class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" lang="xml" cid="n137" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: Monaco, Consolas, "Andale Mono", "DejaVu Sans Mono", monospace; margin-top: 0px; margin-bottom: 20px; font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; white-space: normal; background: rgb(51, 51, 51); position: relative !important; padding: 10px 10px 10px 30px; width: inherit; color: rgb(184, 191, 198); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;">蘇州街維亞大廈
桔子酒店蘇州街店</pre>
其處理步驟如下：
1、正排索引給每個(gè)文檔進(jìn)行編號(hào)，作為其唯一的標(biāo)識(shí)。
| 文檔 id | content |
|---|---|
| 1 | 蘇州街維亞大廈 |
| 2 | 桔子酒店蘇州街店 |
2、生成倒排索引：
首先要對(duì)字段的內(nèi)容進(jìn)行分詞，分詞就是將一段連續(xù)的文本按照語(yǔ)義拆分為多個(gè)單詞，這里兩個(gè)文檔包含的關(guān)鍵詞有：蘇州街、維亞大廈… 然后按照單詞來(lái)作為索引，對(duì)應(yīng)的文檔 id 建立一個(gè)鏈表，就能構(gòu)成上述的倒排索引結(jié)構(gòu)。 Word 文檔 id 蘇州街 1,2 維亞大廈 1 維亞 1 桔子 2 酒店 2 大賽 1 有了倒排索引，能快速、靈活地實(shí)現(xiàn)各類(lèi)搜索需求。整個(gè)搜索過(guò)程中我們不需要做任何文本的模糊匹配。
例如，如果需要在上述兩個(gè)文檔中查詢(xún) 蘇州街桔子 ，可以通過(guò)分詞后 蘇州街 查到 1、2，通過(guò) 桔子 查到 2，然后再進(jìn)行取交取并等操作得到最終結(jié)果。
[圖片上傳失敗...(image-ab50e1-1658972353472)]
倒排索引的結(jié)構(gòu)
根據(jù)倒排索引的概念，我們可以用一個(gè) Map來(lái)簡(jiǎn)單描述這個(gè)結(jié)構(gòu)。這個(gè) Map 的 Key 的即是分詞后的單詞，這里的單詞稱(chēng)為 Term，這一系列的 Term 組成了倒排索引的第一個(gè)部分 —— Term Dictionary (索引表，可簡(jiǎn)稱(chēng)為 Dictionary)。
倒排索引的另一部分為 Postings List（記錄表），也對(duì)應(yīng)上述 Map 結(jié)構(gòu)的 Value 部分集合。
記錄表由所有的 Term 對(duì)應(yīng)的數(shù)據(jù)（Postings） 組成，它不僅僅為文檔 id 信息，可能包含以下信息：
文檔 id（DocId, Document Id），包含單詞的所有文檔唯一 id，用于去正排索引中查詢(xún)?cè)紨?shù)據(jù)。 詞頻（TF，Term Frequency），記錄 Term 在每篇文檔中出現(xiàn)的次數(shù)，用于后續(xù)相關(guān)性算分。 位置（Position），記錄 Term 在每篇文檔中的分詞位置（多個(gè)），用于做詞語(yǔ)搜索（Phrase Query）。 偏移（Offset），記錄 Term 在每篇文檔的開(kāi)始和結(jié)束位置，用于高亮顯示等。
[圖片上傳失敗...(image-edd623-1658972353472)]
Lucene 倒排索引實(shí)現(xiàn)
全文搜索引擎在海量數(shù)據(jù)的情況下是需要存儲(chǔ)大量的文本，所以面臨以下問(wèn)題：
Dictionary 是比較大的（比如我們搜索中的一個(gè)字段可能有上千萬(wàn)個(gè) Term）
Postings 可能會(huì)占據(jù)大量的存儲(chǔ)空間（一個(gè)Term多的有幾百萬(wàn)個(gè)doc）
因此上面說(shuō)的基于 Map 的實(shí)現(xiàn)方式幾乎是不可行的。
在海量數(shù)據(jù)背景下，倒排索引的實(shí)現(xiàn)直接關(guān)系到存儲(chǔ)成本以及搜索性能。
為此，Lucene 引入了多種巧妙的數(shù)據(jù)結(jié)構(gòu)和算法。其倒排索引實(shí)現(xiàn)擁有以下特性：
以較低的存儲(chǔ)成本存儲(chǔ)在磁盤(pán) （索引大小大約為被索引文本的20-30％）
快速讀寫(xiě)
下面將根據(jù)倒排索引的結(jié)構(gòu)，按 Posting List 和 Terms Dictionary 兩部分來(lái)分析 Lucene 中的實(shí)現(xiàn)。
Posting List 實(shí)現(xiàn)
PostingList 包含文檔 id、詞頻、位置等多個(gè)信息，這些數(shù)據(jù)之間本身是相對(duì)獨(dú)立的，因此 Lucene 將 Postings List 被拆成三個(gè)文件存儲(chǔ)：
doc后綴文件：記錄 Postings 的 docId 信息和 Term 的詞頻
pay后綴文件：記錄 Payload 信息和偏移量信息
pos后綴文件：記錄位置信息
基本所有的查詢(xún)都會(huì)用 .doc 文件獲取文檔 id，且一般的查詢(xún)僅需要用到 .doc 文件就足夠了，只有對(duì)于近似查詢(xún)等位置相關(guān)的查詢(xún)則需要用位置相關(guān)數(shù)據(jù)。
三個(gè)文件整體實(shí)現(xiàn)差不太多，這里以.doc 文件為例分析其實(shí)現(xiàn)。
.doc 文件存儲(chǔ)的是每個(gè) Term 對(duì)應(yīng)的文檔 Id 和詞頻。每個(gè) Term 都包含一對(duì) TermFreqs 和 SkipData 結(jié)構(gòu)。
其中 TermFreqs 存放 docId 和詞頻信息，SkipData 為跳表信息，用于實(shí)現(xiàn) TermFreqs 內(nèi)部的快速跳轉(zhuǎn)。
[圖片上傳失敗...(image-9f65f3-1658972353472)]
TermFreqs
TermFreqs 存儲(chǔ)文檔號(hào)和對(duì)應(yīng)的詞頻，它們兩是一一對(duì)應(yīng)的兩個(gè) int 值。Lucene 為了盡可能的壓縮數(shù)據(jù)，采用的是混合存儲(chǔ) ，由 PackedBlock 和 VIntBlocks 兩種結(jié)構(gòu)組成。
PackedBlock
其采用 PackedInts 結(jié)構(gòu)將一個(gè) int[] 壓縮打包成一個(gè)緊湊的 Block。它的壓縮方式是取數(shù)組中最大值所占用的 bit 長(zhǎng)度作為一個(gè)預(yù)算的長(zhǎng)度，然后將數(shù)組每個(gè)元素按這個(gè)長(zhǎng)度進(jìn)行截取，以達(dá)到壓縮的目的。
例如：一個(gè)包含128個(gè)元素的 int 數(shù)組中最大值的是 2，那么預(yù)算長(zhǎng)度為2個(gè) bit, PackedInts 的長(zhǎng)度僅是 2 * 128 / 8 = 32個(gè)字節(jié)，然后就可以通過(guò)4個(gè) long 值存儲(chǔ)。
[圖片上傳失敗...(image-c75215-1658972353472)]
VIntBlock
VIntBlock 是采用 VInt 來(lái)壓縮 int 值，對(duì)于絕大多數(shù)語(yǔ)言，int 型都占4個(gè)字節(jié)，不論這個(gè)數(shù)據(jù)是1、100、1000、還是1000,000。VInt 采用可變長(zhǎng)的字節(jié)來(lái)表示一個(gè)整數(shù)。數(shù)值較大的數(shù)，使用較多的字節(jié)來(lái)表示，數(shù)值較少的數(shù)，使用較少的字節(jié)來(lái)表示。每個(gè)字節(jié)僅使用第1至第7位(共7 bits)存儲(chǔ)數(shù)據(jù)，第8位作為標(biāo)識(shí)，表示是否需要繼續(xù)讀取下一個(gè)字節(jié)。
舉個(gè)例子：
整數(shù)130為 int 類(lèi)型時(shí)需要4個(gè)字節(jié)，轉(zhuǎn)換成 VInt 后僅用2個(gè)字節(jié)，其中第一個(gè)字節(jié)的第8位為1，標(biāo)識(shí)需要繼續(xù)讀取第二個(gè)字節(jié)。
[圖片上傳失敗...(image-13171a-1658972353472)]
根據(jù)上述兩種 Block 的特點(diǎn)，Lucene 會(huì)每處理包含 Term 的128篇文檔，將其對(duì)應(yīng)的 DocId 數(shù)組和 TermFreq 數(shù)組分別處理為 PackedDocDeltaBlock 和 PackedFreqBlock 的 PackedInt 結(jié)構(gòu)，兩者組成一個(gè) PackedBlock，最后不足128的文檔則采用 VIntBlock 的方式來(lái)存儲(chǔ)。
[圖片上傳失敗...(image-b6b69c-1658972353472)]
SkipData
在搜索中存在將每個(gè) Term 對(duì)應(yīng)的 DocId 集合進(jìn)行取交集的操作，即判斷某個(gè) Term 的 DocId 在另一個(gè) Term 的 TermFreqs 中是否存在。TermFreqs 中每個(gè) Block 中的 DocId 是有序的，可以采用順序掃描的方式來(lái)查詢(xún)，但是如果 Term 對(duì)應(yīng)的 doc 特別多時(shí)搜索效率就會(huì)很低，同時(shí)由于 Block 的大小是不固定的，我們無(wú)法使用二分的方式來(lái)進(jìn)行查詢(xún)。因此 Lucene 為了減少掃描和比較的次數(shù)，采用了 SkipData 這個(gè)跳表結(jié)構(gòu)來(lái)實(shí)現(xiàn)快速跳轉(zhuǎn)。 調(diào)表
跳表是在原有的有序鏈表上面增加了多級(jí)索引，通過(guò)索引來(lái)實(shí)現(xiàn)快速查找。
實(shí)質(zhì)就是一種可以進(jìn)行二分查找的有序鏈表。
[圖片上傳失敗...(image-5f8885-1658972353472)]
SkipData結(jié)構(gòu)
在 TermFreqs 中每生成一個(gè) Block 就會(huì)在 SkipData 的第0層生成一個(gè)節(jié)點(diǎn)，然后第0層以上每隔 N 個(gè)節(jié)點(diǎn)生成一個(gè)上層節(jié)點(diǎn)。
每個(gè)節(jié)點(diǎn)通過(guò) Child 屬性關(guān)聯(lián)下層節(jié)點(diǎn)，節(jié)點(diǎn)內(nèi) DocSkip 屬性保存 Block 的最大的 DocId 值，DocBlockFP、PosBlockFP、PayBlockFP 則表示 Block 數(shù)據(jù)對(duì)應(yīng)在 .pay、.pos、.doc 文件的位置。
[圖片上傳失敗...(image-64aefb-1658972353472)]
Posting 最終數(shù)據(jù)
Posting List 采用多個(gè)文件進(jìn)行存儲(chǔ)，最終我們可以得到每個(gè) Term 的如下信息：
SkipOffset：用來(lái)描述當(dāng)前 term 信息在 .doc 文件中跳表信息的起始位置。
DocStartFP：是當(dāng)前 term 信息在 .doc 文件中的文檔 ID 與詞頻信息的起始位置。
PosStartFP：是當(dāng)前 term 信息在 .pos 文件中的起始位置。
PayStartFP：是當(dāng)前 term 信息在 .pay 文件中的起始位置。
Term Dictionary 實(shí)現(xiàn)
Terms Dictionary（索引表）存儲(chǔ)所有的 Term 數(shù)據(jù)，同時(shí)它也是 Term 與 Postings 的關(guān)系紐帶，存儲(chǔ)了每個(gè) Term 和其對(duì)應(yīng)的 Postings 文件位置指針。
[圖片上傳失敗...(image-696922-1658972353472)]
數(shù)據(jù)存儲(chǔ)
Terms Dictionary 通過(guò) .tim 后綴文件存儲(chǔ)，其內(nèi)部采用 NodeBlock 對(duì) Term 進(jìn)行壓縮前綴存儲(chǔ)，處理過(guò)程會(huì)將相同前綴的的 Term 壓縮為一個(gè) NodeBlock，NodeBlock 會(huì)存儲(chǔ)公共前綴，然后將每個(gè) Term 的后綴以及對(duì)應(yīng) Term 的 Posting 關(guān)聯(lián)信息處理為一個(gè) Entry 保存到 Block。
[圖片上傳失敗...(image-f4187d-1658972353472)]
在上圖中可以看到 Block 中還包含了 Block，這里是為了處理包含相同前綴的 Term 集合內(nèi)部部分 Term 又包含了相同前綴。
舉個(gè)例子，在下圖中為公共前綴為 a 的 Term 集合，內(nèi)部部分 Term 的又包含了相同前綴 ab，這時(shí)這部分 Term 就會(huì)處理為一個(gè)嵌套的 Block。 [圖片上傳失敗...(image-44da49-1658972353472)]
數(shù)據(jù)查找
Terms Dictionary 是按 NodeBlock 存儲(chǔ)在.tim 文件上。當(dāng)文檔數(shù)量越來(lái)越多的時(shí)，Dictionary 中的 Term 也會(huì)越來(lái)越多，那查詢(xún)效率必然也會(huì)逐漸變低。
因此需要一個(gè)很好的數(shù)據(jù)結(jié)構(gòu)為 Dictionary 建構(gòu)一個(gè)索引，這就是 Terms Index(.tip文件存儲(chǔ))，Lucene 采用了 FST 這個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)這個(gè)索引。 FST
FST, 全稱(chēng) Finite State Transducer（有限狀態(tài)轉(zhuǎn)換器）。
它具備以下特點(diǎn)：
給定一個(gè) Input 可以得到一個(gè) output，相當(dāng)于 HashMap
共享前綴、后綴節(jié)省空間，F(xiàn)ST 的內(nèi)存消耗要比 HashMap 少很多
詞查找復(fù)雜度為 O(len(str))
構(gòu)建后不可變更
如下圖為 mon/1，thrus/4，tues/2 生成的 FST，可以看到 thrus 和 tues 共享了前綴 t 以及后綴 s。
[圖片上傳失敗...(image-448a13-1658972353472)]
根據(jù) FST 就可以將需要搜索 Term 作為 Input，對(duì)其途徑的邊上的值進(jìn)行累加就可以得到 output，下述為以 input 為 thrus 的讀取邏輯：
初始狀態(tài)0
輸入t， FST 從0 -> 3， output=2
輸入h，F(xiàn)ST 從3 -> 4， output=2+2=4
輸入r， FST 從4 -> 5， output=4+0
輸入u，F(xiàn)ST 從5 -> 7， output=4+0
輸入s， FST 到達(dá)終止節(jié)點(diǎn)，output=4+0=4
那么 Term Dictionary 生成的 FST 對(duì)應(yīng) input 和 output 是什么呢？可能會(huì)誤認(rèn)為 FST 的 input 是 Dictionary 中所有的 Term，這樣通過(guò) FST 就可以找到具體一個(gè) Term 對(duì)應(yīng)的 Posting 數(shù)據(jù)。
實(shí)際上 FST 是通過(guò) Dictionary 的每個(gè) NodeBlock 的前綴構(gòu)成，所以通過(guò) FST 只可以直接找到這個(gè) NodeBlock 在 .tim 文件上具體的 File Pointer, 然后還需要在 NodeBlock 中遍歷 Entry 匹配后綴進(jìn)行查找。
因此它在 Lucene 中充當(dāng)以下功能：
快速試錯(cuò)，即是在 FST 上找不到可以直接跳出不需要遍歷整個(gè) Dictionary，類(lèi)似于 BloomFilter。
快速定位 Block 的位置，通過(guò) FST 是可以直接計(jì)算出 Block 的在文件中位置。
FST 也是一個(gè) Automation(自動(dòng)狀態(tài)機(jī))。這是正則表達(dá)式的一種實(shí)現(xiàn)方式，所以 FST 能提供正則表達(dá)式的能力。通過(guò) FST 能夠極大的提高近似查詢(xún)的性能，包括通配符查詢(xún)、SpanQuery、PrefixQuery 等。
倒排查詢(xún)邏輯
在介紹了索引表和記錄表的結(jié)構(gòu)后，就可以得到 Lucene 倒排索引的查詢(xún)步驟：
通過(guò) Term Index 數(shù)據(jù)（.tip文件）中的 StartFP 獲取指定字段的 FST
通過(guò) FST 找到指定 Term 在 Term Dictionary（.tim 文件）可能存在的 Block
將對(duì)應(yīng) Block 加載內(nèi)存，遍歷 Block 中的 Entry，通過(guò)后綴（Suffix）判斷是否存在指定 Term
存在則通過(guò) Entry 的 TermStat 數(shù)據(jù)中各個(gè)文件的 FP 獲取 Posting 數(shù)據(jù)
如果需要獲取 Term 對(duì)應(yīng)的所有 DocId 則直接遍歷 TermFreqs，如果獲取指定 DocId 數(shù)據(jù)則通過(guò) SkipData 快速跳轉(zhuǎn)
[圖片上傳失敗...(image-8a42e7-1658972353472)]
Lucene 數(shù)值類(lèi)型處理
上述 Terms Dictionary 與 Posting List 的實(shí)現(xiàn)都是處理字符串類(lèi)型的 Term，而對(duì)于數(shù)值類(lèi)型，如果采用上述方式實(shí)現(xiàn)會(huì)存在以下問(wèn)題：
數(shù)值潛在的 Term 可能會(huì)非常多，比如是浮點(diǎn)數(shù)，導(dǎo)致查詢(xún)效率低 無(wú)法處理多維數(shù)據(jù)，比如經(jīng)緯度 所以 Lucene 為了支持高效的數(shù)值類(lèi)或者多維度查詢(xún)，引入了 BKDTree。 KDTree
BKDTree 是基于 KDTree，KDTree 實(shí)現(xiàn)起來(lái)很像是一個(gè)二叉查找樹(shù)。主要的區(qū)別是，KDTree 在不同的層使用的是不同的維度值。
下面是一個(gè)2維樹(shù)的樣例 ，其第一層以 x 為切分維度，將 x>30的節(jié)點(diǎn)傳遞給右子樹(shù)，x<30的傳遞給左子樹(shù)，第二層再按 y 維度切分，不斷迭代到所有數(shù)據(jù)都被建立到 KD Tree 的節(jié)點(diǎn)上為止。
[圖片上傳失敗...(image-786a23-1658972353472)]
BKDTree
BKD 樹(shù)是 KD 樹(shù)和 B+ 樹(shù)的組合，擁有以下特性
內(nèi)部 node 必須是一個(gè)完全二叉樹(shù)
葉子節(jié)點(diǎn)存儲(chǔ)點(diǎn)數(shù)據(jù)，降低層高度，減少磁盤(pán) IO
[圖片上傳失敗...(image-c90928-1658972353472)]
