數(shù)據(jù)庫內核揭秘：存儲引擎的設計與實現(xiàn)

第1章  概述 1
1.1  數(shù)據(jù)庫與數(shù)據(jù)庫管理系統(tǒng) 1
1.2  為什么需要數(shù)據(jù)庫管理系統(tǒng) 2
1.3  數(shù)據(jù)模型 3
1.4  模塊化 4
1.4.1  計算引擎 4
1.4.2  存儲引擎 5
第2章  軟件和硬件基礎 7
2.1  多處理器架構 7
2.1.1  對稱多處理器架構 7
2.1.2  非對稱多處理器架構 8
2.2  CPU 9
2.2.1  高速緩存 9
2.2.2  流水線 15
2.2.3  SIMD 17
2.3  內存管理 18
2.3.1  虛擬內存 18
2.3.2  頁表 19
2.3.3  缺頁 20
2.3.4  TLB 21
2.4  存儲設備 21
2.4.1  機械硬盤 22
2.4.2  固態(tài)硬盤 23
2.5  文件系統(tǒng)接口 24
2.5.1  緩沖I/O 24
2.5.2  直接I/O和異步I/O 26
2.5.3  io_uring 28
2.5.4  小結 32
第3章  存儲結構 33
3.1  頁式存儲 33
3.1.1  如何管理文件中的頁 34
3.1.2  如何管理頁中的記錄 36
3.2  日志式存儲 38
3.3  行式存儲和列式存儲 40
3.3.1  行式存儲 40
3.3.2  列式存儲 41
3.3.3  行列混合存儲 42
3.4  數(shù)據(jù)壓縮和編碼 44
3.4.1  通用壓縮算法 44
3.4.2  游程編碼 44
3.4.3  位壓縮和參考框架 45
3.4.4  前綴壓縮 46
3.4.5  字典編碼 47
3.4.6  快速靜態(tài)符號表 47
第4章  緩沖池 49
4.1  內存映射 49
4.1.1  接口和原理 49
4.1.2  內存映射與緩沖池 50
4.2  緩沖池結構 52
4.3  緩存替換算法 53
4.3.1  LRU算法 53
4.3.2  FIFO算法和Clock算法 54
4.3.3  LFU算法 57
4.3.4  LRU-K算法 58
4.3.5  LRFU算法 59
4.3.6  LIRS算法 61
4.4  臟頁落盤的原子性 64
4.4.1  MySQL的雙寫機制 65
4.4.2  PostgreSQL的整頁寫入機制 65
4.5  優(yōu)化 65
4.5.1  多緩沖池優(yōu)化 66
4.5.2  預讀取 66
4.5.3  緩沖池旁路 66
4.5.4  隔離緩存污染 66
4.5.5  掃描共享 67
第5章  索引結構：哈希表 68
5.1  基本原理 68
5.2  哈希函數(shù) 70
5.3  鏈接法 71
5.4  開放尋址法 72
5.4.1  線性探測 73
5.4.2  二次探測 73
5.4.3  雙重哈希 74
5.4.4  刪除操作 75
5.4.5  小結 76
5.5  Cuckoo Hashing 77
5.5.1  查找操作 77
5.5.2  刪除操作 78
5.5.3  插入操作 78
5.5.4  優(yōu)化分析 80
5.6  Hopscotch Hashing 81
5.6.1  插入操作 81
5.6.2  查找操作 83
5.6.3  刪除操作 83
5.6.4  優(yōu)化分析 83
5.7  Robin Hood Hashing 83
5.7.1  插入操作 84
5.7.2  刪除操作 86
5.7.3  查找操作 86
5.8  擴容 87
5.8.1  重新哈希 88
5.8.2  線性哈希 88
5.9  完美哈希 92
5.10  總結 93
第6章  索引結構：LSM樹 94
6.1  基本原理 94
6.2  內存表 97
6.3  合并 99
6.3.1  觸發(fā)時機 99
6.3.2  分層合并 100
6.3.3  分級合并 102
6.3.4  組合合并算法 103
6.4  點查詢 103
6.4.1  SST 104
6.4.2  布隆過濾器 105
6.4.3  布谷鳥過濾器 107
6.4.4  異或過濾器 109
6.4.5  帶狀過濾器 113
6.4.6  總結 116
6.5  范圍查詢 117
6.5.1  前綴布隆過濾器 118
6.5.2  SuRF 119
6.5.3  REMIX 124
6.6  鍵值分離 129
6.6.1  如何降低鍵值分離對查詢性能的影響 130
6.6.2  如何將鍵值分離存儲 131
6.6.3  如何對已過期的值進行垃圾回收 133
第7章  索引結構：B樹家族 136
7.1  B樹 136
7.1.1  搜索算法 139
7.1.2  插入算法 140
7.1.3  刪除算法 144
7.2  B 樹 153
7.2.1  搜索算法 154
7.2.2  插入算法 156
7.2.3  刪除算法 161
7.3  并發(fā)控制 170
7.3.1  鎖分支 171
7.3.2  樂觀鎖分支 172
7.3.3  鎖分支方案的問題 172
7.4  Blink樹 173
7.4.1  搜索算法 174
7.4.2  插入算法 175
7.4.3  刪除算法 177
7.5  OLFIT樹 177
7.5.1  結點的無鎖原子讀取 177
7.5.2  刪除算法 178
7.6  Bw樹 179
7.6.1  整體結構 180
7.6.2  Bw樹的基本結構 181
7.6.3  增量記錄 182
7.6.4  查詢操作 183
7.6.5  結點分裂 184
7.6.6  結點合并 186
第8章  故障恢復 187
8.1  故障類型 188
8.2  影子分頁 188
8.3  預寫式日志 190
8.3.1  重做日志 191
8.3.2  回滾日志 191
8.3.3  重做-回滾日志 191
8.4  物理日志和邏輯日志 192
8.4.1  物理日志 192
8.4.2  邏輯日志 192
8.4.3  物理日志和邏輯日志對比 192
8.4.4  物理-邏輯日志 193
8.5  刷盤策略 193
8.6  檢查點 195
8.7  ARIES 196
8.7.1  日志序列號 196
8.7.2  事務提交 197
8.7.3  事務回滾 198
8.7.4  模糊檢查點 199
8.7.5  恢復 201
8.8  MARS和WBL 202
8.8.1  MARS 202
8.8.2  WBL 203
8.9  總結 204
第9章  并發(fā)控制 206
9.1  事務 206
9.1.1  事務的沖突 208
9.1.2  事務的異常 208
9.1.3  隔離級別 210
9.2  并發(fā)控制算法 211
9.3  多版本并發(fā)控制 212
9.4  基于鎖的并發(fā)控制算法 212
9.4.1  鎖的類型 213
9.4.2  基礎兩階段鎖 213
9.4.3  嚴格兩階段鎖和強嚴格兩階段鎖 214
9.4.4  多版本兩階段鎖 215
9.4.5  死鎖處理 215
9.4.6  鎖的粒度 217
9.4.7  熱點優(yōu)化 218
9.5  基于時間戳順序的并發(fā)控制算法 221
9.5.1  基礎T/O算法 221
9.5.2  托馬斯寫入規(guī)則 222
9.6  樂觀并發(fā)控制算法 223
9.6.1  算法原理 223
9.6.2  可序列化的充分條件 224
9.6.3  串行驗證之向后驗證 226
9.6.4  串行驗證之向前驗證 226
9.6.5  并行驗證 227
9.7  基于有向序列化圖的并發(fā)控制算法 228
9.7.1  有向序列化圖 228
9.7.2  序列化快照隔離 229
9.7.3  并發(fā)控制算法小結 230
9.8  多版本記錄的存儲方式 231
9.8.1  追加寫存儲 232
9.8.2  時間穿梭存儲 232
9.8.3  增量存儲 233
9.9  多版本記錄的過期回收 233
9.10  多版本數(shù)據(jù)的索引管理 234