數(shù)據(jù)庫(kù)中非常常用的索引數(shù)據(jù)結(jié)構(gòu)——B+ 樹(shù)，在過(guò)去很多年里它都是數(shù)據(jù)庫(kù)索引的首選實(shí)現(xiàn)方式俊扳，但是這種數(shù)據(jù)結(jié)構(gòu)也并不是很完美途蒋。因?yàn)椋看涡薷臄?shù)據(jù)都很有可能破壞 B+ 樹(shù)的約束馋记，我們需要對(duì)整棵樹(shù)進(jìn)行遞歸的合并号坡、分裂等調(diào)整操作，而不同節(jié)點(diǎn)在磁盤(pán)上的位置很可能并不是連續(xù)的梯醒，這就導(dǎo)致我們需要不斷地做隨機(jī)寫(xiě)入的操作宽堆，而隨機(jī)寫(xiě)入的性能是比較差的，這個(gè)問(wèn)題在寫(xiě)多讀少的場(chǎng)景下會(huì)更加明顯茸习。
LSM Tree（Log Structure Merge Tree）是比 B+ 樹(shù)更適合寫(xiě)多讀少場(chǎng)景的索引結(jié)構(gòu)畜隶，也廣泛應(yīng)用在各大 NoSQL 中。比如基于 LSM 樹(shù)實(shí)現(xiàn)底層索引結(jié)構(gòu)的 RocksDB号胚、LevelDB籽慢。
LSM Tree 的實(shí)現(xiàn)原理：
LSM 樹(shù)包含了三個(gè)部分，memtable猫胁、immutable memtable箱亿、SSTable前兩個(gè)在內(nèi)存中（使用預(yù)寫(xiě)日志的機(jī)制來(lái)確保數(shù)據(jù)的持久性），最后一個(gè)在磁盤(pán)中弃秆。同樣届惋，我們會(huì)先臨時(shí)地把數(shù)據(jù)寫(xiě)在 memtable 中，然后在合適的時(shí)機(jī)刷入磁盤(pán)上的 SSTable 中菠赚。
1.Memtable
Memtable 顯然是內(nèi)存中的數(shù)據(jù)結(jié)構(gòu)脑豹，存儲(chǔ)的是近期更新的記錄值，可以用各種有序高效的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)衡查，比如跳躍表瘩欺、紅黑樹(shù)，不過(guò)可以簡(jiǎn)單的理解Memtable是一個(gè) 有序Map峡捡。
2.Immutable Table
在 Memtable 存儲(chǔ)的元素到達(dá)一個(gè)數(shù)量級(jí)之后（大小一般為虛擬內(nèi)存的頁(yè)的倍數(shù) 4n KB）击碗，會(huì)把它固化成 immutable table筑悴，從字面上理解们拙，就是不可變表稍途。很明顯這就是 memtable 的拷貝操作，因?yàn)榭截愡^(guò)程是需要時(shí)間的砚婆，但同時(shí)我們的系統(tǒng)很可能仍然在對(duì)外工作械拍，所以創(chuàng)建副本可以很好的地幫助我們避免讀寫(xiě)沖突競(jìng)爭(zhēng)，從而避免阻塞装盯，提高系統(tǒng)性能坷虑。
3.SSTable
SSTable 是整個(gè) LSM Tree 的核心，畢竟我們的大部分?jǐn)?shù)據(jù)都是存儲(chǔ)在磁盤(pán)上的埂奈，SSTable 就是在磁盤(pán)上做持久化的部分迄损。本質(zhì)其實(shí)很簡(jiǎn)單，就是一段段按照 key 有序排列的鍵值對(duì)账磺，而持久化數(shù)據(jù)到磁盤(pán)最高效的方式就是順序?qū)懸槐椋樞騃O）芹敌，每次內(nèi)存中的數(shù)據(jù)immutable table，我們都一次性 dump 成磁盤(pán)上的一段自然是比較快的垮抗，這樣一段段的數(shù)據(jù)氏捞，我們就稱(chēng)為一個(gè)個(gè) segment。當(dāng)然冒版，后面存儲(chǔ)的段和前面存儲(chǔ)的段液茎，key 可能是重復(fù)的，因?yàn)楹竺娴亩涡乱恍┐俏耍栽谟兄貜?fù)的時(shí)候捆等，最靠后的段中的記錄值，就是某個(gè) key 最新的狀態(tài)续室。
但很顯然楚里，這樣的存儲(chǔ)會(huì)有很多問(wèn)題，首先數(shù)據(jù)冗余很大猎贴，隨著時(shí)間推移班缎，磁盤(pán)上就會(huì)有大量重復(fù)的鍵，其次我們需要遍歷每個(gè)有序的 segment她渴，查看數(shù)據(jù)是否存在达址。隨著數(shù)據(jù)量增大，最壞情況下趁耗，要遍歷的 segment 會(huì)非常多沉唠，整個(gè)系統(tǒng)的查詢(xún)效率顯然是慘不忍睹的。
所以我們需要合并 segment苛败，合并前老的 segment 長(zhǎng)度都是一樣的且有序的满葛，在 SSTable 的主流實(shí)現(xiàn)里径簿，我們會(huì)把不同的階段被合并的 segment 放到不同的層中，并限制每一層數(shù)量嘀韧，當(dāng)某層 segment 超過(guò)一定數(shù)量篇亭，我們就會(huì)把它們刪除，合并出一個(gè)更大的 segment 放入下一層（低層中的 segment 是更新的記錄值锄贷，高層的則是更老的記錄值）译蒂。同時(shí)也會(huì)對(duì)相同的key進(jìn)行最新值的覆蓋，以減少數(shù)據(jù)的冗余谊却。
檢索的時(shí)候柔昼，我們只需要按照“內(nèi)存 -> SSTable 第一層->SSTable 第二層”這樣的順序，去遍歷每層中不同段是否包含目標(biāo) key炎辨。每個(gè)段內(nèi)都是有序存儲(chǔ)的捕透，所以整體讀的時(shí)間復(fù)雜度也是可以接受的，確實(shí)可能會(huì)比 B+ 樹(shù)的查詢(xún)效率低一些碴萧，不過(guò)輔以布隆過(guò)濾器等手段乙嘀，劣化也不會(huì)非常明顯，在許多讀寫(xiě)比不到 1:10 的場(chǎng)景下勿决，順序?qū)憥?lái)的寫(xiě)性能提升是非常令人滿(mǎn)意的乒躺。
總結(jié)自（極客時(shí)間-業(yè)務(wù)開(kāi)發(fā)算法50講-黃清昊）
