作為后端程序員，選擇合適的數(shù)據(jù)庫與存儲引擎弯淘，對于數(shù)據(jù)庫與引擎進行調優(yōu)是基本的素養(yǎng)倾哺。
針對事務處理和針對分析的存儲引擎優(yōu)化具有較大的差異令宿。
存儲引擎包含兩個大的家族：日志結構的存儲引擎和面向頁的存儲引擎楣号。
數(shù)據(jù)庫核心：數(shù)據(jù)結構
首先通過bash腳本配合追加以及grep等操作最易，構建一個基本的鍵值型數(shù)據(jù)庫，而用于存儲追加數(shù)據(jù)的文件就是日志竖席，日志指僅支持追加式更新的文件耘纱。
如果一個日志中保存了大量的數(shù)據(jù)敬肚，每次查找時的全文掃描效率即為低下毕荐，因此需要新的數(shù)據(jù)結構：索引，索引能夠提升查詢的性能艳馒，但會降低寫的性能憎亚。
哈希索引
鍵/值數(shù)據(jù)通吃笨埽可采用哈希表等作為索引，哈希表可以保存于內存中第美，可以利用內存中的哈希表對于磁盤中的數(shù)據(jù)進行索引蝶锋，也就是哈希索引。
Bitcask通過磁盤上的僅追加文件（日志）進行數(shù)據(jù)記錄什往，利用內存中的哈希表記錄數(shù)據(jù)的偏移量扳缕，新寫入的數(shù)據(jù)追加至日志文件中，利用哈希表記錄該記錄在文件中的偏移别威。Bitcask非常適合執(zhí)行多寫操作躯舔，僅追加的方式相比于原地修改能夠大幅提升寫入性能，并且Bitcask具有壓縮功能省古，使得較早的重復記錄被覆蓋粥庄。
Bitcask還需要考慮一些其他問題：
- 文件格式：應用二進制格式相比CSV有更好的效率
- 刪除記錄：利用墓碑節(jié)點即可
- 崩潰恢復：重啟后重新讀取日志文件恢復哈希表
- 部分寫入記錄：添加校驗碼，隨時刪除損毀的部分
- 并發(fā)控制：只采用一個寫入進程
Bitcask的局限性：
- 哈希表體積：哈希表放置于內存時性能較好豺妓，若放置于磁盤則性能十分糟糕惜互，因此哈希表性能十分受限于內存容量
- 區(qū)間查詢效率：哈希表注定區(qū)間查詢效率不行
SSTables和LSM-Tree
在Bitcask中鍵/值對無需排序，且同一文件中可能存在相同的鍵琳拭。
SSTables則要求每個鍵/值對的鍵在其所處的段文件中只出現(xiàn)一次训堆，并且每個段文件中所有鍵/值對按照鍵的順序排列，SSTables相比于Bitcask具有以下優(yōu)點：
段文件的合并更加高效：各個段文件可通過歸并的方式高效合并
無需存儲所有鍵的索引：只需要少量索引配合二分查找就可以高效查詢
易于壓縮：各個塊在寫入磁盤之前可以壓縮白嘁，減少文件體積和I/O帶寬占用
構建和維護SSTables
SSTables相比于Bitcask需要維護排序結構蔫慧，而如果為了維護排序結構頻繁讀寫磁盤顯然不合理，因此排序結構被保存在內存中权薯，可通過紅黑樹姑躲、AVL、跳表等方式實現(xiàn)盟蚣，通常其工作流程如下：
1. 在寫入（增刪改）時黍析，將新的數(shù)據(jù)添加到內存中的跳表，稱之為**內存表**
2. 當內存表大于某個固定閾值后屎开，將其形成**SSTables**并寫入磁盤阐枣，寫入舊的內存表后，建立一個新的內存表
3. 在查找時奄抽，先行查找內存表蔼两，再查找最近的SSTables，接下來是次新的逞度，以此類推
4. 后臺周期執(zhí)行SSTables的合并與壓縮
除此之外额划，還需要防止程序崩潰導致的內存表丟失問題，通常采用預寫日志（Work Ahead Log）
從SSTables到LSM-Tree
基于以上邏輯档泽，就構成了日志結構合并樹（Log-Structure Merge Tree）的出行俊戳，被應用于LevelDB揖赴、RocksDB等數(shù)據(jù)庫。
性能優(yōu)化
查找LSM-Tree中不存在的鍵可能造成大量的讀取抑胎，采用布隆過濾器進行優(yōu)化
設計合理的壓縮與合并策略燥滑，將SSTables分層并設定為不同的大小，設計基于體積或訪問落空次數(shù)的合并策略
LSM-Tree的魅力在于保存遠大于內存的數(shù)據(jù)阿逃，犧牲較少的讀取性能獲得較大的寫入性能
B-tree
Bitcask和LSM-Tree都屬于基于日志的索引铭拧，但是B-tree才是最為常見的索引，是關系型數(shù)據(jù)庫的基石恃锉。B-tree是一種基于頁的索引結構羽历，頁通常是磁盤讀寫的最小單元，大小一般為4KB淡喜，每個頁通過地址或者位置進行標識秕磷。
B-tree中某一個頁被指定為B-tree的根，B-tree是一種多路查找樹炼团，除葉子節(jié)點外的每個頁指向多個頁澎嚣，即具有多個子節(jié)點，每個頁包含的引用數(shù)量稱為分支因子瘟芝，對于B-tree中某個項進行查詢易桃，需要遞歸的進行操作，各種查詢的時間復雜度都為對數(shù)時間復雜度锌俱。
是B-tree可靠
由于B-tree中插入導致的頁溢出等問題晤郑，同樣需要機制保證數(shù)據(jù)庫能夠從崩潰中恢復，常見的方式為預寫日志即WAL贸宏。
除此之外B-tree具有并發(fā)問題造寝，需要通過鎖等手段進行控制
優(yōu)化B-tree
典型措施如：
- 保存鍵的縮略信息，節(jié)省頁空間吭练，使得分支因子增加诫龙，從而減少樹的層數(shù)
- 嘗試將相鄰葉子的頁面在磁盤上順序保存
- 對于葉子節(jié)點，添加前后的引用鲫咽，增加范圍性能
- 運用寫時復制
對比B-tree和LSM-tree
總體來看签赃，通常認為B-tree適合讀而LSM-tree適合寫
LSM-tree的優(yōu)點
B-tree寫入至少包括兩次：對日志寫入，對樹中頁的寫入分尸，即便是少量內容修改也需要對于整個塊進行覆蓋锦聊，具有較大的寫放大，寫放大指一次寫請求引發(fā)磁盤的內部多次寫入的現(xiàn)象箩绍，對于寫密集應用孔庭，性能瓶頸很可能在于寫入速率，可以認為LSM-tree相比B-tree寫放大更辛嫜 （本人對此處存疑）史飞，這對于寫入效率和磁盤壽命都有好處尖昏。
LSM-tree更易于壓縮仰税，LSM-tree不是面向頁以及定期重寫的特性適合進行壓縮构资。
LSM-tree的缺點
壓縮占用磁盤帶寬的問題
B-tree面向頁的特性使得其很適合事務
其他索引結構
以上只討論了鍵/值索引，就像關系模型中的主鍵陨簇，用于標識關系（表）中的一行吐绵。
除開主鍵索引，二級索引也很常見河绽，通過CREATE INDEX命令在某個字段之上建立己单，二級索引可以基于各種鍵/值索引構建，B-tree耙饰，LSM-tree都可以用于二級索引纹笼。
在索引中存儲值
可以將數(shù)據(jù)行直接存儲于索引之中即為聚簇索引，在InnoDB中主鍵采用聚簇索引苟跪，而二級索引引用主鍵即為非聚簇索引廷痘。
聚簇索引和非聚簇索引具有一個折中——覆蓋索引，支持在索引中只保存部分列的信息件已。
增加索引雖然可以提升查詢效率笋额，但是增大了寫入開銷，并且事務更難實現(xiàn)篷扩。
多列索引
通過多個列進行排序的聯(lián)合索引
適用于地理空間等特殊數(shù)據(jù)的多維索引
全文搜索和模糊索引
并非所有的查詢都有確切的數(shù)據(jù)兄猩，對于搜索引擎等需要模糊的搜索
在內存中保存所有內容
Memcached、Redis等內存中的鍵/值存儲可以作為緩存鉴未，提升效率枢冤。
事務處理與分析處理
以上所說的索引技術通常面向博客、游戲铜秆、電商的事務處理掏导，該模式通常稱為在線事務處理（online transaction processing, OLTP），而對于企業(yè)用戶可能會有數(shù)據(jù)分析的需求羽峰，改模式稱為在線分析處理（online analystic processing, OLAP）,相比之下OLAP具有數(shù)據(jù)規(guī)模大趟咆，對大量數(shù)據(jù)進行匯總，訪問頻率較低等特點梅屉，因此通常應用特別的數(shù)據(jù)系統(tǒng)進行分析工作值纱，這個數(shù)據(jù)系統(tǒng)稱為數(shù)據(jù)倉庫。
數(shù)據(jù)倉庫
一般來說讓數(shù)據(jù)分析人員在OLTP數(shù)據(jù)庫中進行分析通常并不合適坯汤，需要單獨的數(shù)據(jù)倉庫
OLTP數(shù)據(jù)庫與數(shù)據(jù)倉庫之間的差異
數(shù)據(jù)倉庫和OLTP都往往采用SQL進行查詢虐唠，而SQL只是聲明式的查詢，數(shù)據(jù)倉庫和OLTP區(qū)別在于對于SQL的優(yōu)化差別很大
星型與雪花性分析模式
OLAP中通常具有一個非常龐大的事實表惰聂，保存了海量記錄疆偿，可能具有幾百個字段咱筛，圍繞事實表還有許多維度表，事實表中的列可能引用維度表中的外鍵杆故。
事實表周圍圍繞維度表構成了星型分析模式迅箩，如果維度表還具有維度表，那么就形成了雪花型分析模式处铛。
列式存儲
在OLTP數(shù)據(jù)庫中饲趋，通常按照行進行存儲，而由于OLAP的諸多特性撤蟆，OLAP將每列中的所有值存儲在一起奕塑，稱為列式存儲。
列壓縮
由于某個列中可能有上千萬條數(shù)據(jù)家肯，但數(shù)據(jù)取值只有固定幾種情況龄砰，因此可以進行壓縮，如果某列有n種取值共計m行讨衣，其基本流程如下：
- 對n種取值作one hot處理换棚，將一個列拆分為n個列
- 每個列用長度為m的bitmap，形成了共計n個bitmap
- 采用游程編碼壓縮每個bitmap
內存帶寬與矢量化處理
涉及到cache值依、亂序執(zhí)行等問題
列存儲中的排序
如果只是排序單獨的一列沒有意義圃泡，必須關聯(lián)好所有行才有意義。
OLAP應用可以指定多個列進行排列愿险，類似于聯(lián)合索引颇蜡。
排序好的列可以極大的提升壓縮（游程編碼）的效率
幾種不同的排序
對于同一個表，可以存儲多種排序方式形成的表辆亏，相當于具有多種二級索引风秤，可以提升處理效率。
列存儲的寫操作
直接對于壓縮的列進行寫入是不可能的扮叨，通常借助于LSM-tree的思想缤弦，先將所有的寫入添加至內存盹兢，并將其添加到列存儲中茂浮，此時執(zhí)行查詢需要結合列數(shù)據(jù)和內存最近的寫入。
聚合：數(shù)據(jù)立方體與物化視圖
OLAP應用中可能設計到大量的聚合操作激涤，如COUNT衷蜓，SUM累提、AVG、MIN等磁浇，因此可以對于常見的計數(shù)總和進行緩存斋陪，常見的一種方式為物化視圖。物化視圖還有一種特殊方式為數(shù)據(jù)立方體，在特定的維度上存儲聚合數(shù)據(jù)无虚。
小結
本章討論遵循以下邏輯進行：
- 面向事務處理（OLTP）
- 面向日志結構
- 哈希索引與Bitcask
- SSTables與LSM-Tree
- 面向頁
- B-Tree
- 面向日志結構
- 面向分析處理（OLAP）
- 列存儲
