作者：林金河 著
出版社：清华大学出版社
出版日期：2025
ISBN：9787302679363
电子书格式：pdf/epub/txt
网盘下载地址：下载数据库内核揭秘:存储引擎的设计与实现
内容简介
“《数据库内核揭秘:存储引擎的设计与实现》深入探讨数据库存储引擎内部机制，详细阐述存储引擎在数据管理中的核心作用，包括数据的存储、检索和管理方式。
《数据库内核揭秘:存储引擎的设计与实现》共分为9章，内容从基础概念到高级技术，逐步深入，旨在为读者提供全面的理解框架。前两章为读者打下坚实的基础，介绍数据库系统的概览以及操作系统和硬件设备的相关知识。接下来的章节按照自底向上的逻辑顺序，深入探讨存储引擎的关键模块。第3章讲解数据在文件系统中的组织和存储方式。第4章聚焦于缓冲池的设计和缓存替换算法。作为存储引擎的核心，索引在本书占据了3章的篇幅（第5~7章），详细介绍哈希表、LSM树和B树家族。第8章讨论数据库系统中的故障恢复问题，重点介绍了ARIES算法及其应用。第9章关注事务的并发控制，包括多种并发控制算法和优化手段，如多版本并发控制（MVCC）。
《数据库内核揭秘:存储引擎的设计与实现》提供了宝贵的理论知识和实践指导，帮助读者掌握构建高性能、高可靠性数据库系统的关键技术。它不仅适合数据库开发者和系统架构师，也适合对存储引擎感兴趣的技术爱好者。”
作者简介
林金河
开源技术爱好者，从事分布式数据库的开发工作，深度参与过多个大规模分布式数据库系统的设计和开发。
本书特色
《数据库内核揭秘:存储引擎的设计与实现》专注于数据库内核中存储引擎的核心模块，结合作者多年的实践经验，深入浅出地剖析了哈希表、LSM-Tree、B-Tree等多种存储引擎的原理与实现。书中内容不仅注重理论与实际应用的结合，还通过精选案例与代码注释，帮助读者快速理解复杂技术。《数据库内核揭秘:存储引擎的设计与实现》适合中高级开发者、DBA以及数据库内核研发入门者阅读，旨在降低学习门槛、提升实操能力。它不仅是一部不错的技术指南，值得所有数据库从业者深入研读。
目录
第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
前言
为什么要写本书
在网络上，打开搜索引擎，我们可以找到大量关于数据库存储引擎的资料和图书，其内容大致可分为两大类。
第一类侧重于架构层面的探讨。这类资料通常从宏观视角出发，强调“大道理”，但在算法细节方面往往较为简略。尽管这类资料通俗易懂，却难以深入存储引擎的精髓，读者在阅读后可能会感到“知其然，然不知其所以然”，缺乏对核心机制的深刻理解。
第二类是源码分析类资料。根据笔者的了解，这类资料存在两个显著问题：首先，源码版本可能较为陈旧，主要受限于开源软件的更新速度和版本差异。虽然这不一定构成严重障碍，但仍需注意。其次，更为关键的问题是，这类资料的入门门槛较高，涉及的细节繁杂，读者很容易在浩如烟海的细节中迷失方向，难以把握整体脉络，进而陷入被局部细节困扰的泥潭，难以自拔。
当然，这两类资料在学习数据库存储引擎研发的过程中都起到了重要作用，为初学者提供了宝贵的知识和经验。然而，笔者深感在宏观架构与源码分析之间，存在一个知识空白，这正是初学者学习曲线陡峭的根源。因此，笔者坚信，需要一种介于这两者之间的第三类资料，它能够平滑初学者的学习曲线，填补这一知识空白。
