• 順序存盤與哈希索引
• SSTable和LSM tree
• B-Tree
• 存盤結構的比對
• 小結

所謂資料庫，最基礎的功能，就是保存資料，并且在需要的時候可以方便地檢索到需要的資料，在這個基礎上，演化出了不同的資料庫系統，以及多種索引機制幫助檢索資料，這篇我們就來討論幾種常見的資料存盤和索引機制，主要是B-tree，LSM-Tree，以及它們對應的優缺點，

順序存盤與哈希索引

試想一下，如果按照保存資料，并且在需要的時候可以方便地檢索到需要的資料這一標準，設計一個簡單的資料庫，那么最簡單的做法應該怎么做呢？

最簡單的做法，就是通過順序保存資料到一個日志檔案中，然后通過索引，這里以哈希索引為例（比如java的hashMap），記錄每條資料的key以及對應的位移，將其保存到記憶體中，避免隨機檢索巨大的開銷，值得注意的是，引入索引，雖然會顯著提高查詢效率，但會略微降低寫入速度，因為每次寫入的時候都需要額外寫入到哈希索引中，這一點對大部分索引都是適用的，

上圖為哈希索引示例，下面是順序存盤在磁盤上是日志資料，上面的記憶體中的哈希索引，哈希索引是很多復雜索引的基礎，比如在mysql中就有提供哈希索引的選項，當然哈希索引并不常用，因為它最基礎，同時也意味著它最容易被優化，

上述形式的順序存盤+哈希索引中，增加資料和查找資料相對容易理解，而修改資料則可以通過將新資料追加到檔案尾部，重新生成索引實作，洗掉操作則可以給與哈希索引一個識別符號實作（如對應key置為-1），

但這樣有一個問題，可能會出現磁盤耗盡的情況，針對這一個問題，我們可以將日志檔案拆分成多個一定大小的檔案段（這里的檔案段可以理解為接受統一管理的資料檔案），當一個檔案段達到一定大小，比如4kb的時候，就關閉它，新建一個檔案段，而舊的檔案段可以進行壓縮，前面提到過，洗掉和修改都是通過追加日志相同的key-value實作的，那么早先的資料其實就已經沒用的，所以壓縮的時候只保留最新的key資料，壓縮到程序如下面這張圖所示：

圖中上面的部分就是順序存盤的資料，可以發現其中有很多的key都是相同的，這是因為順序存盤情況下，修改資料就是不斷新寫入相同的key，這種情況我們要的只有相同key的最新的value，所以壓縮程序也是一個清理磁盤的程序，

壓縮合并程序可以由后臺進行默默進行，所以不必擔心這個程序影響查詢性能，上圖中只有一個資料檔案段，但實際上可以有多個檔案段，多個檔案段也可以合并（類似于Hbase中多個檔案的merge操作），

當然這樣的優化可以極大程度節省空間，但必不可少得會給檢索帶來時間上的損耗，在多個檔案段的情況，每個檔案段都有自己的哈希索引，故而要查找資料會首先根據key查找記憶體中最新檔案段的哈希索引，如果找不到，那么找次新檔案段的哈希索引，接著找次新的哈希索引，直到遍歷所有檔案段的哈希索引，

綜上，順序存盤+哈希索引優點明顯，簡單，高效，缺點是哈希索引需全部存到記憶體（如果將哈希索引放到磁盤那相當于放棄了檢索的高效），并且難以實作區域查詢，

為了解決它的這些問題，我們可以將哈希索引做一些小小的改變，具體來說，就是讓檔案段的資料，按key進行排序存盤，這樣會帶來哪些改變呢？

SSTable和LSM tree

將資料檔案段中的資料按key進行排序，并且保證相同的key只出現一次（在壓縮的時候保證），這種格式就稱之為排序字串表，簡稱SStable（Sorted String Table），

將資料按Key進行排序后有以下幾個好處：

1. 合并更加簡單高效，即使資料檔案段大于記憶體，也可以使用類似歸并排序演算法進行資料段的壓縮，即將一個大檔案拆成多個小資料進行壓縮，如果多個檔案段中有相同的key，那么以最新的檔案段的key為準，
2. 緩解哈希索引需要整個hashMap存盤到記憶體的窘境，因為key是排序的，所以可以在記憶體中維持一個稀疏索引，存盤每個key的范圍，具體見下圖，并且這個稀疏索引所需的記憶體空間是很小的，

通過稍微改變一下檔案段的結果，就獲得如此多的好處，但還有一個問題，前面的哈希索引是基于順序存盤的日志檔案的，要讓SStable按key排序，那就不能順序存盤磁盤了呀（即無法存盤的時候立即寫入磁盤）！！的確是這樣，雖然也可以使用類似B-tree來實作磁盤上的排序存盤，但轉換下思路，其實將資料先保存在記憶體中其實更加方便，

具體實作流程，是在記憶體中維護一個類似TreeMap的資料結構用于存盤資料（TreeMap底層是基于紅黑樹對存盤的key進行排序的，無論我們按照什么樣的順序存盤資料，TreeMap總是會將資料按照key進行排序），這個TreeMap稱為記憶體表，當記憶體表超過一定閾值的時候，就將其寫入到磁盤中，成為SStable，因為已經排好序，所以寫入的效率其實比想象的要高，后期再對磁盤中的SStable進行壓縮與合并操作，

當需要根據key檢索的時候，會先去記憶體表中檢索，找不到再去最新的SStable，再去次新的SStable，直到遍歷完全部，

上述這種索引結構被稱為之LSM-Tree，全稱是Log-Structured Merge-Tree，即日志合并樹，而這種基于合并和壓縮檔案原理的存盤引擎被稱為LSM存盤引擎，其中比較為人所知的是Hbase，

B-Tree

最后，我們再來討論流傳最久的資料庫村粗結構，與LSM-Tree這幾年才逐漸為人所知不同，B-tree存盤結構擔得起經久不衰這四個字，

B-tree本身是一種樹形的資料結構，更具體點說是一顆平衡查找樹，它也是通過存盤順序的key存盤資料（這一點和SStable有相似之處），不同于前面的LSM-tree的檔案段，B-tree將資料庫分解成固定大小的塊或頁，通常一個頁大小是4kb，這種分配方法更加貼合底層的磁盤，

當需要進行查找的時候，總是從根開始，根據范圍跳轉到對應的key，而其對應的value可以是值本身，也可以是指向存盤對應資料的磁盤地址，下圖是一個具體的例子：

而在更新或插入的時候，有可能會出現沒有足夠空間來容納新key的問題，這時候就會發生分裂，分裂操作是比較危險的，在分裂的時候如果資料庫崩潰，可能會導致索引被破壞，為了防止這個問題，可以引入預寫日志（write-ahead log，WAL）機制，mysql的binlog就是這樣的東西，具體說就是在執行操作的時候，將此次操作寫入一個只允許追加的檔案中，這樣一來當崩潰的時候就可以檢查日志并進行恢復，

存盤結構的比對

從使用的角度上來說，B-tree等索引存盤結構多用于OLTP型的資料庫，因為這類資料庫主要以事務，或是行級別的讀取和存盤為主的（比如Mysql），換句話說，這種型別的資料庫更多的操作是小批量或單行級別的更新或讀取，并且可能還有事務方面的需求，這種型別正是B-tree結構所擅長的，

而 LSM-tree則多用于大規模資料情況下的檢索分析和快速寫入的情況，在寫入的性能上，因為上直接寫入記憶體再定期刷入到磁盤中，所以寫入操作對用戶的感知而言上非常迅速的，而檢索速度也因為key順序存盤，可以快速定位到key對應的位置，因而具有較好的檢索性能，

但是LSM-tree比較顯著的應用方向還是在大規模分析這方面，在大規模分析（OLAP）場景下，資料通常都是列式存盤，并且需要全表掃描，其中磁盤資料可以使用二進制進行壓縮，讀取的時候可以有效減少磁盤IO的處理時間（與之相比，B-tree等存盤結構就無法充分壓縮，因為每次都只處理小部分資料），同時在存盤檔案中還能再進一步切分，比如將列式資料按照水平切分成不同的Page，同時存盤一些簡單的索引，用來指定不同Page大概范圍，Hadoop的存盤資料格式Parquet就是類似的設計，

小結

本篇主要討論了幾種基礎的存盤結構和索引以及其對應使用場景，限于篇幅，更多索引的變種無法多加討論，比如B-tree的優化版B+tree，多列索引等，

其實大部分資料庫或者說存盤引擎，都是針對不同的場景下，在舊有的基礎上進行一定程度的微改造創新，但大體的結構依舊是以上述兩三種為準，了解了上述幾種結構，對資料存盤方面應該能夠有一個感性的認知了，

此外本章多參考自《DDIA》第三章節，對分布式系統感興趣的童鞋可以看看此書，肯定不會失望的，

以上~

標籤：Java

上一篇：架構設計 | 異步處理流程，多種實作模式詳解

下一篇：SpringBoot整合Druid