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

\\\"《数据库内核揭秘:存储引擎的设计与实现》深入探讨数据库存储引擎内部机制，详细阐述存储引擎在数据管理中的核心作用，包括数据的存储、检索和管理方式。 《数据库内核揭秘:存储引擎的设计与实现》共分为9章，内容从基础概念到高级技术，逐步深入，旨在为读者提供全面的理解框架。前两章为读者打下坚实的基础，介绍数据库系统的概览以及操作系统和硬件设备的相关知识。接下来的章节按照自底向上的逻辑顺序，深入探讨存储引擎的关键模块。第3章讲解数据在文件系统中的组织和存储方式。第4章聚焦于缓冲池的设计和缓存替换算法。作为存储引擎的核心，索引在本书占据了3章的篇幅（第5~7章），详细介绍哈希表、LSM树和B树家族。第8章讨论数据库系统中的故障恢复问题，重点介绍了ARIES算法及其应用。第9章关注事务的并发控制，包括多种并发控制算法和优化手段，如多版本并发控制（MVCC）。 《数据库内核揭秘:存储引擎的设计与实现》提供了宝贵的理论知识和实践指导，帮助读者掌握构建高性能、高可靠性数据库系统的关键技术。它不仅适合数据库开发者和系统架构师，也适合对存储引擎感兴趣的技术爱好者。\\\"

\"林金河 开源技术爱好者，从事分布式数据库的开发工作，深度参与过多个大规模分布式数据库系统的设计和开发。\"

目 录 第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