# 日志結(jié)構(gòu)存儲(chǔ)引擎
使用日志記錄數(shù)據(jù)捌浩，僅支持追加形式的記錄集合。
# 面向頁(yè)的存儲(chǔ)引擎
# 索引是基于原始數(shù)據(jù)派生而來(lái)的額外的數(shù)據(jù)結(jié)構(gòu)铝宵，是為了快速定位想要的數(shù)據(jù)翎冲，也就是提高查詢的性能。
# 在存儲(chǔ)系統(tǒng)中重要的權(quán)衡設(shè)計(jì)：適當(dāng)?shù)乃饕梢约涌熳x取速度谨敛，但是每個(gè)索引會(huì)減慢寫的速度究履，兩者需要根據(jù)實(shí)際進(jìn)行權(quán)衡。
# 哈希索引：以鍵-值方式索引數(shù)據(jù)脸狸。
# 為什么日志采取追加方式最仑，而不進(jìn)行原地更新？
1. 追加和分段寫主要是順序?qū)懘都祝入S機(jī)寫速度更快泥彤。
2. 段文件是追加的，不可變的卿啡，故并發(fā)和崩潰恢復(fù)更為簡(jiǎn)單吟吝。
# 哈希（key-value）到SSTables（排序字符串表）：改變段文件的格式，要求key-value按鍵排序颈娜。每個(gè)鍵在每個(gè)合并的段文件中只能出現(xiàn)一次剑逃，相比哈希日志段浙宜，有兩個(gè)優(yōu)點(diǎn)：
1. 合并段更加簡(jiǎn)單高效，即使文件大于可用內(nèi)存炕贵。
2. 在文件查找特定的鍵時(shí)梆奈，不在需要在內(nèi)存中保存所有鍵的索引
問題來(lái)了？寫入是任意順序的称开，怎么讓數(shù)據(jù)按鍵排序？答：內(nèi)存排序的數(shù)據(jù)結(jié)構(gòu)：紅黑樹或AVL樹
存儲(chǔ)引擎的基本工作流程：
1. 當(dāng)寫入時(shí)乓梨，將其添加到內(nèi)存中的平衡數(shù)數(shù)據(jù)結(jié)構(gòu)（內(nèi)存表）中鳖轰。
2. 當(dāng)內(nèi)存表大于某個(gè)閥值時(shí)，將其作為SSTable文件寫入磁盤扶镀。
3. 為了處理請(qǐng)求蕴侣，首先在內(nèi)存表查找，然后從最新的依次查找段文件臭觉。
4. 后臺(tái)進(jìn)程周期性執(zhí)行段文件合并與壓縮昆雀，并丟棄已經(jīng)覆蓋或刪除的值。
從SSTablesdao LSM-Tree(日志結(jié)構(gòu)的合并樹)
LSM-Tree：基于合并與壓縮排序文件的原理的存儲(chǔ)引擎統(tǒng)稱蝠筑。
# 最廣泛使用的存儲(chǔ)引擎-B-tree
> 日志結(jié)構(gòu)索引將數(shù)據(jù)庫(kù)分解為可變大小的段狞膘，通常大小為幾兆或更大，并且要求順序?qū)懭攵耸惨摇６旆猓珺-tree將數(shù)據(jù)庫(kù)分解為固定大小的塊或頁(yè)，每個(gè)也可以使用一個(gè)地址標(biāo)識(shí)臣镣，傳統(tǒng)大小為4K辅愿，頁(yè)是操作系統(tǒng)讀寫的最小單元，這種設(shè)計(jì)更接近底層忆某。
# 原理：某一頁(yè)被指定為B-tree的根点待；每當(dāng)查找索引的一個(gè)鍵時(shí)，總是從這里開始弃舒；該頁(yè)面包含了若干個(gè)鍵和對(duì)子頁(yè)的引用癞埠；每個(gè)孩子都負(fù)責(zé)一個(gè)連續(xù)范圍內(nèi)的鍵，相鄰引用之間的鍵可以指示這些范圍之間的邊界棒坏。
為了保證數(shù)據(jù)庫(kù)能從崩潰中恢復(fù)燕差，B-tree增加了預(yù)寫日志（WAL：write-ahead log），這是一個(gè)僅支持追加修改的文件坝冕，每個(gè)B-tree的修改必須先更新WAL然后再修改樹本身的頁(yè)徒探。
