數(shù)據(jù)庫(kù)內(nèi)核揭秘：存儲(chǔ)引擎的設(shè)計(jì)與實(shí)現(xiàn)

第1章  概述 1
1.1  數(shù)據(jù)庫(kù)與數(shù)據(jù)庫(kù)管理系統(tǒng) 1
1.2  為什么需要數(shù)據(jù)庫(kù)管理系統(tǒng) 2
1.3  數(shù)據(jù)模型 3
1.4  模塊化 4
1.4.1  計(jì)算引擎 4
1.4.2  存儲(chǔ)引擎 5
第2章  軟件和硬件基礎(chǔ) 7
2.1  多處理器架構(gòu) 7
2.1.1  對(duì)稱多處理器架構(gòu) 7
2.1.2  非對(duì)稱多處理器架構(gòu) 8
2.2  CPU 9
2.2.1  高速緩存 9
2.2.2  流水線 15
2.2.3  SIMD 17
2.3  內(nèi)存管理 18
2.3.1  虛擬內(nèi)存 18
2.3.2  頁(yè)表 19
2.3.3  缺頁(yè) 20
2.3.4  TLB 21
2.4  存儲(chǔ)設(shè)備 21
2.4.1  機(jī)械硬盤 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  小結(jié) 32
第3章  存儲(chǔ)結(jié)構(gòu) 33
3.1  頁(yè)式存儲(chǔ) 33
3.1.1  如何管理文件中的頁(yè) 34
3.1.2  如何管理頁(yè)中的記錄 36
3.2  日志式存儲(chǔ) 38
3.3  行式存儲(chǔ)和列式存儲(chǔ) 40
3.3.1  行式存儲(chǔ) 40
3.3.2  列式存儲(chǔ) 41
3.3.3  行列混合存儲(chǔ) 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)符號(hào)表 47
第4章  緩沖池 49
4.1  內(nèi)存映射 49
4.1.1  接口和原理 49
4.1.2  內(nèi)存映射與緩沖池 50
4.2  緩沖池結(jié)構(gòu) 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  臟頁(yè)落盤的原子性 64
4.4.1  MySQL的雙寫機(jī)制 65
4.4.2  PostgreSQL的整頁(yè)寫入機(jī)制 65
4.5  優(yōu)化 65
4.5.1  多緩沖池優(yōu)化 66
4.5.2  預(yù)讀取 66
4.5.3  緩沖池旁路 66
4.5.4  隔離緩存污染 66
4.5.5  掃描共享 67
第5章  索引結(jié)構(gòu)：哈希表 68
5.1  基本原理 68
5.2  哈希函數(shù) 70
5.3  鏈接法 71
5.4  開放尋址法 72
5.4.1  線性探測(cè) 73
5.4.2  二次探測(cè) 73
5.4.3  雙重哈希 74
5.4.4  刪除操作 75
5.4.5  小結(jié) 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  擴(kuò)容 87
5.8.1  重新哈希 88
5.8.2  線性哈希 88
5.9  完美哈希 92
5.10  總結(jié) 93
第6章  索引結(jié)構(gòu)：LSM樹 94
6.1  基本原理 94
6.2  內(nèi)存表 97
6.3  合并 99
6.3.1  觸發(fā)時(shí)機(jī) 99
6.3.2  分層合并 100
6.3.3  分級(jí)合并 102
6.3.4  組合合并算法 103
6.4  點(diǎn)查詢 103
6.4.1  SST 104
6.4.2  布隆過(guò)濾器 105
6.4.3  布谷鳥過(guò)濾器 107
6.4.4  異或過(guò)濾器 109
6.4.5  帶狀過(guò)濾器 113
6.4.6  總結(jié) 116
6.5  范圍查詢 117
6.5.1  前綴布隆過(guò)濾器 118
6.5.2  SuRF 119
6.5.3  REMIX 124
6.6  鍵值分離 129
6.6.1  如何降低鍵值分離對(duì)查詢性能的影響 130
6.6.2  如何將鍵值分離存儲(chǔ) 131
6.6.3  如何對(duì)已過(guò)期的值進(jìn)行垃圾回收 133
第7章  索引結(jié)構(gòu)：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  樂(lè)觀鎖分支 172
7.3.3  鎖分支方案的問(wèn)題 172
7.4  Blink樹 173
7.4.1  搜索算法 174
7.4.2  插入算法 175
7.4.3  刪除算法 177
7.5  OLFIT樹 177
7.5.1  結(jié)點(diǎn)的無(wú)鎖原子讀取 177
7.5.2  刪除算法 178
7.6  Bw樹 179
7.6.1  整體結(jié)構(gòu) 180
7.6.2  Bw樹的基本結(jié)構(gòu) 181
7.6.3  增量記錄 182
7.6.4  查詢操作 183
7.6.5  結(jié)點(diǎn)分裂 184
7.6.6  結(jié)點(diǎn)合并 186
第8章  故障恢復(fù) 187
8.1  故障類型 188
8.2  影子分頁(yè) 188
8.3  預(yù)寫式日志 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  物理日志和邏輯日志對(duì)比 192
8.4.4  物理-邏輯日志 193
8.5  刷盤策略 193
8.6  檢查點(diǎn) 195
8.7  ARIES 196
8.7.1  日志序列號(hào) 196
8.7.2  事務(wù)提交 197
8.7.3  事務(wù)回滾 198
8.7.4  模糊檢查點(diǎn) 199
8.7.5  恢復(fù) 201
8.8  MARS和WBL 202
8.8.1  MARS 202
8.8.2  WBL 203
8.9  總結(jié) 204
第9章  并發(fā)控制 206
9.1  事務(wù) 206
9.1.1  事務(wù)的沖突 208
9.1.2  事務(wù)的異常 208
9.1.3  隔離級(jí)別 210
9.2  并發(fā)控制算法 211
9.3  多版本并發(fā)控制 212
9.4  基于鎖的并發(fā)控制算法 212
9.4.1  鎖的類型 213
9.4.2  基礎(chǔ)兩階段鎖 213
9.4.3  嚴(yán)格兩階段鎖和強(qiáng)嚴(yán)格兩階段鎖 214
9.4.4  多版本兩階段鎖 215
9.4.5  死鎖處理 215
9.4.6  鎖的粒度 217
9.4.7  熱點(diǎn)優(yōu)化 218
9.5  基于時(shí)間戳順序的并發(fā)控制算法 221
9.5.1  基礎(chǔ)T/O算法 221
9.5.2  托馬斯寫入規(guī)則 222
9.6  樂(lè)觀并發(fā)控制算法 223
9.6.1  算法原理 223
9.6.2  可序列化的充分條件 224
9.6.3  串行驗(yàn)證之向后驗(yàn)證 226
9.6.4  串行驗(yàn)證之向前驗(yàn)證 226
9.6.5  并行驗(yàn)證 227
9.7  基于有向序列化圖的并發(fā)控制算法 228
9.7.1  有向序列化圖 228
9.7.2  序列化快照隔離 229
9.7.3  并發(fā)控制算法小結(jié) 230
9.8  多版本記錄的存儲(chǔ)方式 231
9.8.1  追加寫存儲(chǔ) 232
9.8.2  時(shí)間穿梭存儲(chǔ) 232
9.8.3  增量存儲(chǔ) 233
9.9  多版本記錄的過(guò)期回收 233
9.10  多版本數(shù)據(jù)的索引管理 234