# 日志結(jié)構(gòu)存儲引擎

使用日志記錄數(shù)據(jù)，僅支持追加形式的記錄集合。

# 面向頁的存儲引擎

# 索引是基于原始數(shù)據(jù)派生而來的額外的數(shù)據(jù)結(jié)構(gòu)，是為了快速定位想要的數(shù)據(jù)，也就是提高查詢的性能。

# 在存儲系統(tǒng)中重要的權(quán)衡設(shè)計：適當?shù)乃饕梢约涌熳x取速度，但是每個索引會減慢寫的速度，兩者需要根據(jù)實際進行權(quán)衡。

# 哈希索引：以鍵-值方式索引數(shù)據(jù)。

# 為什么日志采取追加方式，而不進行原地更新？

1. 追加和分段寫主要是順序?qū)懀入S機寫速度更快。

2. 段文件是追加的，不可變的，故并發(fā)和崩潰恢復(fù)更為簡單。

# 哈希（key-value）到SSTables（排序字符串表）：改變段文件的格式，要求key-value按鍵排序。每個鍵在每個合并的段文件中只能出現(xiàn)一次，相比哈希日志段，有兩個優(yōu)點：

1. 合并段更加簡單高效，即使文件大于可用內(nèi)存。

2. 在文件查找特定的鍵時，不在需要在內(nèi)存中保存所有鍵的索引

問題來了？寫入是任意順序的，怎么讓數(shù)據(jù)按鍵排序？答：內(nèi)存排序的數(shù)據(jù)結(jié)構(gòu)：紅黑樹或AVL樹

存儲引擎的基本工作流程：

1. 當寫入時，將其添加到內(nèi)存中的平衡數(shù)數(shù)據(jù)結(jié)構(gòu)（內(nèi)存表）中。

2. 當內(nèi)存表大于某個閥值時，將其作為SSTable文件寫入磁盤。

3. 為了處理請求，首先在內(nèi)存表查找，然后從最新的依次查找段文件。

4. 后臺進程周期性執(zhí)行段文件合并與壓縮，并丟棄已經(jīng)覆蓋或刪除的值。

從SSTablesdao LSM-Tree(日志結(jié)構(gòu)的合并樹)

LSM-Tree：基于合并與壓縮排序文件的原理的存儲引擎統(tǒng)稱。

# 最廣泛使用的存儲引擎-B-tree

> 日志結(jié)構(gòu)索引將數(shù)據(jù)庫分解為可變大小的段，通常大小為幾兆或更大，并且要求順序?qū)懭攵?。而，B-tree將數(shù)據(jù)庫分解為固定大小的塊或頁，每個也可以使用一個地址標識，傳統(tǒng)大小為4K，頁是操作系統(tǒng)讀寫的最小單元，這種設(shè)計更接近底層。

# 原理：某一頁被指定為B-tree的根；每當查找索引的一個鍵時，總是從這里開始；該頁面包含了若干個鍵和對子頁的引用；每個孩子都負責(zé)一個連續(xù)范圍內(nèi)的鍵，相鄰引用之間的鍵可以指示這些范圍之間的邊界。

為了保證數(shù)據(jù)庫能從崩潰中恢復(fù)，B-tree增加了預(yù)寫日志（WAL：write-ahead log），這是一個僅支持追加修改的文件，每個B-tree的修改必須先更新WAL然后再修改樹本身的頁。