深入淺出存儲引擎

Contents　　目　　錄
前言
第1章　存儲引擎概述1
1.1　數(shù)據(jù)存儲體系1
1.1.1　OLTP、OLAP與HTAP1
1.1.2　關系數(shù)據(jù)庫、NoSQL數(shù)據(jù)庫與
　　 　NewSQL數(shù)據(jù)庫2
1.1.3　內(nèi)存型存儲組件與磁盤型存儲
　　 　組件8
1.1.4　讀多寫少組件、寫多讀少組件
　　 　和讀多寫多組件9
1.1.5　數(shù)據(jù)存儲與檢索10
1.2　數(shù)據(jù)存儲的核心：存儲引擎10
1.2.1　存儲引擎整體架構10
1.2.2　存儲引擎的共性問題13
1.3　存儲引擎的分類13
1.3.1　讀多寫少：基于B+樹的存儲
　　 　引擎14
1.3.2　寫多讀少：基于LSM派系的
　　 　存儲引擎15
1.4　小結17
第2章　索引數(shù)據(jù)結構18
2.1　基礎數(shù)據(jù)結構18
2.1.1　數(shù)組18
2.1.2　鏈表20
2.2　Hash類數(shù)據(jù)結構22
2.2.1　Hash表22
2.2.2　位圖27
2.2.3　布隆過濾器28
2.3　二叉樹類數(shù)據(jù)結構32
2.3.1　二叉搜索樹33
2.3.2　紅黑樹36
2.3.3　跳表45
2.4　多叉樹類數(shù)據(jù)結構48
2.4.1　B樹49
2.4.2　B+樹57
2.4.3　其他多叉樹61
2.5　小結61
第3章　數(shù)據(jù)存儲介質(zhì)64
3.1　內(nèi)存65
3.1.1　內(nèi)存的基本內(nèi)容65
3.1.2　內(nèi)存管理機制69
3.1.3　虛擬內(nèi)存管理機制80
3.2　持久化內(nèi)存92
3.3　磁盤96
3.3.1　磁盤的基本內(nèi)容97
3.3.2　磁盤管理機制102
3.3.3　加速磁盤訪問的方案111
3.4　小結112
第4章　從宏觀角度理解B+樹存儲
　引擎的原理113
4.1　B+樹存儲引擎產(chǎn)生的起點114
4.1.1　誕生的背景114
4.1.2　設計的目標116
4.2　B+樹存儲引擎方案選型117
4.2.1　數(shù)據(jù)結構方案對比117
4.2.2　目光轉(zhuǎn)向磁盤118
4.2.3　索引維護和存儲121
4.2.4　選擇B樹還是B+樹125
4.3　B+樹存儲引擎方案選型結果128
4.3.1　方案選型結果128
4.3.2　反向論證130
4.4　小結130
第5章　從微觀角度理解B+樹存儲
　引擎的工程細節(jié)132
5.1　邊界條件處理132
5.1.1　B+樹在磁盤和內(nèi)存中的映射132
5.1.2　讀操作的處理133
5.1.3　寫操作的處理137
5.2　異常情況處理154
5.2.1　異常情況總體分析154
5.2.2　數(shù)據(jù)部分寫入的異常處理156
5.3　事務158
5.3.1　事務的基本概念158
5.3.2　并發(fā)控制160
5.4　范圍查詢與全量遍歷170
5.5　小結171
第6章　BoltDB核心源碼分析172
6.1　BoltDB整體結構172
6.1.1　BoltDB項目結構172
6.1.2　BoltDB整體實現(xiàn)架構173
6.2　page解析175
6.2.1　page基本結構176
6.2.2　元數(shù)據(jù)頁177
6.2.3　空閑列表頁179
6.2.4　分支節(jié)點頁183
6.2.5　葉子節(jié)點頁186
6.3　node解析187
6.3.1　B+樹結構概述187
6.3.2　node結構分析187
6.3.3　node的增刪改查189
6.3.4　node分裂190
6.3.5　node合并195
6.4　Bucket解析199
6.4.1　Bucket結構分析199
6.4.2　Bucket遍歷的Cursor核心
　結構分析201
6.4.3　Bucket的增刪改查206
6.4.4　KV數(shù)據(jù)的增刪改查210
6.4.5　Bucket的分裂和合并211
6.5　Tx解析213
6.5.1　Tx結構分析213
6.5.2　Commit()方法分析214
6.5.3　Rollback()方法分析217
6.6　DB解析219
6.6.1　DB結構分析219
6.6.2　Open()方法分析221
6.6.3　Begin()方法分析224
6.6.4　Update()和View()方法分析226
6.6.5　Batch()方法分析227
6.7　小結229
第7章　深入理解LSM Tree原理232
7.1　LSM Tree的發(fā)展背景232
7.2　從零推導LSM Tree234
7.2.1　存儲介質(zhì)的選擇234
7.2.2　寫請求的處理234
7.2.3　讀請求的處理239
7.3　LSM Tree的架構演進240
7.3.1　數(shù)據(jù)更新分類240
7.3.2　雙組件LSM Tree結構241
7.3.3　多組件LSM Tree結構242
7.3.4　實際的LSM Tree結構243
7.4　LSM Tree的核心問題245
7.4.1　數(shù)據(jù)壓縮/合并245
7.4.2　數(shù)據(jù)分區(qū)246
7.4.3　讀放大、寫放大和空間放大249
7.4.4　寫放大優(yōu)化251
7.5　小結252
第8章　LSM派系存儲引擎253
8.1　LSM Tree存儲引擎253
8.1.1　LSM Tree工程應用253
8.1.2　LSM Tree的KV分離存儲
　技術WiscKey256
8.2　LSM Hash存儲引擎264
8.2.1　LSM Hash的起源264
8.2.2　Bitcask的核心原理265
8.3　LSM Array存儲引擎269
8.3.1　LSM Array的設計思想269
8.3.2　Moss的核心原理270
8.4　其他LSM存儲引擎274
8.4.1　LSM存儲引擎擴展274
8.4.2　消息隊列Kafka存儲引擎275
8.5　小結277
第9章　LevelDB核心源碼分析278
9.1　LevelDB概述278
9.1.1　LevelDB整體架構279
9.1.2　LevelDB項目結構280