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

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

左側(cè)為數(shù)據(jù)記錄的物理地址，右側(cè)為查找樹，需要注意的是，邏輯上相鄰的記錄在磁盤上也并不是一定物理相鄰的。實際的數(shù)據(jù)庫應(yīng)用中我們往往使用 B+ 樹或者 LSM 來替代二叉查找樹或者紅黑樹來構(gòu)建索引系統(tǒng)，并且充分利用 虛擬存儲管理 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 。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

不能跳過索引中的列；

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

因此 B-Tree 的列順序非常重要，上述使用規(guī)則都和列順序有關(guān)。對于實際的應(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é)果進行排序，需要索引的順序和 ORDER BY 子句中的順序一致，并且所有列的升降序一致(ASC/DESC)。如果查詢連接了多個表，只有在 ORDER BY 的列引用的是第一個表才可以(需要按序 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 通常會存在寫操作吞吐量上的瓶頸，其需要大量的磁盤隨機 IO，很顯然，大量的磁盤隨機 IO 會嚴重影響索引建立的速度。對于那些索引數(shù)據(jù)大的情況(例如，兩個列的聯(lián)合索引)，插入速度是對性能影響的重要指標，而讀取相對來說就比較少。譬如在一個無緩存的情況下，B-Tree 首先需要進行一次磁盤讀寫將磁盤頁讀取到內(nèi)存中，然后進行修改，最后再進行一次 IO 寫回到磁盤中。

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

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

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

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