Dabble
Kraska 等人提出使用機(jī)器學(xué)習(xí)模型代替?zhèn)鹘y(tǒng)的 B 樹索引，并在真實數(shù)據(jù)集上取得了不錯的效果，但其提出的模型假設(shè)工作負(fù)載是靜態(tài)的、只讀的，對于索引更新問題沒有提出很好的解決辦法。提出了基于中間層的可擴(kuò)展的學(xué)習(xí)索引模型 Dabble，用來解決索引更新引發(fā)的模型重訓(xùn)練問題。首先，Dabble 模型利用 K-Means 聚類算法將數(shù)據(jù)集劃分為 K 個區(qū)域，并訓(xùn)練 K 個神經(jīng)網(wǎng)絡(luò)分別學(xué)習(xí)不同區(qū)域的數(shù)據(jù)分布。在模型訓(xùn)練階段，創(chuàng)新性地把數(shù)據(jù)的訪問熱點(diǎn)信息融入到神經(jīng)網(wǎng)絡(luò)中，從而提高模型對熱點(diǎn)數(shù)據(jù)的預(yù)測精度。在數(shù)據(jù)插入時，借鑒了 LSM 樹延遲更新的思想，提高了數(shù)據(jù) 寫入速度。在索引更新階段，提出一種基于中間層的機(jī)制將模型解耦，從而緩解由于數(shù)據(jù)插入帶來的模型更新問題。
例子
如果我們想要建立一個數(shù)據(jù)庫存儲和查詢 100M 個以連續(xù)整數(shù)作為鍵值的記錄，我們可以將鍵視為偏移量，從而將查詢的時間復(fù)雜度由 B 樹的 O(logN)降低到為 O(1)；同時，索引的內(nèi)存占用也從 O(N)減少到 O(1)。
學(xué)習(xí)型索引的不足
作者認(rèn)為當(dāng)前學(xué)習(xí)索引有兩大不足：
可擴(kuò)展性較差，體現(xiàn)在不能更新數(shù)據(jù)。某個數(shù)據(jù)的插入會引發(fā)大量數(shù)據(jù)的位置變化,這也導(dǎo)致了模型之間的依賴度較高.一旦有某個模型需要重新訓(xùn)練,為了維持模型的準(zhǔn)確性,所有的模型都要重新訓(xùn)練;
模型復(fù)雜，RMI 要遍歷多個模型，增加延遲。
RMI 建立 了一個層次化的模型,下一層的數(shù)據(jù)劃分取決于上一層模型的預(yù)測.第 1 層給出一個 0 到 N 的預(yù)測,假設(shè)第 2 層 有 K 個模型,那么第 1 層預(yù)測在范圍(0,N/K)的記錄將交給第 2 層的模型 1 進(jìn)一步預(yù)測,落在(N/K+1,2×N/K)的記 錄將由第 2 層的模型 2 進(jìn)一步預(yù)測,以此類推.
