[[432663]]

我們介紹過一個(gè)用幾行 Shell 代碼實(shí)現(xiàn)的簡(jiǎn)陋數(shù)據(jù)庫，它的插入性能很好，但查詢性能很差。

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

實(shí)際上，數(shù)據(jù)庫索引技術(shù)因底層數(shù)據(jù)結(jié)構(gòu)不同，可以分為好幾種：

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

其中，哈希索引的結(jié)構(gòu)最為簡(jiǎn)單，但也很常用。今天我們就先將它一舉拿下!

哈希索引結(jié)構(gòu)

鍵值對(duì)存儲(chǔ)引擎其實(shí)跟編程語言中的 字典 ( dictionary )類型很像，而字典底層通常是用 哈希表( hash table )實(shí)現(xiàn)的。既然哈希表可以用來索引內(nèi)存中的數(shù)據(jù)，應(yīng)該也可以用來索引磁盤數(shù)據(jù)吧?

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

如上圖，數(shù)據(jù)庫當(dāng)前保存著 3 個(gè)鍵值對(duì)記錄：

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

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

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

更新操作

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

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

請(qǐng)注意，數(shù)據(jù)文件只會(huì)追加新記錄，不會(huì)修改已有記錄。更新操作也是通過追加新記錄來實(shí)現(xiàn)的，新記錄覆蓋舊記錄。如上圖，灰色部分為鍵 1 的舊記錄，現(xiàn)已失效。

刪除操作

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

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

后續(xù)查詢鍵 123 時(shí)，將得到特殊的刪除標(biāo)記 \0\0\0\0 ，便可知道該鍵已被刪除。

內(nèi)存開銷

因?yàn)楣１肀４嬖趦?nèi)存里面，因此讀寫操作都非?？臁５乐胁蛔愕氖牵簝?nèi)存必須能夠容納所有的記錄鍵，否則就會(huì)成為瓶頸。而記錄值就沒有這個(gè)限制，因?yàn)樗鼈冎槐４嬖诖疟P文件中，就算遠(yuǎn)遠(yuǎn)超過物理內(nèi)存也問題不大。

通過哈希表確定記錄偏移量后，只需一次磁盤尋址，即可讀到對(duì)應(yīng)的記錄值。如果文件系統(tǒng)剛好緩存了對(duì)應(yīng)的磁盤數(shù)據(jù)塊，那么可以直接從緩存讀數(shù)據(jù)，連磁盤 IO 都省了。因此，就算數(shù)據(jù)值遠(yuǎn)遠(yuǎn)超出內(nèi)存，查詢效率也不會(huì)低。

磁盤空間回收

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

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

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

如上圖，假設(shè)我們?cè)O(shè)定的閾值大小是 80 字節(jié)，如果這時(shí)再插入一個(gè)新數(shù)據(jù) 123 ，就要新開一個(gè)數(shù)據(jù)文件來寫。注意到，每個(gè)分段文件都會(huì)維護(hù)自己的哈希表，查詢時(shí)應(yīng)該從最新文件開始，依次檢索。

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

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

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

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

注意到，文件精簡(jiǎn)后數(shù)據(jù)記錄偏移量肯定會(huì)有變動(dòng)，因此哈希表也需要重建。

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

經(jīng)過若干寫操作，數(shù)據(jù)文件②也達(dá)到尺寸閾值，進(jìn)而發(fā)生切換。切換完畢后，數(shù)據(jù)文件②就不再修改，可以在后臺(tái)對(duì)其進(jìn)行精簡(jiǎn)。請(qǐng)注意，對(duì)于鍵 66 的刪除記錄必須保留，因?yàn)楦绲臄?shù)據(jù)文件①中可能還有這個(gè)鍵。

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

注意到，鍵 66 在文件①中的老記錄可被移除;其在文件②中的刪除記錄也可移除，因?yàn)樗?66 的歷史記錄均已移除。同樣，合并操作可以用后臺(tái)線程來做，合并完畢后再整體切換。

索引重建

您可能又有疑問了：哈希索引只保存在內(nèi)存里面，數(shù)據(jù)庫一宕機(jī)不就全沒了嗎?

的確如此。不過數(shù)據(jù)庫重新啟動(dòng)后，可以根據(jù)每個(gè)分段文件中的數(shù)據(jù)，重新恢復(fù)索引。但恢復(fù)索引的過程需要遍歷所有數(shù)據(jù)，如果數(shù)據(jù)量太大的話，肯定會(huì)比較耗時(shí)。

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

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

總結(jié)

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

了解哈希索引底層原理后，我們知道它比較適用于鍵值對(duì)存儲(chǔ)場(chǎng)景。