[[432663]]

我們介紹過一個用幾行 Shell 代碼實現的簡陋數據庫，它的插入性能很好，但查詢性能很差。

我們都知道，想要提升數據庫的查詢速度，索引必不可少 。那么，索引的底層結構都是怎樣的呢?它們又是如何工作的呢?

實際上，數據庫索引技術因底層數據結構不同，可以分為好幾種：

• 哈希索引( hash index )
• LSM樹( log structured merge tree )
• B樹( b-tree )

其中，哈希索引的結構最為簡單，但也很常用。今天我們就先將它一舉拿下!

哈希索引結構

鍵值對存儲引擎其實跟編程語言中的 字典 ( dictionary )類型很像，而字典底層通常是用 哈希表( hash table )實現的。既然哈希表可以用來索引內存中的數據，應該也可以用來索引磁盤數據吧?

我們實現的玩具數據庫引擎，只是將數據記錄源源不斷地追加到數據文件。因此，只要在內存中維護一個哈希表，記錄每個鍵最新記錄在數據文件中的 偏移量( offset )，即可極大提升查詢速度：

如上圖，數據庫當前保存著 3 個鍵值對記錄：

1,fasionchan.com 
123,google.com 
66,stackoverflow.com 

紫色部分是我們新引入的哈希表，它在內存中維護了每個鍵記錄在文件中的最新偏移量。舉個例子，鍵 123 最新記錄的偏移量是 17 ，意味著 123 這條記錄位于數據文件中的第 17 字節。

當我們查詢鍵 123 時，數據庫先從哈希表中找到數據記錄的偏移量;然后再根據偏移量 seek 到文件指定位置，即可讀出對應的數據，效率因而大大提升。

更新操作

當數據庫處理插入或更新操作時，除了將數據記錄追加到文件，還需要更新哈希表，以保存數據記錄的最新偏移量。這就是索引給寫操作帶來的額外開銷，好在哈希表操作通常都很快，這個開銷是可控的。

如上圖，我們將鍵 1 的值改為 www.fasionchan.com ，數據庫將新鍵值對記錄追加到數據文件，偏移量為 53 。然后，它將哈希表中鍵 1 的偏移量更新為 53 ，指向最新的記錄。

請注意，數據文件只會追加新記錄，不會修改已有記錄。更新操作也是通過追加新記錄來實現的，新記錄覆蓋舊記錄。如上圖，灰色部分為鍵 1 的舊記錄，現已失效。

刪除操作

插入和更新都是往數據文件追加記錄，那刪除又該怎么辦呢?

其實很簡單，我們可以向數據文件追加一條特殊的記錄，用來表示刪除。例如，寫入一條值為 4 個 \0 的記錄，來刪除鍵 123 ：

后續查詢鍵 123 時，將得到特殊的刪除標記 \0\0\0\0 ，便可知道該鍵已被刪除。

內存開銷

因為哈希表保存在內存里面，因此讀寫操作都非常快。但美中不足的是：內存必須能夠容納所有的記錄鍵，否則就會成為瓶頸。而記錄值就沒有這個限制，因為它們只保存在磁盤文件中，就算遠遠超過物理內存也問題不大。

通過哈希表確定記錄偏移量后，只需一次磁盤尋址，即可讀到對應的記錄值。如果文件系統剛好緩存了對應的磁盤數據塊，那么可以直接從緩存讀數據，連磁盤 IO 都省了。因此，就算數據值遠遠超出內存，查詢效率也不會低。

磁盤空間回收

您可能會好奇，所有寫操作都是往數據文件追加數據，永不刪除，最后不會將磁盤寫滿嗎?

隨著時間推移，數據文件中無用部分(灰色)越來越多，有辦法將這部分空間回收利用嗎?

由于數據文件一直在追加寫入，便難以回收其中的垃圾空間。但我們可以將數據文件分成多個片段：如果當前文件達到一定大小，就將它關閉，同時新建一個文件來寫：

如上圖，假設我們設定的閾值大小是 80 字節，如果這時再插入一個新數據 123 ，就要新開一個數據文件來寫。注意到，每個分段文件都會維護自己的哈希表，查詢時應該從最新文件開始，依次檢索。

那么，將文件分段的好處是什么呢?

請注意，除了最新的數據文件還會追加數據外，舊的文件都不會再修改了。這樣一來，我們就可以將舊的文件進行 精簡( compaction )：將其中已經失效或者被刪除的記錄移除，最終只保留每個鍵的最新記錄：

如上圖，原文件中灰色部分為已失效的數據，深灰色部分為已被刪除的數據，這兩部分均可移除。注意到，源文件大小為 82 字節，經過精簡后降為 42 字節，磁盤空間大大降低。

數據文件精簡完畢后，即可替代原文件，而原文件則可安全移除。精簡操作可以用后臺線程來做，這時查詢操作仍可檢索原文件，完全不受影響。一旦精簡完畢，可以將查詢立馬切換到精簡后的文件上。

注意到，文件精簡后數據記錄偏移量肯定會有變動，因此哈希表也需要重建。

隨著數據分段文件越來越多，查詢需要遍歷的文件也會越來越多，效率肯定越來越差。注意到，一個數據文件經過精簡后，尺寸將大大減小。因此，我們可以將多個分段文件 合并( merge )為一個更大的分段文件：

經過若干寫操作，數據文件②也達到尺寸閾值，進而發生切換。切換完畢后，數據文件②就不再修改，可以在后臺對其進行精簡。請注意，對于鍵 66 的刪除記錄必須保留，因為更早的數據文件①中可能還有這個鍵。

于此同時，數據庫可以在后臺將精簡過的兩個數據文件進行合并。在合并過程中，鍵相同的記錄將被進一步精簡，只保留最新的一條。這樣不僅進一步降低了磁盤使用量，也收斂了文件數量，查詢效率因而能夠得到保證。

注意到，鍵 66 在文件①中的老記錄可被移除;其在文件②中的刪除記錄也可移除，因為所有 66 的歷史記錄均已移除。同樣，合并操作可以用后臺線程來做，合并完畢后再整體切換。

索引重建

您可能又有疑問了：哈希索引只保存在內存里面，數據庫一宕機不就全沒了嗎?

的確如此。不過數據庫重新啟動后，可以根據每個分段文件中的數據，重新恢復索引。但恢復索引的過程需要遍歷所有數據，如果數據量太大的話，肯定會比較耗時。

好在數據文件切換后，舊分段文件就不會再追加數據，而對應的哈希表也就固定不變了。如果這時將哈希表持久化到磁盤，故障重啟時就可以直接從磁盤恢復哈希表，而不用再重建。這樣一來，重啟速度將大大加快。

由于最新的分段文件還會不斷寫入數據，它的哈希表仍會不斷更新。由于哈希表更新基本上都是隨機的，難以實時持久化到磁盤。不過沒關系，故障恢復時我們只需重建最新分段的索引，耗時也相對可控。

總結

• 哈希索引擅長鍵值對存儲場景;
• 磁盤擅長順序寫，數據文件總是在末尾追加寫入;
• 更新操作也是在數據文件末尾追加新記錄;
• 刪除操作則是在數據文件末尾追加特殊的標記記錄;
• 當數據文件超過一定大小，就新開文件來寫;
• 只有最新的數據文件會寫數據;
• 歷史文件永遠不會再寫入數據;
• 查詢時需要從最新文件開始，逐一檢索;
• 為加快檢索速度，每個文件都在內存中維護一個哈希索引;
• 哈希索引記錄一個鍵在文件中的最新記錄的偏移量;
• 哈希表保存在內存中，要求內存至少能夠容納所有鍵;
• 由于更新和刪除操作，數據文件會有失效的記錄;
• 對不再寫入數據的歷史文件進行精簡，移除失效記錄，即可回收磁盤空間;
• 對多個精簡后的文件進行合并，既能進一步精簡瘦身，又能降低文件數量，進而保證查詢速度;
• 哈希索引保存在內存中，數據庫故障就會丟失，但可以通過數據文件重建;
• 歷史文件哈希表固定不變，可以將其持久化到硬盤，以加快故障恢復速度;

 

了解哈希索引底層原理后，我們知道它比較適用于鍵值對存儲場景。