存儲引擎有兩大類
- LSM 存儲引擎
- 面向頁面的存儲引擎（基于 B-Tree）
世界上最簡單的資料庫
set(key, value) { echo "${key},${value}" > test.db}
get(key) { grep "^${key}," test.db | sed -e "s/^${key},//" | tail -n 1}
資料庫集在檔案末尾附加記錄，複雜度 O(1)。性能杠杠的。
讀取性能
在最壞的情況下，要搜尋記錄必須周遊資料庫中的所有記錄。時間複雜度為 O(n)
如何提高讀取性能？
在主要内容上建立索引，影響查詢的性能。
- 索引可提高讀取性能
- 索引會降低寫入性能。
哈希索引
你想見朋友，你知道他的社群名稱，但忘記了較高價的電梯大廈号碼。
一種方法是去每個家庭，詢問那所房子是否屬于你的朋友。最壞情況 O(N)
另一種方法是去社群居委會，根據他的名字詢問你朋友的門牌号碼。這就是基于哈希的索引的工作原理。
基于哈希的索引将鍵映射到存儲值的位置。
分段、合并和壓縮
磁盤空間不足
寫入操作追加在檔案末尾，它不斷變大，一段時間後會耗盡空間。
分割
當檔案大小增加門檻值時，關閉檔案并建立新的段檔案以進行寫入。
壓縮
壓縮重複的記錄，隻保留最新的記錄。
合并
分段和壓縮将繼續增加分段的數量。是以定期合并它們。
對檔案進行順序追加必然導緻大量資料備援，如何解決？
一般的解決方式是用背景線程，對檔案進行定時的壓縮合并，對于相同的鍵，隻保留最新的值。
那麼删除資料呢？
删除資料在對應的資料上标記一個墓碑，在進行合并日志段時，一旦發現标記墓碑，就會丢棄該記錄。
崩潰恢複：
由于是對檔案進行追加寫，記憶體中的索引檔案會丢失但是具體的資料檔案不會。我們可以通過掃描磁盤檔案重建立立索引，但由于是O（n）操作，在檔案過大時會消耗大量時間。
基于哈希的索引的優勢
- 寫入速度更快
- 并發和崩潰恢複更好
基于哈希的索引缺點
- 基于範圍的查詢效率低下
- 哈希索引适合基于記憶體
SSTable 和 LSM
SSTable 全稱 Sorted String Table，顧名思義，裡面的 key-value 都是有序儲存的
SStable在功能上隻是對hash加入了一個按鍵值排序。
SSTable的建構
解釋SSTable中的以下流程
- 寫入記憶體表
- 寫入段（磁盤）
- 讀（先記憶體，再磁盤）
- 背景排序歸并
SSTable的優點
- 合并和壓縮更容易：基于合并排序。
- 索引稀疏
基于 SSTable 的資料庫
如果使用sstable，先進行記憶體寫，是以我們也要考慮日志系統，類似innodb裡redolog方式來保證持久性。
LSM-Tree 全名叫Log-Structured Merge Tree，最早建立在日志結構檔案之上，現在基于合并和壓縮排序檔案原理的存儲引擎都統稱為LSM存儲引擎。
LSM樹，即日志結構合并樹(Log-Structured Merge-Tree)。其實它并不屬于一個具體的資料結構，它更多是一種資料結構的設計思想。
LSM（日志結構合并樹）
LSM 中的性能優化
布隆過濾器
如果資料庫中不存在記錄，則 DB 必須掃描所有段檔案。為了改進這個布隆過濾器被使用。
壓縮政策：Leveled vs Sized-Tired compaction
Size-tired compaction
Leveled compaction
B樹
由于傳統的機械磁盤具有快速順序讀寫，慢速随機讀寫的通路特性，為了改變這個特性，檔案系統或資料系統通常會對資料進行排序後存儲，加快資料檢索速度，這就需要保證資料在不斷更新、插入、删除保持依然有序，目前最廣泛的做法就是使用B+樹和LSM樹。
B+樹
B+樹是一種專門針對磁盤存儲而優化的N叉排序樹，以樹節點為機關存儲在磁盤中，從根開始查找所需資料所在的節點編号和磁盤位置，将起加載到記憶體中然後繼續查找，直到找到所需的資料。
插入
WAL日志的工作
B 樹與 LSM 樹
經驗法則
1、當寫比讀多時，LSM樹相比于B+樹有更好的性能，因為随着insert操作，為了維護B+樹結構，節點分裂。讀磁盤的随機讀寫機率會變大，性能會逐漸減弱。 LSM樹相比于B+樹，多次單頁随機寫變成一次多頁随機寫,複用了磁盤尋道時間，極大提高寫性能。不過付出代價就是放棄部分讀性能。
2、B+ 樹每次都需要查詢到葉子節點，查詢性能穩定，葉子節點形成有序連結清單，範圍查詢友善