The Case for Learned Index Structures
and
ALEX: An Updatable Adaptive Learned Index

可行性

索引本身就是模型占业，B樹(shù)可以看作是一個(gè)映射一個(gè)key到一個(gè)有序數(shù)組中它對(duì)應(yīng)record的位置的模型；哈希索引可以看作一個(gè)映射key到一個(gè)無(wú)序數(shù)組對(duì)應(yīng)位置的模型氓轰；位圖索引可以看作是驗(yàn)證一個(gè)數(shù)據(jù)記錄是否存在的模型。

一個(gè)極端的例子與數(shù)據(jù)分布

一個(gè)極端的例子忠售，一億條數(shù)據(jù)，主鍵是整型從1到1億油挥，如果用B樹(shù)的話(huà)顾患，從根節(jié)點(diǎn)到一個(gè)個(gè)中間節(jié)點(diǎn)自娩，非常麻煩用踩，如果知道數(shù)據(jù)是這樣分布的話(huà)，那肯定不會(huì)選擇建索引忙迁，直接通過(guò)偏移量訪(fǎng)問(wèn)了脐彩。索引，一般索引都是不知道數(shù)據(jù)分布的姊扔，這樣更具有通用性惠奸，但是通常來(lái)說(shuō)，知道數(shù)據(jù)分布對(duì)于索引的優(yōu)化(空間和查詢(xún)效率)是通常都是非常有效的(比如對(duì)于稠密數(shù)據(jù)恰梢，用ART肯定沒(méi)有用普通的span為8的前綴樹(shù)表現(xiàn)好佛南，尤其是索引的構(gòu)建上)梗掰。但是對(duì)于這些傳統(tǒng)索引來(lái)說(shuō)，無(wú)論是了解數(shù)據(jù)分布嗅回，還是讓索引為每種數(shù)據(jù)分布做專(zhuān)門(mén)的優(yōu)化都過(guò)于復(fù)雜了及穗。

于是有了用機(jī)器學(xué)習(xí)來(lái)學(xué)習(xí)出一個(gè)能夠反映數(shù)據(jù)分布，并能自動(dòng)生成出特定的索引結(jié)構(gòu)的想法妈拌。

用機(jī)器學(xué)習(xí)的角度來(lái)看B樹(shù)

B樹(shù)本身就是一個(gè)模型拥坛，給定一個(gè)key蓬蝶，然后預(yù)測(cè)它在有序的集合中的位置(如果你管這個(gè)叫預(yù)測(cè)的話(huà))尘分。因?yàn)樾噬系脑颍饕话愣疾粫?huì)給到這個(gè)key具體的位置丸氛，而是會(huì)查找葉子節(jié)點(diǎn)培愁，然后再去二分查找或者掃描來(lái)找到具體的位置。在B樹(shù)中灭将，一個(gè)節(jié)點(diǎn)的大小就是一頁(yè)咧最。

從機(jī)器學(xué)習(xí)的角度來(lái)看脊岳，B樹(shù)就是一個(gè)回歸樹(shù)，把key和它對(duì)應(yīng)的位置在最小誤差和最大誤差內(nèi)進(jìn)行映射私股，最小誤差是0，最大誤差是pagesize恩掷，并且保證如果key存在的話(huà)倡鲸，在最大誤差范圍內(nèi)必須能夠找到。既然B樹(shù)本身就是一個(gè)回歸樹(shù)黄娘，那么能不能考慮用其他機(jī)器學(xué)習(xí)模型來(lái)取代回歸樹(shù)峭状。

用什么ML模型

前面提到了B樹(shù)需要保證要要查詢(xún)的key必須在一個(gè)區(qū)間內(nèi)，第一感覺(jué)用機(jī)器學(xué)習(xí)模型不簡(jiǎn)單逼争，但事實(shí)并非如此优床。因?yàn)檫@個(gè)保證是給已經(jīng)存儲(chǔ)的key，而不是任意key誓焦，對(duì)于新來(lái)的key胆敞，B樹(shù)需要重新平衡，對(duì)于學(xué)習(xí)型索引需要重新訓(xùn)練杂伟。再有就是這個(gè)錯(cuò)誤邊界并不是一定要有的移层，因?yàn)閿?shù)據(jù)是有序的，誤差也很容易糾正通過(guò)在預(yù)測(cè)值附近進(jìn)行l(wèi)ocal search稿壁，比如用指數(shù)查找幽钢。因此，可以用其他回歸模型傅是，比如線(xiàn)性回歸或神經(jīng)網(wǎng)絡(luò)來(lái)取代B樹(shù)匪燕。

用ML模型取代B樹(shù)也有一些問(wèn)題蕾羊，B樹(shù)插入和查找的代價(jià)是有限的，能充分利用cache帽驯；另外B樹(shù)的頁(yè)也不需要是連續(xù)的龟再，這些都是ML模型需要考慮解決的問(wèn)題。好處也是顯而易見(jiàn)的尼变，用ML模型取代B樹(shù)有可能把時(shí)間復(fù)雜度從O(logn)減少到常數(shù)級(jí)利凑。ML尤其是神經(jīng)網(wǎng)絡(luò)，能夠?qū)W習(xí)不同的數(shù)據(jù)分布嫌术。問(wèn)題在于平衡模型的復(fù)雜度和精確度哀澈。

假設(shè)B樹(shù)的一個(gè)節(jié)點(diǎn)能存100條record，可以看作每經(jīng)過(guò)一個(gè)節(jié)點(diǎn)度气，所確定的要查找的key所在的范圍就縮小100倍割按。查一個(gè)key一共要遍歷log₁₀₀N個(gè)節(jié)點(diǎn)。用二分查找遍歷一個(gè)B樹(shù)節(jié)點(diǎn)磷籍，大概需要50個(gè)時(shí)鐘周期适荣，很難并行。這50個(gè)時(shí)鐘周期是假設(shè)都在cache中的院领，一次cache miss又會(huì)額外需要50-100個(gè)時(shí)鐘周期弛矛。每個(gè)周期能執(zhí)行8-16條SIMD指令。所以一個(gè)模型用少于50*8個(gè)操作將范圍縮小100倍時(shí)會(huì)比B樹(shù)快比然≌擅ィ考慮到cache miss，和GPU和TPU性能和性能增長(zhǎng)遠(yuǎn)超CPU谈秫，實(shí)際上可以使用更復(fù)雜的模型扒寄。

范圍索引模型就是CDF模型

一個(gè)模型，它的工作是給定一個(gè)key預(yù)測(cè)它在有序數(shù)組中的位置拟烫，近似于累積分布函數(shù)CDF该编。
預(yù)測(cè)一個(gè)有序數(shù)組中的key的位置近似于CDF，預(yù)測(cè)可以寫(xiě)成
p = F(Key) * N

幾點(diǎn)觀(guān)察:

1. B樹(shù)通過(guò)建立回歸樹(shù)來(lái)學(xué)習(xí)數(shù)據(jù)分布硕淑，如果用線(xiàn)性模型的話(huà)课竣，它是通過(guò)線(xiàn)性函數(shù)的最小平方誤差來(lái)學(xué)習(xí)

2. 估計(jì)數(shù)據(jù)集分布是一個(gè)廣泛的問(wèn)題，已經(jīng)有了很多解決方法

3. 學(xué)習(xí)CDF也可以對(duì)其他索引進(jìn)行優(yōu)化置媳，前面提到的數(shù)據(jù)分布對(duì)索引有優(yōu)化效果

4. 經(jīng)驗(yàn)CDF近似于理論CDF

一個(gè)簡(jiǎn)單的實(shí)驗(yàn)

用200M的服務(wù)器日志用Tensorflow實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的在時(shí)間戳上的二級(jí)索引于樟。用ReLU訓(xùn)練了一個(gè)兩層的全連接的神經(jīng)網(wǎng)絡(luò)，每層32個(gè)神經(jīng)元拇囊。

實(shí)際上效果很差迂曲，主要有以下原因：

1. Tensorflow適合訓(xùn)練大模型，調(diào)用開(kāi)銷(xiāo)很大寥袭，尤其是用python

2. B樹(shù)或者說(shuō)決策樹(shù)路捧，很容易用簡(jiǎn)單的if語(yǔ)句過(guò)擬合关霸，而其他的模型雖然可以更有效的近似CDF的整體形狀，但在單個(gè)數(shù)據(jù)上并不準(zhǔn)確杰扫。也就是它可能比較容易將范圍縮小到比如1000队寇，但在這1000個(gè)數(shù)據(jù)中預(yù)測(cè)就非常不準(zhǔn)確了。過(guò)擬合對(duì)于機(jī)器學(xué)習(xí)都是極力避免的問(wèn)題章姓，但是在這里越是過(guò)擬合佳遣，最后查詢(xún)的精度越高，因?yàn)槲覀儾樵?xún)的本身就是我們存儲(chǔ)的數(shù)據(jù)凡伊。

3. B樹(shù)是cache優(yōu)化和操作優(yōu)化的零渐，保持上層節(jié)點(diǎn)在cache中，需要其他page再取窗声。但是神經(jīng)網(wǎng)絡(luò)需要所有的權(quán)值計(jì)算出一個(gè)預(yù)測(cè)值相恃，可能這些大量的乘法cost比較高。

RMI

前面簡(jiǎn)單的學(xué)習(xí)型索引笨觅，效果并不好，主要在于最后一段的預(yù)測(cè)并不精確耕腾，last-mile见剩。比如從100M將預(yù)測(cè)誤差縮小到100是非常困難的。但是將100M縮小到10K的范圍并不困難扫俺，也就是范圍縮小了10000苍苞，所以可能取代B樹(shù)前兩層，用更簡(jiǎn)單的模型實(shí)現(xiàn)狼纬。同理羹呵，再把10K范圍縮小到100。

下面是兩個(gè)方程(損失函數(shù)的解釋)疗琉，已經(jīng)比較清楚了冈欢。

優(yōu)點(diǎn)： 該模型體系結(jié)構(gòu)具有以下優(yōu)點(diǎn)：（1）將模型規(guī)模和復(fù)雜度與執(zhí)行成本分離開(kāi)來(lái)。（2） 它利用了這樣一個(gè)事實(shí)盈简，即很容易了解數(shù)據(jù)分布的總體形狀凑耻。（3） 它有效地將空間劃分為更小的子范圍，如B-樹(shù)柠贤，以便更容易地以更少的操作實(shí)現(xiàn)所需的“最后一英里”精度香浩。（4） 兩個(gè)階段之間不需要搜索過(guò)程。例如臼勉，Model1.1的輸出直接用于在下一階段選擇模型邻吭。這不僅減少了管理結(jié)構(gòu)的指令數(shù)，還允許將整個(gè)索引表示為T(mén)PU/GPU的稀疏矩陣乘法宴霸。

搜索策略與單調(diào)性

負(fù)載較小時(shí)囱晴，在有序數(shù)組上二分搜索或掃描通常是最快的岸裙。

兩種搜索策略：

• 模型偏向搜索：把模型預(yù)測(cè)值作為二分搜索的中間值

• 偏向四分搜索：四分搜索將原來(lái)的二分搜索用一個(gè)點(diǎn)把數(shù)據(jù)段分成兩份換成用三個(gè)點(diǎn)把數(shù)據(jù)段分成四份，這樣可以在三個(gè)點(diǎn)上開(kāi)始prefetch速缆，在數(shù)據(jù)不在cache中有更好的性能降允。最初的三個(gè)點(diǎn)定為pos -a, pos, pos + a

留下來(lái)一些問(wèn)題，主要就是插入與更新艺糜。越是過(guò)擬合剧董，新插入的數(shù)據(jù)越是不同于之前訓(xùn)練好的模型需要重新訓(xùn)練；還有就是對(duì)于數(shù)據(jù)分布的改變破停，能檢測(cè)出來(lái)翅楼，能保證在比如B樹(shù)的O(logn)的查找和插入代價(jià)嗎？
對(duì)于插入有一個(gè)簡(jiǎn)單的方法真慢，就是用delta index毅臊，把所有插入的放在buffer中，周期性的與模型合并并重新訓(xùn)練黑界。

ALEX

學(xué)習(xí)型索引的核心思想是把索引看作是一個(gè)預(yù)測(cè)位置的模型管嬉。它是靜態(tài)的，只讀的朗鸠。

本文在前面的基礎(chǔ)上提出了一個(gè)新的蚯撩，支持點(diǎn)查詢(xún)，小范圍查詢(xún)烛占，插入更新刪除操作的學(xué)習(xí)型索引ALEX胎挎。

兩方面的修改：1.提出了一個(gè)空間與時(shí)間的平衡，不只是提出了可更新的學(xué)習(xí)型索引忆家，在查找上也更快了犹菇。為了支持可更新，這里在葉子節(jié)點(diǎn)上用了Gapped Array芽卿。2.學(xué)習(xí)型索引只支持靜態(tài)的RMI(SRMI)揭芍，RMI的層數(shù)和每一層的模型數(shù)量在初始化時(shí)就是固定的。SRMI在插入時(shí)表現(xiàn)不好如果數(shù)據(jù)分布與之前的model不同蹬竖。ALEX可以在運(yùn)行時(shí)動(dòng)態(tài)的高效的根據(jù)工作負(fù)載來(lái)更新RMI的結(jié)構(gòu)沼沈。

通過(guò)以上主要是兩點(diǎn)，希望能夠：插入可以與B+樹(shù)相比币厕；查找比B+樹(shù)和learned index更快列另；索引的空間比B+樹(shù)和learned index更小旦装；數(shù)據(jù)存儲(chǔ)空間(葉子節(jié)點(diǎn))可以與動(dòng)態(tài)B+樹(shù)相比页衙。

和learned index的幾點(diǎn)不同：

1. 存數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是葉子節(jié)點(diǎn)，像B+樹(shù)。允許單個(gè)節(jié)點(diǎn)靈活的擴(kuò)展或分裂店乐，在插入的時(shí)候也限制了數(shù)據(jù)移動(dòng)的數(shù)量艰躺。在B+樹(shù)中，每個(gè)節(jié)點(diǎn)就是一個(gè)key和payload的數(shù)組眨八，數(shù)組最后是空出來(lái)的空間腺兴，來(lái)吸收新插入的數(shù)據(jù)。類(lèi)似的廉侧，ALEX用的是類(lèi)似的設(shè)計(jì)页响，但在自由空間的使用上會(huì)更謹(jǐn)慎，它會(huì)把自動(dòng)空間會(huì)放在數(shù)組中元素中間段誊，來(lái)達(dá)到更快的插入闰蚕。
2. 第二個(gè)不同是ALEX用的是指數(shù)查找。learned index使用的是二分查找连舍，在錯(cuò)誤邊界內(nèi)進(jìn)行二分查找没陡。實(shí)驗(yàn)表明指數(shù)查找更快，因?yàn)槿绻Ｐ秃芎盟魃停A(yù)測(cè)距離正確的位置很近盼玄。這也不需要模型存儲(chǔ)錯(cuò)誤邊界了。
3. 基于模型的插入参滴。ALEX會(huì)把數(shù)據(jù)插入到模型預(yù)測(cè)的位置强岸，減少了模型的錯(cuò)誤預(yù)測(cè)。
4. ALEX會(huì)根據(jù)工作負(fù)載動(dòng)態(tài)的調(diào)整RMI的形狀和高度砾赔。
5. ALEX不需要針對(duì)每個(gè)數(shù)據(jù)集和工作負(fù)載進(jìn)行調(diào)整參數(shù)(前面說(shuō)過(guò)，RMI是靜態(tài)的青灼，高度和每一層的模型的數(shù)量都是在初始化是固定的)暴心。ALEX可以自動(dòng)的批量加載和用代價(jià)模型調(diào)整RMI的結(jié)構(gòu)以達(dá)到更高的性能。

節(jié)點(diǎn)的布局

Data node
像B+樹(shù)杂拨，分為中間節(jié)點(diǎn)和數(shù)據(jù)節(jié)點(diǎn)(葉子節(jié)點(diǎn))专普。數(shù)據(jù)節(jié)點(diǎn)內(nèi)存的是一個(gè)線(xiàn)性回歸模型(兩個(gè)double，斜率和截距)和兩個(gè)Gapped Array弹沽，一個(gè)是key檀夹，一個(gè)是payload。每個(gè)gap都會(huì)用離它最近的數(shù)據(jù)來(lái)填策橘。為了快速的跳過(guò)gap炸渡，還維持一個(gè)bitmap記錄哪些是空的，哪些地方存了數(shù)據(jù)丽已。

中間節(jié)點(diǎn)
把RMI中的模型視為中間節(jié)點(diǎn)蚌堵。中間節(jié)點(diǎn)內(nèi)存了一個(gè)現(xiàn)行回歸模型和一個(gè)包含指向孩子節(jié)點(diǎn)的指針數(shù)組。和B+樹(shù)不同的是，定位下一層的孩子節(jié)點(diǎn)是計(jì)算出來(lái)吼畏，而不是比較出來(lái)的督赤。

ALEX的內(nèi)部節(jié)點(diǎn)和Learned index是為了不同的目的。在learned index中泻蚊，需要選模型來(lái)符合數(shù)據(jù)躲舌。一個(gè)完美的內(nèi)部節(jié)點(diǎn)會(huì)把數(shù)據(jù)平均的分給它的孩子，一個(gè)完美的RMI有完美的內(nèi)部節(jié)點(diǎn)性雄，會(huì)產(chǎn)生大小相等的數(shù)據(jù)節(jié)點(diǎn)没卸。 但是RMI的目標(biāo)不是產(chǎn)生大小相等的數(shù)據(jù)節(jié)點(diǎn)，而是盡可能使數(shù)據(jù)節(jié)點(diǎn)內(nèi)的key的分布基本上是線(xiàn)性的毅贮，是的一個(gè)線(xiàn)性模型能夠比較精確的fit數(shù)據(jù)办悟。

因此ALEX內(nèi)部節(jié)點(diǎn)的角色是提供更靈活的方式來(lái)劃分key space。[0,1)這個(gè)key space中……

多個(gè)指針指向同一個(gè)節(jié)點(diǎn)

ALEX算法

查找和范圍查詢(xún)

為了查找一個(gè)key滩褥，需要從RMI的根節(jié)點(diǎn)病蛉，不斷用模型計(jì)算指針數(shù)組中的定位找到孩子節(jié)點(diǎn)，直到數(shù)據(jù)節(jié)點(diǎn)瑰煎。中間節(jié)點(diǎn)是完美精度的铺然，不需要在內(nèi)部節(jié)點(diǎn)中遍歷。用數(shù)據(jù)節(jié)點(diǎn)中的模型預(yù)測(cè)要查找的key的位置酒甸，然后進(jìn)行指數(shù)搜索魄健。用bitmap跳過(guò)中間的gap，必要的話(huà)用存下來(lái)指向下一個(gè)數(shù)據(jù)節(jié)點(diǎn)的指針插勤。

插入

兩種情況
插入不滿(mǎn)的數(shù)據(jù)節(jié)點(diǎn)沽瘦，前面提到了，基于模型的插入农尖。如果模型預(yù)測(cè)的位置不對(duì)析恋，先用指數(shù)查詢(xún)找到對(duì)的位置(因?yàn)橐ＷC有序)，如果是gap盛卡，直接插入助隧；否則向最近的gap移動(dòng)一位。

插入已滿(mǎn)的數(shù)據(jù)節(jié)點(diǎn)滑沧，兩種機(jī)制創(chuàng)建更大的空間并村，擴(kuò)展和分裂。ALEX用一個(gè)簡(jiǎn)單的代價(jià)模型來(lái)選擇這兩種機(jī)制滓技。

節(jié)點(diǎn)滿(mǎn)的標(biāo)準(zhǔn)：ALEX不是等到節(jié)點(diǎn)100%滿(mǎn)的時(shí)候才再去擴(kuò)展哩牍。因?yàn)殡S著gap的減少，插入性能會(huì)越來(lái)越低(gap越少殖属，要移動(dòng)的數(shù)據(jù)可能就越多越遠(yuǎn))姐叁。所以引入了一個(gè)gapped array的最小最大密度的概念。一個(gè)節(jié)點(diǎn)超過(guò)du時(shí)認(rèn)為這個(gè)節(jié)點(diǎn)已經(jīng)滿(mǎn)了。

節(jié)點(diǎn)擴(kuò)展機(jī)制：擴(kuò)展一個(gè)包含n條key的數(shù)據(jù)節(jié)點(diǎn)外潜，分配一個(gè)新的更大的gapped array包含n/dl個(gè)槽原环。然后調(diào)整或者重新訓(xùn)練這個(gè)線(xiàn)性回歸模型，再基于這個(gè)回歸模型進(jìn)行插入处窥。

節(jié)點(diǎn)分裂機(jī)制：把一個(gè)數(shù)據(jù)節(jié)點(diǎn)分成兩個(gè)嘱吗，需要把原節(jié)點(diǎn)的數(shù)據(jù)分給這兩個(gè)新節(jié)點(diǎn)，每個(gè)新節(jié)點(diǎn)負(fù)責(zé)一半滔驾。兩種方式分裂：

1. 像B+樹(shù)一樣旁路分裂谒麦，兩種情況，如果父內(nèi)部節(jié)點(diǎn)未滿(mǎn)哆致，用兩個(gè)指向新節(jié)點(diǎn)的指針取代父節(jié)點(diǎn)中指向這個(gè)分裂節(jié)點(diǎn)的指針绕德，父內(nèi)部節(jié)點(diǎn)有冗余指針指向分裂數(shù)據(jù)節(jié)點(diǎn)時(shí)，直接用一般的冗余指針指向兩個(gè)新內(nèi)存節(jié)點(diǎn)摊阀；否則耻蛇，父節(jié)點(diǎn)size double，給每個(gè)指針再進(jìn)行一個(gè)冗余的拷貝胞此，直到節(jié)點(diǎn)達(dá)到最大值臣咖。如果父節(jié)點(diǎn)達(dá)到最大，分裂這個(gè)父內(nèi)部節(jié)點(diǎn)漱牵，和B+樹(shù)一樣夺蛇，分裂向上傳遞。由于限制了所有的內(nèi)部節(jié)點(diǎn)大小是2的冪酣胀，可以以保持邊界的方式分裂節(jié)點(diǎn)刁赦，不需要重新訓(xùn)練模型。
2. 把數(shù)據(jù)節(jié)點(diǎn)變成一個(gè)內(nèi)部節(jié)點(diǎn)闻镶，包含兩個(gè)孩子截型，指向這兩個(gè)新的數(shù)據(jù)節(jié)點(diǎn)。

代價(jià)模型：為了決定選擇哪種機(jī)制儒溉，用了簡(jiǎn)單的線(xiàn)性代價(jià)模型來(lái)預(yù)測(cè)平均查找時(shí)間和插入時(shí)間基于每個(gè)數(shù)據(jù)節(jié)點(diǎn)的樣本統(tǒng)計(jì)：平均指數(shù)查找迭代次數(shù)和每次插入平均移動(dòng)的次數(shù)。

統(tǒng)計(jì)量在創(chuàng)建數(shù)據(jù)節(jié)點(diǎn)時(shí)并不知道发钝，為了得到新節(jié)點(diǎn)的代價(jià)顿涣，會(huì)假設(shè)這個(gè)節(jié)點(diǎn)內(nèi)的數(shù)據(jù)是均勻訪(fǎng)問(wèn)的，插入是根據(jù)現(xiàn)有的key的分布插入的酝豪。具體就是每個(gè)key錯(cuò)誤距離的平均log2涛碑，現(xiàn)有的key距離最近的gap的平均距離

遍歷到葉子節(jié)點(diǎn)代價(jià)模型預(yù)測(cè)從根節(jié)點(diǎn)到數(shù)據(jù)節(jié)點(diǎn)的時(shí)間，兩個(gè)統(tǒng)計(jì)量孵淘，要遍歷的葉子節(jié)點(diǎn)的深度蒲障，所有內(nèi)部節(jié)點(diǎn)和數(shù)據(jù)節(jié)點(diǎn)元數(shù)據(jù)的大小

刪除，更新和其他操作

刪除不需要移動(dòng)key，如果刪除后小于dl揉阎，需要進(jìn)行節(jié)點(diǎn)的收縮或合并庄撮。也要用內(nèi)部節(jié)點(diǎn)代價(jià)模型來(lái)決定

邊界上的插入

插入到最左邊或最右邊
假設(shè)插入到右邊

批量加載

ALEX支持批量加載，用來(lái)初始化索引大量數(shù)據(jù)或重建索引毙籽。目標(biāo)是找到一個(gè)代價(jià)最小洞斯，操作時(shí)間最少的RMI。任何RMI操作都可以分成遍歷到葉子節(jié)點(diǎn)和在葉子節(jié)點(diǎn)操作兩部分坑赡。所以RMI代價(jià)也結(jié)合了TraverToLeaf和intra-node cost兩部分烙如。

批量加載算法： 從根節(jié)點(diǎn)開(kāi)始，每個(gè)節(jié)點(diǎn)獨(dú)立的決定這個(gè)節(jié)點(diǎn)是中間節(jié)點(diǎn)還是數(shù)據(jù)節(jié)點(diǎn)毅否。如果是中間節(jié)點(diǎn)亚铁，fanout是多少。fanout必須是2的冪螟加，孩子節(jié)點(diǎn)平分當(dāng)前節(jié)點(diǎn)的key space徘溢。因?yàn)橛玫臅r(shí)候線(xiàn)性模型，所以每個(gè)節(jié)點(diǎn)造成的影響對(duì)于全局是加法仰迁。
如果一個(gè)節(jié)點(diǎn)決定是內(nèi)部節(jié)點(diǎn)甸昏，它的孩子節(jié)點(diǎn)遞歸進(jìn)行這個(gè)操作。
The fanout tree