搜索引擎應該具備哪些要求

• 查詢速度快
  • 優(yōu)秀的索引結構設計
  • 高效率的壓縮算法
  • 快速的編碼和解碼速度
• 結果準確
  • ElasiticSearch 中7.0 版本之后默認使用BM25 評分算法
  • ElasticSearch 中 7.0 版本之前使用 TP-IDF算法

倒排索引原理

• 當我們有如下列表數(shù)據(jù)信息，并且系統(tǒng)數(shù)據(jù)量達到10億，100億級別的時候，我們系統(tǒng)該如何去解決查詢速度的問題。
• 數(shù)據(jù)庫選擇—mysql， sybase，oracle，mongodb，唯一加速查詢的方法是添加索引

索引

• 無論哪一種存儲引擎的索引都是如下幾個特點
  • 幫助快速檢索
  • 以數(shù)據(jù)結構為載體
  • 以文件的形式落地
• 如下圖中mysql的文件形式，其中的idb文件就是使用innodb存儲引擎來實現(xiàn)數(shù)據(jù)存儲生成的文件，其他后綴的文件是其他存儲引擎生成的，因此無論什么引擎，索引方式，數(shù)據(jù)結構最終都是要落文件的

• 傳統(tǒng)數(shù)據(jù)庫的基本結構如下：

• MySql包括Server層和存儲引擎層：Server層包括，連接器，查詢緩存，分析器，優(yōu)化器，執(zhí)行器
• 連接器：負責和客戶端建立連接
• 查詢緩存：MySql獲取到查詢請求后，會先查詢緩存，如果之前已經(jīng)執(zhí)行過一樣的語句結果會以Key-value的形式存儲到內(nèi)存中，key是查詢語句，value是查詢結果。緩存明中的話可以很快完成查詢，但是大多是情況不能明中，不建議用緩存，因為緩存失效非常頻繁，任何對表的更新都會讓緩存晴空，所以對一個進程更改的表而言，查詢緩存基本不可用，除非是一張配置表?？梢酝ㄟ^配置來決定釋放開啟查詢緩存，并且MySql8.0 之間刪除了查詢緩存功能
• 分析器：詞法分析，識別語句中表名，列名，語法分析，判斷Sql是否滿足MySql語法
• 優(yōu)化器：在有多個索引的情況下，決定使用哪個索引，或者多表聯(lián)合查詢的時候，表的連接順序這么執(zhí)行等
• 執(zhí)行器：執(zhí)行器先判斷權限，有權限才會去調(diào)用存儲引擎對應的查詢接口，默認InnoDB

數(shù)據(jù)載體 mongodb & mysql

• 以為mongodb為案例，索引數(shù)據(jù)存儲的結構如下

• Mongodb索引使用的是B樹：B樹是多叉平衡查找樹，包括以下幾個結構特性

  • 左子樹數(shù)據(jù)小于跟數(shù)據(jù)，右子樹數(shù)據(jù)大于根節(jié)點數(shù)據(jù)
  • 左右子樹高度差不大于1
  • 每個節(jié)點可以有N個字節(jié)的，N>2

• B樹的每個節(jié)點都存放 索引 & 數(shù)據(jù)，數(shù)據(jù)遍布整個樹結構，搜索可能在非葉子結點結束，最好情況是O(1)

• B樹存在的問題：

  • 紫色部分存儲數(shù)據(jù)的主鍵信息，藍色存儲的是指針指向下一個節(jié)點，黃色部分是存儲的主鍵對應的數(shù)據(jù)Data。因此Data是在節(jié)點中占比最大的一部分數(shù)據(jù)，他可能有1M或者更大的一個數(shù)據(jù)體
  • 假設我們一個節(jié)點的大小是固定的M，在Mysql中最小的數(shù)據(jù)邏輯單元是數(shù)據(jù)頁，一個數(shù)據(jù)頁是16KB，如果Data越大，M所能容納的Data個數(shù)就越小，如果需要存儲更多的數(shù)據(jù)則需要更多的節(jié)點，B樹為了承載更多的節(jié)點的同時滿足結構特性就需要更多的分叉，因此就導致樹的深度更大，每一個層級都意味著一次IO操作導致IO次數(shù)更多

• 以為Mysql為案例分析：

• Mysql中innoDB 使用的索引結構是B+樹，
• B+ 樹是B樹的變種，區(qū)別在于：
  • 葉子結點保存了完整的索引 & 數(shù)據(jù)，非葉子結點只保存索引值，因此他的查詢時間固定為logn
  • 葉子結點中有指向下一個葉子結點的指針，葉子結點類似一個雙向鏈表
  • 因為葉子結點有完整數(shù)據(jù)，并且有雙鏈表結構，因此我們在范圍查詢的時候能有效提升查詢效率。
• 數(shù)據(jù)都在子節(jié)點上，因此非葉子節(jié)點就能容納更多的索引信息，這樣就增加了同一個節(jié)點的出度，減少了數(shù)據(jù)Data信息，同一個節(jié)點就能容納更多的其他類型數(shù)據(jù)信息，因此能用更少的節(jié)點來承載索引數(shù)據(jù)，節(jié)點的減少導致樹的深度更低，查詢的IO次數(shù)就變少了。

倒排索引數(shù)據(jù)結構

• 對如上兩個索引結構的分析，我們能看到MySql 無法解決大數(shù)據(jù)索引問題：
  • 第一點：索引往往字段很長，如果使用B+trees，樹可能很深，IO很可怕
  • 第二點：索引可能會失效
  • 第三點：查詢準確度差，
• 有如下案例，有1億條數(shù)據(jù)的商品信息，我們需要對其中的product字段進行查詢，而且是文本信息查詢，例如“小米”這個字段查詢，那么有如下查詢語句：

select * from product where brand like "%小米 NFC 手機%"

• 第一點說明：以上查詢語句，我們需要在product上建索引， MySql上使用的B+樹，因為文本的信息量特別的大，導致所需要的節(jié)點就更多N個16KB（MySql索引中如果一個數(shù)據(jù)行的大小超過了頁的大小16KB，MySQL 會將該行的部分數(shù)據(jù)存儲在行溢出頁中。這意味著數(shù)據(jù)行會被分割，一部分存儲在索引頁中，而溢出的部分存儲在單獨的溢出頁中），節(jié)點數(shù)的增加，導致樹深度增大查詢IO次數(shù)增加
  

• 第二點說明：“%小米 NFC 手機%” 查詢中用了左匹配的方式去查詢，會導致索引失效，這樣導致全表掃描。

• 第三點說明：“小米 NFC 手機%” 去掉左匹配，走索引的方式，則會只查詢"小米 NFC 手機"開頭的，這樣就會導致結果不準確

ElascitSearch索引解決方案

• 對product字段進行分詞拆分，得到如下一個詞項 與id的匹配關系如下

Posting List （倒排表）

• 索引系統(tǒng)通過掃描文章中的每一個詞，對其創(chuàng)建索引，指明在文章中出現(xiàn)的次數(shù)和位置，當用戶查詢時，索引系統(tǒng)過就會根據(jù)事先建立的索引進行查找，并將查找的結果反饋給用戶的檢索方式，利用如上表可以快速完成全文檢索
• 在為屬性（product）構建倒排索引后，此時，本類別中包含了所有文檔中所有字段的一個 分詞（term） 文檔id對應關系的字典信息，通過倒排索引我們可以迅速找到符合條件的文檔，例如“手機” 在文檔 1，2，3 中。

Term Dictionary（前綴樹）

• 當我們進行Elasticsearch查詢，為了能快速找到某個term在倒排表中的位置，ElasticSearch 將類型中所有的term進行排序，然后通過二分法查找term，時間復雜度能達到 logN的查找效率，就像通過字典查找一樣，這就是Term Dictionary，整個是二級輔助索引

Term Index（前綴索引）

• 同時參照 B-Tree通過減少磁盤尋道次數(shù)來提高查詢性能，Elasticsearch也是采用同樣的思路，直接通過內(nèi)存查找term，將term Dictionary這個構建的Mapping存放在內(nèi)存中。但是如果term太多，term dictionary也會很大，放內(nèi)存不現(xiàn)實，于是有了Term Index，因此整個ElasticSearch的數(shù)據(jù)結構如下圖

壓縮算法

• 倒排表生成后，可能存在如表中，小米關鍵字匹配到的文檔id有 100W個 int類型的有序數(shù)組，如果直接存儲這個數(shù)據(jù)的那么需要4Byte * 100w =4MB 的存儲空間，因此存儲的時候需要用到一定的壓縮算法來進行數(shù)據(jù)壓縮

FOR （Frame Of Reference）壓縮算法：

• 假設我們獲取到的壓縮表數(shù)組id是[1,2,3,4,5,…100W] 每一個數(shù)據(jù)占用的存儲空間是 4Byte， 總共是100W * 4Byte = 100W * 4 * 8 bit
• 通過計算相鄰數(shù)據(jù)差值 得到數(shù)組2 [1,1,1,1,1,1, ,1]，總共有100W個1， 這樣我們可以將每一個數(shù)據(jù)用一個bit 來存儲，這樣就只需要 100W * 1bit 相比于原來 數(shù)據(jù) 縮小了 32 倍
• 如下圖：

• 當然以上是一個特殊的案例，我們用一個相對正常一點的數(shù)組來重新計算

• 原數(shù)組：[73,300,302,332,343,372] 總共 6*4Byte = 24Byte

• 差值數(shù)組：[73，227，2，30，11，29]。我們得到如下結論。 64 < 73 < 128, 128 < 227 < 256, 1<2<4, 16 < 30<32, 8<11<16, 16 < 29 <32,

• 以上數(shù)據(jù)我們就依然用bit位的存儲方式，我們用以上數(shù)組中最大的數(shù)字所需要的bit位來計算，也就是227 ，用256 來存儲 2 ⁸ , 也就是8個bit位每個數(shù)字，得到如下

• [73，227，2，30，11，29]。需要的存儲。6 * 8bit = 48bit

• 但是我們發(fā)現(xiàn)還是可以有優(yōu)化空間，比如 2 其實只需要一個bit位即可，因此我們將大數(shù)，小數(shù)再次做一次分組 [73, 227] 最大2⁸ es中會做一個記錄，記錄此處數(shù)組占用的是8bit。, [2, 30,11,29] 最大2⁵ 同樣es中做記錄此處占用5bit，進一步縮小存儲空間。

• 計算整個的存儲空間：

  • [73, 227] 部分。 8bit - 給es記錄存儲空間大小是8bit。數(shù)字占用 8bit * 2 總共。 8bit * 3 = 3Byte
  • [2, 30,11,29] 部分。 8bit - 給es記錄存儲空間大小是5bit， 數(shù)字占用 5bit * 4 總共。8 bit + 20bit = 4Byte
  • 因此總共也就7 Byte的空間占用

• 如下圖：

RBM壓縮（Roaring bitmaps）

• 有了FOR算法，而且針對于同一種數(shù)據(jù)結構為什么還需要RBM算法，因為以上數(shù)據(jù)中案例數(shù)組都是比較稠密的數(shù)組，也就是他們的差值都是比較小的值，如果有如下數(shù)組

• [1000W, 2000W, 3000W, 4000W, 5000W] 每個數(shù)都上千萬，差值也是千萬級別，這樣用FOR算法就沒有任何意義了。

• RBM 案例講解，有如下案例[1000, 62101, 131385, 132052, 191173, 196658]

• 第一步，我們將數(shù)字用二進制表示 ，例如。196658 轉二進制是 0000 0000 0000 0011 0000 0000 0011 0010

• 第二步，將二進制分為高16 位： 0000 0000 0000 0011 轉十進制是 2，底16位 0000 0000 0011 0010 轉十進制是50

• 通過以上步驟我們得到196658 的表示方式（2， 50）

• 也可以通過計算方式得到這兩個數(shù)字 196658 / 2¹⁶ 得到的值是2， 余數(shù)是 50 ，這種計算方式得到我們的推測結果,并且得到的所有數(shù)字都小于 2 ¹⁶= 65536

• 我們將以上數(shù)組表示為 [(0,1000), (0,62101), (2,313), (2,980), (2,60101), (2,50)]

• 第三步：用一個container的數(shù)據(jù)結構來存儲以上得到的數(shù)據(jù)表，

short[] 數(shù)組存儲 第一個數(shù)字	Array，bitmap，run 存儲第二個數(shù)字的組合
0	1000. 62101
2	313，980， 60101，50
。。。。	。。。。

• 我們將數(shù)字以第一個數(shù)字為基準做group by 聚合，得到一個表
• RBM的存儲方式有三種 ArrayContainer，BitMapContainer，RunContainer 三種
  • ArrayContainer存儲short 類型的數(shù)組，short類型，最大是2¹⁶ 正好可以存儲下所有數(shù)據(jù)的極限，而第一個位置中的數(shù)字，最大也就是65535，因為我們通過X/65535 X最大也就是2³² 因此，最多也就是。65535個行，同樣一個Array最多也是存儲65536個id，計算總存儲占用
  • short 2Byte = 16bit， 總共有65536個。65536* 2Byte / 1024 = 128KB，因此一個行的數(shù)據(jù)最多存儲128KB
• BitMapContainer存儲位圖，存儲的數(shù)據(jù)必須是不一樣的數(shù)據(jù)，因為避免沖突，bitmap每一位不為0 的位都代表當前位的數(shù)據(jù)存在，比如第10位 1，表示數(shù)組中存在1 ，因此如果有數(shù)組[1,2,3,4,5,6,7], bitMap對應的就是7個bit位
  • 如果65536 個數(shù)字都是不一樣的，那么用一個 65536 個bit位置的bitMap存儲即可，總共 65536 bit / 8 / 1024 = 8KB
  • 缺點是必須每個數(shù)字不一樣
• RunContainer存儲：按照如上思路如果存在如下特殊的數(shù)組[1,2,3,4,5,…100W] ，那么可以表示為（1， 100W）壓縮到極致，比例取決于連續(xù)數(shù)字的多少
• 安以上三種算法，有如下圖表示

Term Dictionary & Term Index

• 構建好倒排表之后，就又能力快速找到某個term對于的文檔id，然后通過id查找磁盤上的segment，新的問題產(chǎn)生了，加入又1億數(shù)據(jù)，那么term可能又上百萬，挨個便利就炸了
• ElasticSearch為了快速找到對應term，講term按數(shù)組排序，排序后二分查找，以logN的查詢時間復雜度完成查詢，這樣就構建了一個類似如下的term Dictionary

[aaa, aba, abb,abc, allen, .... ,sara,sarb,sarc,....selena.....]

• 即使是logN的時間復雜的，在存在磁盤操作的情況 + 大數(shù)據(jù)量情況也是非常慢的，如果講term dictionary加載到內(nèi)存，十萬級別的數(shù)據(jù)量可能就把內(nèi)存沾滿了，因此需要另外一個更曉的數(shù)據(jù)來對term dictionary進行替代到內(nèi)存中進行查詢，他就是 term index
• 構建term index 過程： 便利所有 term dictionary 中的數(shù)據(jù)，按字符拆分，構建成b-tree，例如aaa 構建成 a-a-a，其他分支依然按字符拆分，如下圖

• 以上前綴表中不會包含所有的term信息，它包含的是term的前綴信息，例如 aaa，aab，aac 都存在aa前綴，通過term index可以快速地定位到term dictionary的某個offset，再結合FST(Finite State Transducers)的壓縮技術，可以使term index緩存到內(nèi)存中。從term index查到對應的term dictionary的block位置之后，再去磁盤上找term，大大減少了磁盤隨機讀的次數(shù)。如下圖：

FST 壓縮算法

• 假設我們要將mop, moth, pop, star, stop and top(term index里的term前綴)映射到序號：0，1，2，3，4，5(term dictionary的block位置)。最簡單的做法就是定義個Map<string, integer=“”>，大家找到自己的位置對應入座就好了，但從內(nèi)存占用少的角度看可以用FST來進行壓縮后在存儲到內(nèi)存。如下圖

• O表示一種狀態(tài)
• –>表示狀態(tài)的變化過程，上面的字母/數(shù)字表示狀態(tài)變化和權重
• 將單詞分成單個字母通過??和–>表示出來，0權重不顯示。如果??后面出現(xiàn)分支，就標記權重，最后整條路徑上的權重加起來就是這個單詞對應的序號。
• FST以字節(jié)的方式存儲所有的term，這種壓縮方式可以有效的縮減存儲空間，使得term index足以放進內(nèi)存，但這種方式也會導致查找時需要更多的CPU資源。