資料庫索引結構

概述

本文主要描述基本的數據結構：LSM-Trees和B-tree，其中LSM-Trees構成了leveldb、rocksdb等的基礎，B-tree是大多數關係型資料庫的基礎。我們先來看一個最簡單的資料庫的雛形：

write() {

echo "$1,$2" >>file}

read(){

grep "^$1," file |sed -e "s/^$1,//" | tail -n 1}

這個資料庫的write功能是很簡單但是很強大，因為它只需要append-only。與write類似，好多資料庫內部使用append-only的log，大型資料庫可能需要解決並發控制、磁碟載入和容錯處理。

這個資料庫的read性能很差，每次查詢都需要O(n)的時間。加索引可以解決這個問題。在本文我們會分析幾種常見的索引，基本思想都是保存額外的metadata來輔助查詢。如果你想通過多種方式來查詢，你可能需要做不同的索引。

索引一般來源於資料庫的primary數據，這個不會影響資料庫的內容，但是會帶來額外的開銷，尤其是對write操作，因為每次write都需要更新索引。所以索引是一個讀寫的折中：索引可以增加度的性能，但是會減少寫的性能。這一般交給使用者來決定怎麼加索引。

哈希索引

最簡單的索引結構是key-value結構，類似於大多數語言里的HashMap結構。這種結構將數據的key和offset保存在內存里，真是數據可以存儲在disk中，從而突破內存大小的限制。Bitcask就使用了這一結構，一次讀根據索引只會有一次磁碟查詢。如果數據剛好在緩存里，一次讀根本不需要訪問磁碟。Bitcask適合key總數小但是更新頻繁的情況，否則內存無法承載所有索引。

append-only結構存在超過磁碟大小的風險。一個解決方法是將log拆分成小的segment，當segment大小超過設置時再起一個新的segment來寫。然後，我們可以對這些segment做compaction，旨在去除重複的key，保持每隔key的最新值。如下所示：

segment 1

a：1b：2c：3d：delete

segment 2

a：2b：1c：4d：5merged segment 1 and segment 2a：1b：2c：3

compaction可以使segment更小，我們可以同時合併多個compaction。另外，segment是不可更改的文件，compaction不會影響正常的讀寫操作。當compaction在後台線程進行，使用舊的segment進行讀。一旦合併操作完成，我們將讀操作切換到新的segment，這個時候舊的segnent可以被刪除了。

這個時候，每個segment在內存中都有自己的hash table結構了。對於一個查詢，我們先從最新的segment的hash table結構查詢，如果沒有再查詢次新的hash table。由於合併過程使得segment個數變少，所以我們並不需要查詢過多的文件。但是在實際生產中，還有許多細節要考慮：

文件格式。csv並不是最好的格式，二進位格式會更快和更簡單。二進位格式會首先編碼value的大小，然後跟一個原始的字元串。
刪除數據。由於採用了append-only的方式，刪除數據需要特殊標記，在compaction的時候再真正刪除。
宕機恢復。如果資料庫重啟，內存中的哈希索引需要丟失重建，如果從原始數據重建，由於數據量大會很慢，從而導致回復很慢。所以，需要定期的對索引做快照到disk。
部分寫操作。如果數據寫了一半資料庫宕機了，需要通過checksums來檢查數據的完整性，對不完整的數據進行丟棄。
並發控制。由於寫操作具有嚴格的時序性，所以常見的實現方式是單線程來完成。由於segment不可更改，所以可以多線程共同讀。

為什麼使用append-only而不是原地更新呢？原因如下：

appending和compaction是順序操作，遠比隨機寫快得多，尤其是在磁性旋轉盤硬碟驅動器上，在flash-based solid state drivers（SSDs）也是如此。
並發控制和宕機恢復會很簡單。比如，不使用append-only，宕機時你正在寫，會導致寫一半的狀況，使得數據部分新部分舊。
合併舊的segment避免了文件碎片。

但是，此時的hash table也會有一些限制：

hash table必須呆在內存里。當key數量過多時，無法全部保存在內存里。原則上，你可以將hash table保存在disk上，但是實際操作上比較困難，這會需要很多隨機IO，當磁碟滿了時很難擴充，hash碰撞也會比難處理。
scan會很困難。比如掃描000-999之間的數據，實際上需要查看所有的hash table。

下面我們會介紹不受這些約束的索引結構。

SSTables和LSM-Trees

在基於log結構的segment中，數據是一系列的key-value結構，這些數據對沒有順序可言。現在，我們要求這些數據對有序，這樣的數據格式被稱為SSTable（Sorted String Table）。另外，每個key在segment中要求只出現一次，compaction可以確保做到。SStable有很多優勢，如下：

合併segment簡單且高效，即使是在文件大於內存的情況下。可以採用一種類似mergesort的演算法（同時開始讀取輸入文件的第一個key，將最小的key拷貝到輸出文件，repeat），從而產生一個新的segment。如果key出現在多個文件中，將使用最新的值。
對於讀操作，不需要在內存中記錄所有的key，只需要記錄一些粗力度的索引即可。比如，在一個segment中要查找一個key，可以先定位到具體的block（block是對segment進一步的劃分），然後遍歷即可。（如果所有的key-value大小一樣，可以進行二分查找，但是實際情況每條數據大小並不相同）
Block可以進行壓縮，減少磁碟大小和磁碟IO。

構建SSTable

對於有序segment，依靠append-only是無法構建的，但是可以首先在內存中構建（採用紅黑樹、AVL樹）。SSTable的構建過程如下：

當來了一個write操作，將數據插入到內存的平衡樹結構中（memtable）。
當memtable大小超過設置（一般MB），將memtable寫出到磁碟的SSTable。這可以很高效地做到，因為memtable是有序的。這個SSTable會成為最新的SSTable。在寫memtable到SSTable的同時，可以令起一個實例來寫memtable。
當來了一個read操作，先在memtable中查詢，再按照新舊順序在SSTable中查詢。
後台有一個合併的compaction在合併文件。

為了防止宕機丟memtable的數據，每個寫操作需要append到一個disk上的log文件，用於宕機恢復。當memtable寫到SSTable後，就可以將對應的log刪除了。

LSM-tree的由來

構建SSTable的演算法被使用在levelDB和RocksDB中，一種可嵌套key-value存儲引擎。levelDB可以在Riak中替代Bitcask，類似的存儲引擎被應用到Cassandra和HBase中，二者都是受谷歌BigTable論文的啟發。

最開始，這種索引結構出現在Partrick ONeil et al.的Log-Structured Merge-Tree（LSM-Tree）中，所以後續的基於這種合併、compaction的有序文件都被稱作LSM存儲引擎。

Lucene是Elasticsearch和Solr使用的全文本搜索技術，雖然全文本索引比較複雜，但是思想類似，它會保存一個key-list的結構，其中list中是所有包含key的文檔ID。

性能優化

實際生產中有很多細節需要考慮以提升性能。例如，LSM-tree的演算法在查找不存在的key時會很慢，因為需要遍歷所有文件。針對這種問題，存儲引擎使用了Bloom filters來優化，這是一種逼近所有內容的內存結構，它可以告訴你key是否存在。

針對SSTable的compaction和合併，也有許多策略，最常見的是按照size-tiered和level。levelDB和RocksDB使用level的compaction，HBase使用size-tiered的，Cassandra都支持。在size-tiered中，新的和小的SSTable被合併成老的和大的SSTable。在level中，key 範圍被分成更小的SSTable，老的數據被移到單獨的level，從而允許增量compaction和減少磁碟空間。

B-Trees

前面討論了基於log結構的索引，它們被廣泛地接受，但是B-Tree還是當前使用最廣泛的索引系統。自1970年被引入以來，它被廣泛的應用在各種關係型和非關係型資料庫中。LSM-Tree將資料庫分成了更小的segment，採用順序寫的方式。B-Tree則相反，它將資料庫切分成固定大小的blocks（或者叫page），一般是4KB大小（可能更大）。這種設計更貼合硬體系統，因為磁碟也是被組織成固定大小的block。

B-Tree中每一頁都有一個地址，允許其他頁引用，類似於指針，但是存儲在磁碟上。我們可以使用這些頁引用構建一個樹形頁，如下圖所示：

概述