每一種數據存儲系統，對應有一種存儲模型，或者叫存儲引擎。我們今天要介紹的是三種比較流行的存儲模型，分別是：Hash存儲模型B-Tree存儲模型LSM存儲模型不同存儲模型的應用情況1、Hash存儲模型redismemcache2、B-Tree存儲模型MySQL（以及大多數的關係型資料庫）MongoDB... ...
每一種數據存儲系統，對應有一種存儲模型，或者叫存儲引擎。我們今天要介紹的是三種比較流行的存儲模型，分別是：
- Hash存儲模型
- B-Tree存儲模型
- LSM存儲模型
不同存儲模型的應用情況
1、Hash存儲模型
- redis
- memcache
2、B-Tree存儲模型
- MySQL（以及大多數的關係型資料庫）
- MongoDB
3、LSM樹存儲模型
- HBase
- RocksDB
不同存儲模型介紹
1、Hash存儲模型
Hash存儲模型其實就是HashMap（哈希表）的持久化實現。這種模型的特點是與HashMap有密切關係的。我們知道HashMap可以支持：put（key）增加/修改、delete（key）刪除、get（key）隨機獲取操作，但是HashMap不支持get(1)這樣的操作。因為HashMap是無序的，不支持順序掃描。針對put、get操作，它的時間複雜度是O(1)，也就是說讀寫速度都很快，所以針對單個Key的操作是非常快速的。如果我們在應用中無需遍曆數據，Hash引擎是非常合適的。
首先，通過key，找到對應的文件編號。這個檢索的過程，是通過HashMap來實現的。
其次，通過文件編號找到存儲中的文件
再者，通過value長度和位置找到對應的行數據
最後，讀取出value內容
2、B-Tree存儲模型
B-Tree存儲模型由於是樹狀結構存儲，所以，它是不支持隨機讀寫的。就像我們學習二叉樹時，查找數據得通過遍歷樹的方式來查找數據。
上圖是一種典型的B-Tree存儲索引。葉子節點保存了每行的完整數據，非葉子節點保存了索引信息。數據在每個節點都是有序存儲的，但查詢數據的時候，需要從根節點遍歷，然後根據二分查找直到找到葉子節點。如果數據不再記憶體中，需要從磁碟中讀取，並載入到緩存。B+樹的根節點是常駐記憶體的，最多需要h-1次磁碟IO，複雜度為O(h) = O(logdN)。修改操作首先要記錄提交日誌，然後在修改記憶體中的B+樹。
3、LSM樹存儲引擎
LSM樹的思想很容易理解，就是將數據的新增、修改增量數據先保存在記憶體中，到達指定的大小限制後將修改操作批量寫入到磁碟。讀取時，需要合併磁碟中的歷史數據和記憶體中最近的修改操作。LSM的優勢在於有效地隨機寫入問題，但讀取可能需要訪問較多的磁碟文件。
- Level 0 ：日誌/記憶體
- 先寫入預寫日誌，再寫記憶體
- 寫入日誌是為了保障可用性
- Level 1：日誌/記憶體，當Level 0寫入達到閾值，通過非同步方式將部分數據刷寫到硬碟上
- Level 2：合併，由於不斷刷寫會產生大量小文件，這樣不利於管理和查詢。需要在合適的時機啟動一個非同步線程進行合併操作生成一個大文件
