基于合并和壓縮排序文件原理，以日志結構為主的的存儲引擎——LSM引擎。
使用相關算法的數(shù)據(jù)庫：LevelDB、RocksDB、Cassandra、HBase等
- log寫入（追加寫入）時，將其添加到內存中的平衡樹（內存表）數(shù)據(jù)結構中。
- 當內存大于某個閾值（通常為若干MB，如redis自動aof的size是64mb）時，將其作為SSTable文件寫入磁盤。由于樹已經(jīng)維護了按key排序的key-value對，寫磁盤可以相對高效。新的SSTable已經(jīng)成為數(shù)據(jù)庫的最新部分。當SSTable寫磁盤的時候，寫入可以繼續(xù)添加到一個新的內存表實例。
- 每次處理讀請求，首先常識在內存表中查找key，然后是最新的磁盤段文件，然后是次新的磁盤段文件，以此類推，直到找到目標或者為空。
- 后臺進程周期性地執(zhí)行合并與壓縮的過程，來合并多個段文件（可變大小），并丟棄哪些被覆蓋或者被刪除的部分。
- 如果數(shù)據(jù)庫崩潰，在內存表中但是尚未寫入磁盤的log將會丟失，為了避免這種情況，可以在磁盤上保存單獨的日志，每個寫入都會立刻追加到日志。日志文件不需要按鍵排序，它唯一的目的是在崩潰中恢復內存表，當內存表寫入SSTable時，相應的日志就可以被丟棄了。
一些可以優(yōu)化的點
- 布隆過濾器，直接判斷key是否存在，節(jié)省空key的查找
- 改變段合并和壓縮的時機
- 大小分級，HBase
- 分層壓縮，LevelDB，RockesDB
- Cassandra支持以上兩種
相對于B-tree的優(yōu)點
- LSM順序寫入磁盤的效率遠高于隨機寫，并且定期重寫SSTable可以去除磁盤碎片化。B-Tree則可能使磁盤空間部分空間無法使用（比如分裂頁崩潰時導致的孤兒頁）。
- LSM相對于B-Tree擁有較小的寫放大，B-Tree索引需要至少兩次寫入（一次WAL日志，一次寫入樹的頁），每次更改有都要承受整個頁的更改開銷。而LSM以順序方式寫入文件，不必重寫樹中多個頁。
相對于B-tree的缺點
- 壓縮過程容易干擾正在進行的讀寫操作，造成讀寫等待。B-Tree查詢響應則更穩(wěn)定。
- 寫入吞吐高的情況下，壓縮帶寬可能被寫入帶寬占用導致不足，造成磁盤空間有大量未合并段占用空間，因此需要額外的監(jiān)控來及時發(fā)現(xiàn)這種情況。
- 同一個鍵可能存在多個位置，B-Tree則每個鍵都唯一衛(wèi)浴索引中的某個位置，更適合事務的使用。
最廣泛使用的索引——B-Tree
擁有n個分支因子的B-Tree的深度為logn，一般是3-4層，分支因子為500的4kb的頁可以存儲數(shù)據(jù)256TB。
- 將數(shù)據(jù)庫分解為固定大小的頁（內部讀寫最小單元），一般是4kb。每個頁使用地址/位置進行標識，可以讓一個頁引用另一個頁，形成一個樹狀結構。（類似指針，但是指向的是磁盤地址，不是內存）頁包含若干鍵和對子頁的引用等內容
- 指定b樹的一頁為根，每當查詢索引的一個鍵時候，從根節(jié)點開始
- 鍵的更新：搜索含此鍵的葉子頁，更改頁的值，將頁回寫到磁盤。
- 鍵的新增：類似于更新，如頁空間滿了，需要分裂成兩個頁，父頁也需要進行更新
- b樹的增刪改算法
一些存在的隱患以及可以采取防止手段
- 鍵的新增需要更新父頁時，數(shù)據(jù)庫崩潰導致索引被破壞
- 增加WAL（write-ahead log）日志，只支持追加寫。在數(shù)據(jù)庫奔潰的時候先用日志恢復B-tree
- 使用寫時復制，修改的頁被寫入不同的位置，樹中的父頁的新版本被創(chuàng)建，指向新的位置。（也能解決并發(fā)下多線程訪問的問題）
- 節(jié)省頁的空間，只保存鍵的縮略信息。B+樹
- 為葉子頁添加指向同級別的兄弟頁，可以順序掃描頁不同跳回父頁
