本篇主要讨論的是不同存儲結構（主要是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進行排序後有以下幾個好處：
- 合并更加簡單高效 ，即使資料檔案段大于記憶體，也可以使用類似 歸并排序 算法進行資料段的壓縮，即将一個大檔案拆成多個小資料進行壓縮。如果多個檔案段中有相同的key，那麼以最新的檔案段的key為準。
- 緩解哈希索引需要整個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》第三章節，對分布式系統感興趣的童鞋可以看看此書，肯定不會失望的。
以上~