Learned Index利用Model來學習資料的CDF分布，預測資料的位置，那他們是如何查詢的呢?
Kraska et al. 提出了他們查詢的策略
主要有兩個查詢策略 Model Biased Search、Biased Quaternary Search
為預設查詢策略，唯一與Binary Search不同的點在於，Binary Search取中間值為第一個值，Model Biased Search則是取Model預測出的位置為第一個值，針對 [ pos - min_err, pos + max_err ] 再進行Binary Search。
我們預設三個中間值為 :
pos為預測值，sigma為預設標準差。
事先找出這三個值，在進行傳統的Quaternary Search。
除外，針對RMI最後一層的Models，計算min- /max- error，確保一定能找所有存在的資料，如果不知道min-/max- error 可以參考【Day 7 - 不精準的問題】。
關於此篇Paper的重點、架構都講得差不多了，像是後面關於Indexing Strings、Training、以及使用Learned Index取代Hash Table 、Bloom filter..等等的，在這裡就不多說了，我們只介紹到Learned Index取代Range Index(e.g., B-Tree)
接下來會開始講最終測試結果與實作的部分 ~
iThome鐵人賽
看影片追技術