BKD Tree也叫 Block KD-tree，根據(jù)FST思路，如果查詢條件非常多，需要對每個條件根據(jù) FST 查出結(jié)果，進(jìn)行求并集操作 。如果是數(shù)值類型，那么潛在的 Term 可能非常多，查詢銷量也會很低，為了支持高效的數(shù)值類或者多維度查詢，引入 BKD Tree 。在一維下就是一棵二叉搜索樹，在二維下是如果要查詢一個區(qū)間，logN的復(fù)雜度就可以訪問到葉子節(jié)點(diǎn)對應(yīng)的倒排鏈 。
- 確定切分維度，這里維度的選取順序是數(shù)據(jù)在這個維度方法最大的維度優(yōu)先 。一個直接的理解就是，數(shù)據(jù)分散越開的維度，我們優(yōu)先切分 。
- 切分點(diǎn)的選這個維度最中間的點(diǎn) 。
- 遞歸進(jìn)行步驟1，2，我們可以設(shè)置一個閾值，點(diǎn)的數(shù)目少于多少后就不再切分，直到所有的點(diǎn)都切分好停止 。
BitSet 過濾二進(jìn)制處理，通過BKD-Tree查找到的docID是無序的，所以要么先轉(zhuǎn)成有序的docID數(shù)組，或者構(gòu)造BitSet，然后再與其他結(jié)果合并 。
IndexSorting
IndexSorting是一種預(yù)排序，在ES6.0之后才有，與查詢時(shí)的Sort不同，IndexSorting是一種預(yù)排序，即數(shù)據(jù)預(yù)先按照某種方式進(jìn)行排序，它是Index的一個設(shè)置，不可更改 。
一個Segment中的每個文檔，都會被分配一個docID，docID從0開始，順序分配 。在沒有IndexSorting時(shí)，docID是按照文檔寫入的順序進(jìn)行分配的，在設(shè)置了IndexSorting之后，docID的順序就與IndexSorting的順序一致 。
舉個例子來說，假如文檔中有一列為Timestamp，我們在IndexSorting中設(shè)置按照Timestamp逆序排序，那么在一個Segment內(nèi)，docID越小，對應(yīng)的文檔的Timestamp越大，即按照Timestamp從大到小的順序分配docID 。
IndexSorting 之所以可以優(yōu)化性能，是因?yàn)榭梢蕴崆爸袛嘁约疤岣邤?shù)據(jù)壓縮率，但是他并不能滿足所有的場景，比如使用非預(yù)排序字段排序，還會損耗寫入時(shí)的性能 。
搜索引擎正是靠優(yōu)秀的理論加極致的優(yōu)化，做到查詢性能上的極致，后續(xù)會再結(jié)合源碼分析壓縮算法如何做到極致的性能優(yōu)化的 。
推薦閱讀
- 網(wǎng)絡(luò)電話的原理是什么
- 網(wǎng)絡(luò)爬蟲的原理
- 網(wǎng)橋的工作原理
- 網(wǎng)絡(luò)傳輸?shù)脑?
- 太陽能熱水器工作原理 太陽能熱水器的基本參數(shù)
- 軟件無線電原理與應(yīng)用 5g網(wǎng)絡(luò)架構(gòu)及關(guān)鍵技術(shù)分析
- 入射面和折射面的定義及其物理原理 入射面和折射面的定義是什么
- 機(jī)械原理關(guān)于斜齒輪重合度的問題
- 機(jī)械千斤頂?shù)脑砑?
- 機(jī)械制冷的原理