内容简介
《数据库内核揭秘:存储引擎的设计与实现》深入探讨数据库存储引擎内部机制，详细阐述存储引擎在数据管理中的核心作用，包括数据的存储、检索和管理方式。
《数据库内核揭秘:存储引擎的设计与实现》共分为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 搜
前言/序言
为什么要写本书
在网络上，打开搜索引擎，我们可以找到大量关于数据库存储引擎的资料和图书，其内容大致可分为两大类。
第一类侧重于架构层面的探讨。这类资料通常从宏观视角出发，强调“大道理”，但在算法细节方面往往较为简略。尽管这类资料通俗易懂，却难以深入存储引擎的精髓，读者在阅读后可能会感到“知其然，然不知其所以然”，缺乏对核心机制的深刻理解。
第二类是源码分析类资料。根据笔者的了解，这类资料存在两个显著问题：首先，源码版本可能较为陈旧，主要受限于开源软件的更新速度和版本差异。虽然这不一定构成严重障碍，但仍需注意。其次，更为关键的问题是，这类资料的入门门槛较高，涉及的细节繁杂，读者很容易在浩如烟海的细节中迷失方向，难以把握整体脉络，进而陷入被局部细节困扰的泥潭，难以自拔。
当然，这两类资料在学习数据库存储引擎研发的过程中都起到了重要作用，为初学者提供了宝贵的知识和经验。然而，笔者深感在宏观架构与源码分析之间，存在一个知识空白，这正是初学者学习曲线陡峭的根源。因此，笔者坚信，需要一种介于这两者之间的第三类资料，它能够平滑初学者的学习曲线，填补这一知识空白。
这正是笔者决定撰写本书的初衷和主要目标：为读者提供一个既不过于抽象，又不过于烦琐的学习资源。本书将结合宏观架构的清晰概述与源码分析的深入细节，但不会让读者陷入细节的泥潭。通过本书，笔者希望帮助初学者更好地理解存储引擎的核心原理，掌握其设计与实现的关键技术，从而在数据库内核研发的道路上稳步前行。
你能从本书学到什么
本书旨在深入剖析存储引擎的内部机制，并揭示其核心知识。本书共分为9章，其中第1章与第2章作为开篇，为读者搭建起理解的基础框架。第3~9章，我们将按照自底向上的逻辑顺序，逐一探讨存储引擎内部各关键模块的设计理念与实现细节，引领读者逐步深入掌握这一技术领域的精髓。
第1章提供数据库系统的全面概览，聚焦于数据库的使命、数据模型的构建以及功能模块的布局。本章特别强调数据库存储引擎中多个关键模块的作用及其基本工作原理。通过本章的讲解，读者将能够建立对存储引擎内部运作机制的基本理解，为后续章节的学习奠定坚实基础。
第2章深入探讨操作系统和硬件设备（如CPU、内存和硬盘）的基础知识。鉴于数据库系统实质上是一种基础应用软件，操作系统和硬件设备的特性对其设计具有决定性的影响。通过本章的学习，读者将掌握这些关键特性，从而能够在设计存储引擎时，更加高效地利用系统资源，优化性能，进而实现更加精巧和强大的数据库解决方案。
第3章深入探讨存储引擎如何在文件系统的基础上组织和存储数据。本章将重点介绍两种常见的实现方式：页式存储和日志式存储。页式存储将数据划分为固定大小的页，而日志式存储则通过追加写的方式记录数据变更。值得注意的是，这两种实现方式并非完全互斥。实际上，采用日志式存储的存储引擎也可以对数据进行分页管理。通过本章的学习，读者将能够理解这两种存储方式的内在联系，以及它们在实际应用中的灵活运用。
第4章聚焦于缓冲池的重要性及其设计原则。作为内存与硬盘之间的关键接口，缓冲池的性能直接影响系统的整体效率。一个精心设计的缓冲池能够显著减少硬盘I/O操作，从而提升系统的执行速度和响应能力。本章将深入剖析各种缓存替换算法，包括它们的工作原理、优势以及潜在不足。通过对比分析，读者将掌握不同算法在实际应用中的适用场景，为设计高效、稳定的缓冲池提供理论支持和实践指导。
索引作为存储引擎中最关键的数据结构，对提升数据检索效率具有举足轻重的作用。在本书中，我们专门安排了3章内容（第5~8章），分别详细介绍不同的索引结构。这3章将带领读者深入探索各类索引的构建原理、操作机制及优化策略，帮助读者全面理解索引在存储引擎中的核心地位和作用。通过这3章的学习，读者将能够根据实际需求选择和设计最合适的索引结构，从而使数据管理和查询在性能上实现质的飞跃。
第5章深入探讨哈希表这一简单而高效的索引结构，它是存储引擎中最常见的数据组织方式之一。本章的核心内容围绕哈希冲突的解决策略展开，详细介绍多种处理方法及其优劣。哈希冲突的处理是设计哈希表的关键，因为它直接影响索引的性能和稳定性。此外，本章还涉及在线再哈希扩容这一重要议题，这是确保哈希表在数据增长时仍能保持高效运行的关键技术。然而，哈希表存在一个明显的局限性：不支持范围查询。换句话说，当需要对数据进行范围检索时，哈希表可能不是最佳选择。尽管如此，哈希表在等值查询等场景中仍展现出无可比拟的优势。通过本章的学习，读者将全面掌握哈希表的设计原理和应用技巧，为在实际项目中选择和优化索引结构提供有力支持。
第6章聚焦于LSM树（Log-Structured Merge-Tree），这是一种近年来备受瞩目的存储引擎通用索引结构。LSM树的特点是：
