数据库内核揭秘：存储引擎的设计与实现

第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