摘要：本文節(jié)選自深入淺出分布式基礎(chǔ)架構(gòu)數(shù)據(jù)庫篇。與在數(shù)據(jù)結(jié)構(gòu)與算法查找樹一節(jié)中我們介紹了的基本概念與實(shí)現(xiàn)，這里我們繼續(xù)來分析下為何相較于紅黑樹等二叉查找樹會(huì)更適合于作為數(shù)據(jù)庫索引的實(shí)

本文節(jié)選自深入淺出分布式基礎(chǔ)架構(gòu)-數(shù)據(jù)庫篇 https://url.wx-coder.cn/kl3ms。

索引（Index）是幫助數(shù)據(jù)庫系統(tǒng)高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)庫索引本質(zhì)上是以增加額外的寫操作與用于維護(hù)索引數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間為代價(jià)的用于提升數(shù)據(jù)庫中數(shù)據(jù)檢索效率的數(shù)據(jù)結(jié)構(gòu)。索引可以幫助我們快速地定位到數(shù)據(jù)而不需要每次搜索的時(shí)候都遍歷數(shù)據(jù)庫中的每一行。典型的索引譬如在內(nèi)存中維護(hù)一個(gè)二叉查找樹，每個(gè)節(jié)點(diǎn)分別包含索引鍵值和一個(gè)指向?qū)?yīng)數(shù)據(jù)記錄物理地址的指針，這樣就可以運(yùn)用二叉查找在 O(log2n)的復(fù)雜度內(nèi)獲取到相應(yīng)數(shù)據(jù)。

左側(cè)為數(shù)據(jù)記錄的物理地址，右側(cè)為查找樹，需要注意的是，邏輯上相鄰的記錄在磁盤上也并不是一定物理相鄰的。實(shí)際的數(shù)據(jù)庫應(yīng)用中我們往往使用 B+ 樹或者 LSM 來替代二叉查找樹或者紅黑樹來構(gòu)建索引系統(tǒng)，并且充分利用 虛擬存儲(chǔ)管理 https://url.wx-coder.cn/PeNqS 一節(jié)中介紹過的局部性原理、磁盤預(yù)讀與頁緩存等概念。

值得一提的是，本節(jié)并未涵蓋搜索引擎中常用的與文本索引相關(guān)的技術(shù)，譬如倒排索引、TF-IDF 等，如果有興趣可以參考本篇搜索引擎 https://url.wx-coder.cn/O07eI 一章。

本部分節(jié)選自深入淺出 Linux 操作系統(tǒng) https://url.wx-coder.cn/Q0AmI 。

計(jì)算機(jī)存儲(chǔ)設(shè)備可被粗略分為內(nèi)存儲(chǔ)器（Main Memory）與外存儲(chǔ)器（External Memory）兩大類，內(nèi)存存取速度快，但容量小，價(jià)格昂貴，而且不能長期保存數(shù)據(jù)，在不通電情況下數(shù)據(jù)會(huì)消失；外存儲(chǔ)器存取速度相對較慢，卻可以吃持久化存儲(chǔ)。如果進(jìn)行更加細(xì)致地劃分，每個(gè)計(jì)算機(jī)系統(tǒng)中的存儲(chǔ)設(shè)備都被組織成了一個(gè)存儲(chǔ)器層次結(jié)構(gòu)，在這個(gè)層次結(jié)構(gòu)中，從上至下，設(shè)備變得訪問速度越來越慢、容量越來越大，并且每字節(jié)的造價(jià)也越來越便宜。

存儲(chǔ)器層次結(jié)構(gòu)的主要思想是一層上的存儲(chǔ)器作為低一層存儲(chǔ)器的高速緩存。因此，寄存器文件就是 L1 的高速緩存，L1 是 L2 的高速緩存，L2 是 L3 的高速緩存，L3 是主存的高速緩存，而主存又是磁盤的高速緩存。在某些具有分布式文件系統(tǒng)的網(wǎng)絡(luò)系統(tǒng)中，本地磁盤就是存儲(chǔ)在其他系統(tǒng)中磁盤上的數(shù)據(jù)的高速緩存。

主存是一個(gè)臨時(shí)存儲(chǔ)設(shè)備，在處理器執(zhí)行程序時(shí)，用來存放程序和程序處理的數(shù)據(jù)。從物理上來說，主存是由一組動(dòng)態(tài)隨機(jī)存取存儲(chǔ)器（DRAM）芯片組成的。從邏輯上來說，存儲(chǔ)器是一個(gè)線性的字節(jié)數(shù)組，每個(gè)字節(jié)都有其唯一的地址（即數(shù)組索引），這些地址是從零開始的。一般來說，組成程序的每條機(jī)器指令都由不同數(shù)量的字節(jié)構(gòu)成。

現(xiàn)代 DRAM 的結(jié)構(gòu)和存取原理比較復(fù)雜，這里抽象出一個(gè)十分簡單的存取模型來說明 DRAM 的工作原理。從抽象角度看，主存是一系列的存儲(chǔ)單元組成的矩陣，每個(gè)存儲(chǔ)單元存儲(chǔ)固定大小的數(shù)據(jù)。每個(gè)存儲(chǔ)單元有唯一的地址，現(xiàn)代主存的編址規(guī)則比較復(fù)雜，這里將其簡化成一個(gè)二維地址：通過一個(gè)行地址和一個(gè)列地址可以唯一定位到一個(gè)存儲(chǔ)單元。

當(dāng)系統(tǒng)需要讀取主存時(shí)，則將地址信號(hào)放到地址總線上傳給主存，主存讀到地址信號(hào)后，解析信號(hào)并定位到指定存儲(chǔ)單元，然后將此存儲(chǔ)單元數(shù)據(jù)放到數(shù)據(jù)總線上，供其它部件讀取。寫主存的過程類似，系統(tǒng)將要寫入單元地址和數(shù)據(jù)分別放在地址總線和數(shù)據(jù)總線上，主存讀取兩個(gè)總線的內(nèi)容，做相應(yīng)的寫操作。這里可以看出，主存存取的時(shí)間僅與存取次數(shù)呈線性關(guān)系，因?yàn)椴淮嬖跈C(jī)械操作，兩次存取的數(shù)據(jù)的“距離”不會(huì)對時(shí)間有任何影響，例如，先取 A0 再取 A1 和先取 A0 再取 D3 的時(shí)間消耗是一樣的。

寄存器文件在層次結(jié)構(gòu)中位于最頂部，也就是第 0 級(jí)或記為 L0。一個(gè)典型的寄存器文件只存儲(chǔ)幾百字節(jié)的信息，而主存里可存放幾十億字節(jié)。然而，處理器從寄存器文件中讀數(shù)據(jù)的速度比從主存中讀取幾乎要快 100 倍。針對這種處理器與主存之間的差異，系統(tǒng)設(shè)計(jì)者采用了更小、更快的存儲(chǔ)設(shè)備，即高速緩存存儲(chǔ)器（簡稱高速緩存），作為暫時(shí)的集結(jié)區(qū)域，用來存放處理器近期可能會(huì)需要的信息。

L1 和 L2 高速緩存是用一種叫做靜態(tài)隨機(jī)訪問存儲(chǔ)器（SRAM）的硬件技術(shù)實(shí)現(xiàn)的。比較新的、處理能力更強(qiáng)大的系統(tǒng)甚至有三級(jí)高速緩存：L1、L2 和 L3。系統(tǒng)可以獲得一個(gè)很大的存儲(chǔ)器，同時(shí)訪問速度也很快，原因是利用了高速緩存的局部性原理，即程序具有訪問局部區(qū)域里的數(shù)據(jù)和代碼的趨勢。通過讓高速緩存里存放可能經(jīng)常訪問的數(shù)據(jù)的方法，大部分的存儲(chǔ)器操作都能在快速的高速緩存中完成。

磁盤是一種直接存取的存儲(chǔ)設(shè)備 (DASD)。它是以存取時(shí)間變化不大為特征的。可以直接存取任何字符組，且容量大、速度較其它外存設(shè)備更快。磁盤是一個(gè)扁平的圓盤(與電唱機(jī)的唱片類似)，盤面上有許多稱為磁道的圓圈，數(shù)據(jù)就記錄在這些磁道上。磁盤可以是單片的，也可以是由若干盤片組成的盤組，每一盤片上有兩個(gè)面。如下圖中所示的 6 片盤組為例，除去最頂端和最底端的外側(cè)面不存儲(chǔ)數(shù)據(jù)之外，一共有 10 個(gè)面可以用來保存信息。

當(dāng)磁盤驅(qū)動(dòng)器執(zhí)行讀 / 寫功能時(shí)。盤片裝在一個(gè)主軸上，并繞主軸高速旋轉(zhuǎn)，當(dāng)磁道在讀 / 寫頭 ( 又叫磁頭 ) 下通過時(shí)，就可以進(jìn)行數(shù)據(jù)的讀 / 寫了。一般磁盤分為固定頭盤 ( 磁頭固定 ) 和活動(dòng)頭盤。固定頭盤的每一個(gè)磁道上都有獨(dú)立的磁頭，它是固定不動(dòng)的，專門負(fù)責(zé)這一磁道上數(shù)據(jù)的讀 / 寫?；顒?dòng)頭盤 ( 如上圖 ) 的磁頭是可移動(dòng)的。每一個(gè)盤面上只有一個(gè)磁頭 ( 磁頭是雙向的，因此正反盤面都能讀寫 )。它可以從該面的一個(gè)磁道移動(dòng)到另一個(gè)磁道。所有磁頭都裝 在同一個(gè)動(dòng)臂上，因此不同盤面上的所有磁頭都是同時(shí)移動(dòng)的 ( 行動(dòng)整齊劃一 )。當(dāng)盤片繞主軸旋轉(zhuǎn)的時(shí)候，磁頭與旋轉(zhuǎn)的盤片形成一個(gè)圓柱體。各個(gè)盤面上半徑相 同的磁道組成了一個(gè)圓柱面，我們稱為柱面。因此，柱面的個(gè)數(shù)也就是盤面上的磁道數(shù)。

磁盤上數(shù)據(jù)必須用一個(gè)三維地址唯一標(biāo)示：柱面號(hào)、盤面號(hào)、塊號(hào) ( 磁道上的盤塊 )。讀 / 寫磁盤上某一指定數(shù)據(jù)需要下面 3 個(gè)步驟: (1) 首先移動(dòng)臂根據(jù)柱面號(hào)使磁頭移動(dòng)到所需要的柱面上，這一過程被稱為定位或查找。 (2) 如上圖 11.3 中所示的 6 盤組示意圖中，所有磁頭都定位到了 10 個(gè)盤面的 10 條磁道上 ( 磁頭都是雙向的 )。這時(shí)根據(jù)盤面號(hào)來確定指定盤面上的磁道。 (3) 盤面確定以后，盤片開始旋轉(zhuǎn)，將指定塊號(hào)的磁道段移動(dòng)至磁頭下。經(jīng)過上面三個(gè)步驟，指定數(shù)據(jù)的存儲(chǔ)位置就被找到。這時(shí)就可以開始讀 / 寫操作了。訪問某一具體信息，由 3 部分時(shí)間組成：

查找時(shí)間 (seek time) Ts: 完成上述步驟 (1) 所需要的時(shí)間。這部分時(shí)間代價(jià)最高，最大可達(dá)到 0.1s 左右。

等待時(shí)間 (latency time) Tl: 完成上述步驟 (3) 所需要的時(shí)間。由于盤片繞主軸旋轉(zhuǎn)速度很快，一般為 7200 轉(zhuǎn) / 分 ( 電腦硬盤的性能指標(biāo)之一 , 家用的普通硬盤的轉(zhuǎn)速一般有 5400rpm( 筆記本 )、7200rpm 幾種 )。因此一般旋轉(zhuǎn)一圈大約 0.0083s。

傳輸時(shí)間 (transmission time) Tt: 數(shù)據(jù)通過系統(tǒng)總線傳送到內(nèi)存的時(shí)間，一般傳輸一個(gè)字節(jié) (byte) 大概 0.02us=2*10^(-8)s

磁盤讀取數(shù)據(jù)是以盤塊(block)為基本單位的。位于同一盤塊中的所有數(shù)據(jù)都能被一次性全部讀取出來。而磁盤 IO 代價(jià)主要花費(fèi)在查找時(shí)間 Ts 上。因此我們應(yīng)該盡量將相關(guān)信息存放在同一盤塊，同一磁道中?；蛘咧辽俜旁谕恢婊蛳噜徶嫔?，以求在讀/寫信息時(shí)盡量減少磁頭來回移動(dòng)的次數(shù)，避免過多的查找時(shí)間Ts。所以，在大規(guī)模數(shù)據(jù)存儲(chǔ)方面，大量數(shù)據(jù)存儲(chǔ)在外存磁盤中，而在外存磁盤中讀取 / 寫入塊 (block) 中某數(shù)據(jù)時(shí)，首先需要定位到磁盤中的某塊，如何有效地查找磁盤中的數(shù)據(jù)，需要一種合理高效的外存數(shù)據(jù)結(jié)構(gòu)。

哈希索引即是基于哈希技術(shù)，如上圖所示，我們將一系列的最終的鍵值通過哈希函數(shù)轉(zhuǎn)化為存儲(chǔ)實(shí)際數(shù)據(jù)桶的地址數(shù)值。值本身存儲(chǔ)的地址就是基于哈希函數(shù)的計(jì)算結(jié)果，而搜索的過程就是利用哈希函數(shù)從元數(shù)據(jù)中推導(dǎo)出桶的地址。

添加新值的流程，首先會(huì)根據(jù)哈希函數(shù)計(jì)算出存儲(chǔ)數(shù)據(jù)的地址，如果該地址已經(jīng)被占用，則添加新桶并重新計(jì)算哈希函數(shù)。

更新值的流程則是先搜索到目標(biāo)值的地址，然后對該內(nèi)存地址應(yīng)用所需的操作。

哈希索引會(huì)在進(jìn)行相等性測試（等或者不等）時(shí)候具有非常高的性能，但是在進(jìn)行比較查詢、Order By 等更為復(fù)雜的場景下就無能為力。

在數(shù)據(jù)結(jié)構(gòu)與算法/查找樹 https://url.wx-coder.cn/9PnzG 一節(jié)中我們介紹了 B-Tree 的基本概念與實(shí)現(xiàn)，這里我們繼續(xù)來分析下為何 B-Tree 相較于紅黑樹等二叉查找樹會(huì)更適合于作為數(shù)據(jù)庫索引的實(shí)現(xiàn)。一般來說，索引本身也很大，不可能全部存儲(chǔ)在內(nèi)存中，因此索引往往以索引文件的形式存儲(chǔ)的磁盤上。這樣的話，索引查找過程中就要產(chǎn)生磁盤 I/O 消耗，相對于內(nèi)存存取，I/O 存取的消耗要高幾個(gè)數(shù)量級(jí)，所以評價(jià)一個(gè)數(shù)據(jù)結(jié)構(gòu)作為索引的優(yōu)劣最重要的指標(biāo)就是在查找過程中磁盤 I/O 操作次數(shù)的漸進(jìn)復(fù)雜度。換句話說，索引的結(jié)構(gòu)組織要盡量減少查找過程中磁盤 I/O 的存取次數(shù)。

根據(jù) B-Tree 的定義，可知檢索一次最多需要訪問 h 個(gè)節(jié)點(diǎn)。數(shù)據(jù)庫系統(tǒng)的設(shè)計(jì)者巧妙利用了磁盤預(yù)讀原理，將一個(gè)節(jié)點(diǎn)的大小設(shè)為等于一個(gè)頁，這樣每個(gè)節(jié)點(diǎn)只需要一次 I/O 就可以完全載入。每次新建節(jié)點(diǎn)時(shí)，直接申請一個(gè)頁的空間，這樣就保證一個(gè)節(jié)點(diǎn)物理上也存儲(chǔ)在一個(gè)頁里，加之計(jì)算機(jī)存儲(chǔ)分配都是按頁對齊的，就實(shí)現(xiàn)了一個(gè)節(jié)點(diǎn)只需一次 I/O。而檢索的時(shí)候，一次檢索最多需要 h-1 次 I/O（根節(jié)點(diǎn)常駐內(nèi)存），其漸進(jìn)復(fù)雜度為 $O(h)=O(log_dN)O(h)=O(log_dN)$，實(shí)際應(yīng)用中，出度 d 是非常大的數(shù)字，通常超過 100，因此 h 非常?。ㄍǔ２怀^ 3）。而紅黑樹這種結(jié)構(gòu)，h 明顯要深的多。由于邏輯上很近的節(jié)點(diǎn)（父子）物理上可能很遠(yuǎn)，無法利用局部性，所以紅黑樹的 I/O 漸進(jìn)復(fù)雜度也為 O(h)，效率明顯比 B-Tree 差很多。

B+Tree 是 的變種，有著比 B-Tree 更高的查詢性能，其相較于 B-Tree 有了如下的變化：

有 m 個(gè)子樹的節(jié)點(diǎn)包含有 m 個(gè)元素（B-Tree 中是 m-1）。

根節(jié)點(diǎn)和分支節(jié)點(diǎn)中不保存數(shù)據(jù)，只用于索引，所有數(shù)據(jù)都保存在葉子節(jié)點(diǎn)中。

所有分支節(jié)點(diǎn)和根節(jié)點(diǎn)都同時(shí)存在于子節(jié)點(diǎn)中，在子節(jié)點(diǎn)元素中是最大或者最小的元素。

葉子節(jié)點(diǎn)會(huì)包含所有的關(guān)鍵字，以及指向數(shù)據(jù)記錄的指針，并且葉子節(jié)點(diǎn)本身是根據(jù)關(guān)鍵字的大小從小到大順序鏈接。

一般在數(shù)據(jù)庫系統(tǒng)或文件系統(tǒng)中使用的 B+Tree 結(jié)構(gòu)都在經(jīng)典 B+Tree 的基礎(chǔ)上進(jìn)行了優(yōu)化，增加了順序訪問指針：

如上圖所示，在 B+Tree 的每個(gè)葉子節(jié)點(diǎn)增加一個(gè)指向相鄰葉子節(jié)點(diǎn)的指針，就形成了帶有順序訪問指針的 B+Tree。做這個(gè)優(yōu)化的目的是為了提高區(qū)間訪問的性能，例如下圖中如果要查詢 key 為從 3 到 8 的所有數(shù)據(jù)記錄，當(dāng)找到 3 后，只需順著節(jié)點(diǎn)和指針順序遍歷就可以一次性訪問到所有數(shù)據(jù)節(jié)點(diǎn)，極大提到了區(qū)間查詢效率。

B-Tree 索引可以很好地用于單行、范圍或者前綴掃描，他們只有在查找使用了索引的最左前綴（Leftmost Prefix）的時(shí)候才有用。不過 B-Tree 索引存在一些限制：

如果查找不從索引列的最左邊開始，索引就無法使用；同樣，不能查找字符串結(jié)尾；

不能跳過索引中的列；

不能使用任何在第一個(gè)范圍條件右邊的列作為條件；

因此 B-Tree 的列順序非常重要，上述使用規(guī)則都和列順序有關(guān)。對于實(shí)際的應(yīng)用，一般要根據(jù)具體的需求，創(chuàng)建不同列和不同列順序的索引。假設(shè)有索引 Index(A,B,C):

# 使用索引
A>5 AND A<10 - 最左前綴匹配
A=5 AND B>6 - 最左前綴匹配
A=5 AND B=6 AND C=7 - 全列匹配
A=5 AND B IN (2,3) AND C>5 - 最左前綴匹配，填坑

# 不能使用索引
B>5 - 沒有包含最左前綴
B=6 AND C=7 - 沒有包含最左前綴

# 使用部分索引
A>5 AND B=2 - 使用索引 A 列
A=5 AND B>6 AND C=2 - 使用索引的 A 和 B 列

使用索引對結(jié)果進(jìn)行排序，需要索引的順序和 ORDER BY 子句中的順序一致，并且所有列的升降序一致(ASC/DESC)。如果查詢連接了多個(gè)表，只有在 ORDER BY 的列引用的是第一個(gè)表才可以(需要按序 JOIN)。

# 使用索引排序
ORDER BY A - 最左前綴匹配
WHERE A=5 ORDER BY B,C - 最左前綴匹配
WHERE A=5 ORDER BY B DESC - 最左前綴匹配
WHERE A>5 ORDER BY A,B - 最左前綴匹配

# 不能使用索引排序
WHERE A=5 ORDER BY B DESC,C ASC - 升降序不一致
WHERE A=5 ORDER BY B,D - D 不在索引中
WHERE A=5 ORDER BY C - 沒有包含最左前綴
WHERE A>5 ORDER BY B,C - 第一列是范圍條件，無法使用 BC 排序
WHERE A=5 AND B IN(1, 2) ORDER BY C - B 也是范圍條件，無法用 C 排序

B-Tree 這種數(shù)據(jù)庫索引方式是傳統(tǒng)關(guān)系型數(shù)據(jù)庫中主要的索引構(gòu)建方式，然而 BTree 通常會(huì)存在寫操作吞吐量上的瓶頸，其需要大量的磁盤隨機(jī) IO，很顯然，大量的磁盤隨機(jī) IO 會(huì)嚴(yán)重影響索引建立的速度。對于那些索引數(shù)據(jù)大的情況(例如，兩個(gè)列的聯(lián)合索引)，插入速度是對性能影響的重要指標(biāo)，而讀取相對來說就比較少。譬如在一個(gè)無緩存的情況下，B-Tree 首先需要進(jìn)行一次磁盤讀寫將磁盤頁讀取到內(nèi)存中，然后進(jìn)行修改，最后再進(jìn)行一次 IO 寫回到磁盤中。

LSM Tree 則采取讀寫分離的策略，會(huì)優(yōu)先保證寫操作的性能；其數(shù)據(jù)首先存儲(chǔ)內(nèi)存中，而后需要定期 Flush 到硬盤上。LSM-Tree 通過內(nèi)存插入與磁盤的順序?qū)?，來達(dá)到最優(yōu)的寫性能，因?yàn)檫@會(huì)大大降低磁盤的尋道次數(shù)，一次磁盤 IO 可以寫入多個(gè)索引塊。HBase, Cassandra, RockDB, LevelDB, SQLite 等都是基于 LSM Tree 來構(gòu)建索引的數(shù)據(jù)庫；LSM Tree 的樹節(jié)點(diǎn)可以分為兩種，保存在內(nèi)存中的稱之為 MemTable, 保存在磁盤上的稱之為 SSTable。

LSM-tree 的主要思想是劃分不同等級(jí)的樹。以兩級(jí)樹為例，可以想象一份索引數(shù)據(jù)由兩個(gè)樹組成，一棵樹存在于內(nèi)存，一棵樹存在于磁盤。內(nèi)存中的樹可以可以是 AVL Tree 等結(jié)構(gòu)；因?yàn)閿?shù)據(jù)大小是不同的，沒必要犧牲 CPU 來達(dá)到最小的樹高度。而存在于磁盤的樹是一棵 B-Tree。

數(shù)據(jù)首先會(huì)插入到內(nèi)存中的樹。當(dāng)內(nèi)存中的樹中的數(shù)據(jù)超過一定閾值時(shí)，會(huì)進(jìn)行合并操作。合并操作會(huì)從左至右遍歷內(nèi)存中的樹的葉子節(jié)點(diǎn)與磁盤中的樹的葉子節(jié)點(diǎn)進(jìn)行合并，當(dāng)被合并的數(shù)據(jù)量達(dá)到磁盤的存儲(chǔ)頁的大小時(shí)，會(huì)將合并后的數(shù)據(jù)持久化到磁盤，同時(shí)更新父親節(jié)點(diǎn)對葉子節(jié)點(diǎn)的指針。

之前存在于磁盤的葉子節(jié)點(diǎn)被合并后，舊的數(shù)據(jù)并不會(huì)被刪除，這些數(shù)據(jù)會(huì)拷貝一份和內(nèi)存中的數(shù)據(jù)一起順序?qū)懙酱疟P。這會(huì)操作一些空間的浪費(fèi)，但是，LSM-Tree 提供了一些機(jī)制來回收這些空間。磁盤中的樹的非葉子節(jié)點(diǎn)數(shù)據(jù)也被緩存在內(nèi)存中。數(shù)據(jù)查找會(huì)首先查找內(nèi)存中樹，如果沒有查到結(jié)果，會(huì)轉(zhuǎn)而查找磁盤中的樹。有一個(gè)很顯然的問題是，如果數(shù)據(jù)量過于龐大，磁盤中的樹相應(yīng)地也會(huì)很大，導(dǎo)致的后果是合并的速度會(huì)變慢。一個(gè)解決方法是建立各個(gè)層次的樹，低層次的樹都比 上一層次的樹數(shù)據(jù)集大。假設(shè)內(nèi)存中的樹為 c0, 磁盤中的樹按照層次一次為 c1, c2, c3, ... ck-1, ck。合并的順序是 (c0, c1), (c1, c2)...(ck-1, ck)。