可靠存儲的索引設計，對比LSM-Tree和B-Tree

首先

許多資料庫系統使用日志（log）來記錄順序寫入，用于提高寫性能、資料持久化等等；這套系統叫做日志機制。在日志機制的基礎上，如果高效地查找資料庫中特定鍵的值，需要其他的機制（也就是索引機制）來輔助執行。

最樸素的存儲與查找的實作

db_set(){
     echo "$1,$2" >> database
 }
 
 db_get(){
     grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
 }           

會生成這樣的檔案

# database
 c,[1, 2, 3]
 a,[6, 7]
 a,[15, 34, 1]
 d,"1gfvaw1fva"           

一個追加的日志機制看起來非常浪費空間，為什麼不原地更新呢。我們簡單論證一下日志機制的優越性

1. 追加寫的速度遠比随機寫快。
2. 因為日志檔案是隻增不改的，是以可以并發讀。
3. 因為日志檔案是追加式的，并發和崩潰恢複就很友善。
4. 可以通過合并段檔案（當單個日志檔案過大，就建立一個日志檔案，稱為分段）來避免空間浪費和碎片化。

我們需要解決的問題，其實不隻是快速查找，一共有以下這些問題，我們提前列出來，然後看看不同的索引結構，對這些問題的處理有何差别。

• 快速讀已存在的key
• 快速讀不存在key
• 快速範圍搜尋
• 快速寫
• 快速删
• 壓縮日志（檔案大小）
• 索引持久化

哈希索引

由于目前的資料都是key/value式的，很容易就想到使用類似map、dict的結構來實作索引：

在資料寫入檔案的時候，在記憶體中維護着 key的hash值 -> key、寫入資料時檔案大小（offset）和資料的大小（limit）。（暫不考慮hash沖突）

對于寫操作，就如上所示。如果已有這個key，則更新索引。沒有則添加索引。因為key、offset、limit的大小都是有限的（比如256、int64、int64），是以很容易使用數組來高效實作。

對于讀操作，順着key的hash值找到offset和limit，直接可以定位到檔案的某一位置，隻需要一次磁盤尋址。

以上是哈希索引的主要内容。針對壓縮日志，哈希索引一般這麼處理：

當單個日志檔案增長到一定大小，就新開一個日志檔案和這個日志檔案對應的哈希表（每個日志檔案都對應着一個哈希表），将所有的寫操作轉移到新的日志檔案之中。

之後對舊日志檔案進行壓縮，并對壓縮後的日志建立新的哈希表。在壓縮的過程中，因為是隻讀的，是以讀請求依舊可以使用舊日志檔案。當日志檔案多了之後，還可以合并多個日志檔案。

例如上面那個檔案，壓縮之後會變成這樣。實際中壓縮的效率會更加高。

# database
 c,[1, 2, 3]
 a,[15, 34, 1]
 d,"1gfvaw1fva"           

哈希索引簡單清晰，但是也存在一些問題。比如哈希表必須全部放入記憶體、哈希沖突處理起來複雜、區間查詢效率不高等等。對于索引持久化，哈希是以可以把舊日志檔案的舊哈希表持久化，通過最新的日志檔案重構最新的哈希表。

SSTables和LSM-Tree

上面的索引依靠hash來建立，是以是無序的，必須要放在記憶體中才能實作高效的随機通路。想想，其他資料結構中，有序的資料機構的随機通路效率一般也比較高。比如有序數組、各種查找樹等。有序的key/value日志，稱為排序字元串表。事實上不隻是随機通路效率高，我們一個一個來梳理好處：

1. 由于其有序，即使存放在磁盤之中，也能比較高效地進行二分查找（哈希表由于哈希沖突，磁盤查找并不友善）。
2. 由于其有序，我們可以建立稀疏的記憶體索引，有效地減小了記憶體的占用。
3. 由于有序，當段檔案過大過多時，也可以通過K路歸并來實作日志壓縮，占用較小的記憶體。
4. 由于有序，範圍查找相當友善

好了，既然有這麼多好處，我們來考慮一下怎麼在日志體系下應用排序字元串表（畢竟我們也不想丢失日志體系的好處）

我們在記憶體中維護一個平衡查找樹的資料結構（比如紅黑樹），這個樹有時被稱為記憶體表。

對于寫操作，往磁盤中寫入日志（不排序），往記憶體表中寫入key和value。當記憶體表的大小超過一定門檻值之後，開一個新的記憶體表，将舊記憶體表轉化為排序字元串表，存入磁盤。這個存入磁盤的排序字元串表，稱為SSTable（記憶體表和SSTable都來自于Google的Bigtable論文）。

對于讀操作，先嘗試在記憶體表中查找，然後是最新的SSTable，然後是次新的SSTable，直到找到目标或者為空。

背景程序周期性合并與壓縮SSTable

資料庫崩潰後，通過日志檔案恢複記憶體表（SSTable在磁盤中，不用恢複）

這套算法本質上被LevelDB和RocksDB使用。算法的最初結構是建立在更加早期的日志結構檔案系統之上，被稱為Log-Structured Merge-Tree（LSM-Tree）。

還有一些政策能決定壓縮和合并的時機，比如對資料使用分層壓縮（LevelDB和RocksDB使用）與大小分級（HBase），能起到性能優化的效果，但是這裡不多贅述。

B-trees

B-tree也是有序的，但是除了有序之外，其他地方都和LSM-Tree不一樣。

之前看到的結構，都是對資料分段，一般大小在幾M或者更大。但是B-tree将資料分頁，每頁為4k（可以更大）。頁是内部讀寫的最小操作機關。4k這個數字，比較接近底層硬體的布局，是以性能也不錯。

每個頁面都通過位址進行辨別，每個頁面都負責了一定的範圍。某一個頁面被指定為根頁面，父頁會引用子頁（比如一個根頁的範圍是0-1000，其10個子頁分别覆寫100的範圍，其共100個孫頁，每個負責10的範圍。在這個例子中，隻有孫頁記錄了資料，其他頁隻記錄引用），父頁對子頁的引用按照子頁的範圍排序，葉子頁的記錄安排key排序。

對于更新操作，首先搜尋包含該鍵的子頁，然後更新子頁，再将子頁重新寫回硬碟。（看出來，都是以子頁為機關操作）

對于新增操作，首先找到符合其鍵範圍的子頁，然後将其添加到此頁之中。如果某個範圍内的子頁已經沒有額外的空間了，那麼将會把該子頁拆分為兩個兩頁，并更新父頁的引用。

對于讀操作，先從根頁開始，通過二分找到合适的範圍區間，然後進入到下一個頁，直到達到葉子頁，找到記錄或為空。

對于删除操作，比較複雜，暫且不談也罷。

通過在添加鍵的時候分裂頁面，可以保持數的平衡。一個頁包含的子頁引用數量稱為分支因子，一般分支因子在幾百個。分支因子為512的4KB頁的四級樹可以存儲256TB（5124∗4KB/1024KB/1024MB/1024GB=256TB512^4 * 4KB / 1024KB / 1024MB / 1024GB = 256TB5124∗4KB/1024KB/1024MB/1024GB=256TB)

如果資料庫在頁面分裂時崩潰（此時需要寫兩個頁，并更新父頁對子頁的引用），會産生資料不一緻。是以對于B-tree樹的實作，依舊會借助日志體系，被稱為預寫日志（write-ahead-log，WAL），幫助B-tree恢複狀态。另一種更加常見的操作，是使用寫時複制。先将兩個新的子頁寫入其他的位置，然後再更新父頁，丢棄舊子頁。

并發通路時，通常使用鎖存器（輕量級的鎖）保護樹的資料結構完成。

B-tree樹太過常見了，是以研究特别多，有很多優化，這裡列舉一些

• 壓縮鍵的資訊。比如字元串型，對于根頁，可能隻需要記錄前兩位字元串即可。
• 盡可能将兄弟葉子頁按順序儲存在磁盤上。但是這個事情會随着樹的增長産生困難。
• 建立到左右兄弟頁的引用，友善進行大規模的周遊。（B+樹特性）
• 隻有葉子節點才記錄資料，非葉子節點隻記錄索引（B+樹特性）

暫時的小結

對比一下三種存儲模式。需要注意的是，到這裡為止，我們比較的都是key/value型的資料（關系型資料庫，也可以把主鍵視為key，其他視為value），所在的計算機架構都嚴格區分了記憶體和磁盤的功能與性能。如果抛開以上兩個定語，則目前為止的比較也就不再準确。

哈希索引	LSM-tree	B-tree
讀已存在的key	高效（哈希沖突）	一般	高效
讀不存在key	低效，可借助布爾過濾器	低效，可借助布爾過濾器	高效
範圍搜尋	極低效	一般，需要通路多個SSTable，但是每個表的通路相對迅速	高效
寫	極高效	極高效	高效
删	極高效	極高效	高效
壓縮日志	高效	高效	一般
索引持久化	無、恢複時重構索引	有、恢複時重構少量索引	有且穩定
記憶體空間	大	一般	較低
磁盤空間	一般	較小	較大

對比B-tree和LSM-tree

B-tree比LSM-tree成熟，但是兩者目前都很有吸引力。一般而言認為LSM-tree寫入更快，B-tree讀的表現更加快且穩定。但是還有一些很細節的點，需要我們去考慮。

LSM-tree	B-tree
寫放大（一次寫入請求導緻的多次磁盤寫），由于SSD隻能承受有限次數的擦除覆寫，是以寫放大與成本直接挂鈎。	較差	一般
磁盤空間的緊湊程度。更加緊湊的資料存儲，能在有限的I/O帶寬中支援更多的讀寫請求，減小存儲空間倒是次要的。	較好	一般
磁盤的I/O始終是有限的，如果一個資料庫除了處理請求，還有别的線程消耗I/O，則可能會影響處理請求的速度。	有背景壓縮程式	沒這種顧慮
一些特殊操作，其速度可能夠不上請求的速度，會拖慢請求。	壓縮程式可能會跟不上順序寫，需要額外的監控措施。	保持樹平衡，問題較小
并發控制	較友善	一般
事務隔離	不清楚	較友善

關系型資料庫

我們回到關系型資料庫，看看上文的哪些是關系型資料庫中用到的，那些是可以用到但是有更好的方案的。這樣學習完，算是對整個知識體系有了更加切實的體會。

二級索引

在InnoDB存儲引擎中，我們使用把表的主鍵（聚集索引）視為key，并對其應用B-tree結構來持久化存儲。而對于我們之後添加的索引（非聚集索引），則需要額外建構查找樹，這棵樹的key一般是我們頻繁查詢的列，value是對應記錄的主鍵或者磁盤位址。

在使用二級索引的性能提升時，别忘了為了維護二級索引所帶來的在寫、保證事務性上的開銷。

二級索引中的多列索引

關系型資料庫中的多列索引被稱為級聯索引。其不過簡單的将多個列按順序組合在一起成為key。是以查詢時也要按列的順序去查詢。

還有一種多列索引，被稱為多元索引，常用于地理空間資料等。例如PostGIS實作的R樹（這塊我也沒深入研究）

作者：浪狼郎

連結：https://juejin.cn/post/7143109104213426206