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