數據庫內核揭秘：存儲引擎的設計與實現

林金河，開源技術愛好者，從事分佈式數據庫的開發工作，深度參與過多個大規模分佈式數據庫系統的設計和開發。

目    錄

 

第1章  概述 1

1.1  數據庫與數據庫管理系統 1

1.2  為什麽需要數據庫管理系統 2

1.3  數據模型 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  固態硬盤 23

2.5  文件系統接口 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  數據壓縮和編碼 44

3.4.1  通用壓縮算法 44

3.4.2  游程編碼 44

3.4.3  位壓縮和參考框架 45

3.4.4  前綴壓縮 46

3.4.5  字典編碼 47

3.4.6  快速靜態符號表 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  優化 65

4.5.1  多緩沖池優化 66

4.5.2  預讀取 66

4.5.3  緩沖池旁路 66

4.5.4  隔離緩存污染 66

4.5.5  掃描共享 67

第5章  索引結構：哈希表 68

5.1  基本原理 68

5.2  哈希函數 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  優化分析 80

5.6  Hopscotch Hashing 81

5.6.1  插入操作 81

5.6.2  查找操作 83

5.6.3  刪除操作 83

5.6.4  優化分析 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  觸發時機 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  並發控制 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章  並發控制 206

9.1  事務 206

9.1.1  事務的沖突 208

9.1.2  事務的異常 208

9.1.3  隔離級別 210

9.2  並發控制算法 211

9.3  多版本並發控制 212

9.4  基於鎖的並發控制算法 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  熱點優化 218

9.5  基於時間戳順序的並發控制算法 221

9.5.1  基礎T/O算法 221

9.5.2  托馬斯寫入規則 222

9.6  樂觀並發控制算法 223

9.6.1  算法原理 223

9.6.2  可序列化的充分條件 224

9.6.3  串行驗證之向後驗證 226

9.6.4  串行驗證之向前驗證 226

9.6.5  並行驗證 227

9.7  基於有向序列化圖的並發控制算法 228

9.7.1  有向序列化圖 228

9.7.2  序列化快照隔離 229

9.7.3  並發控制算法小結 230

9.8  多版本記錄的存儲方式 231

9.8.1  追加寫存儲 232

9.8.2  時間穿梭存儲 232

9.8.3  增量存儲 233

9.9  多版本記錄的過期回收 233

9.10  多版本數據的索引管理 234