全书分为3篇：1.第1篇首先会详细讲解存储引擎的全貌，让读者能对存储引擎有一个整体的思维框架，介绍存储引擎的两大分支：基于b+树的存储引擎、基于lsm派系的存储引擎，其次对存储引擎部分涉及的一些数据结构、存储介质等概念做一个简要的介绍，为后面内容的深入学习做铺垫。2.第二篇主要介绍基于b+树的存储引擎，在理论部分重点回答为什么选择b+树做存储引擎索引结构、b+树存储引擎解决哪些问题以及如何解决。在实践部分选择开源社区中比较有名的boltdb存储引擎项目来讲解其内部核心源码的实现细节。3.第三篇主要介绍基于lsm派系的存储引擎，理论部分重点介绍lsm tree中各组件的功能及作用，并在此基础上扩展介绍其他几类lsm派系存储引擎的实现思路，帮助读者开阔视野，实践部分分别以bitcask、moss、leveldb等开源项目的核心源码来展开，介绍其内部实现细节。通过阅读本书，读者不仅能对存储引擎，尤其是单机的存储引擎有一个整体的框架，而且能对两类存储引擎的实现思路及背后原理有个深刻的掌握，只有深刻理解了存储引擎的背后实现原理，读者不仅可以自己动手开发自己的存储引擎，更可以很快掌握关系型数据库或者NoSql这类组件的核心原理，对未来实际应用与开发提供参考。

1.实战积淀，资深工程师倾囊相授：本书由互联网大厂资深工程师撰写，凝聚其多年一线实践经验，为读者提供了宝贵的存储引擎底层原理与实战攻略，助力高效掌握关键技术，从容解决业务挑战。2.问题导向，深度揭秘存储引擎：作者创新采用问题引导式教学法，通过一系列精心设计的问题逐步揭示存储引擎的奥秘，包括存储引擎特性、高频数据结构及存储介质等方面内容，让读者轻松理解并深化记忆。3.两大主流引擎深度解析：书中详尽阐述了B+树和LSM派系存储引擎的宏观原理与微观设计，辅以主流源码实现解读，让您既能把握整体架构，又能洞悉细微之处，全面提升对存储引擎的认知水平。4.理论联系实际，案例丰富：全书结合实际应用场景，以BoltDB和LevelDB为实例，细致剖析存储引擎的实际运作机制，无论是初学者还是资深开发者，都能从中获得深刻理解和实战指导。5.业界权威人士鼎力推荐：多位来自腾讯、PingCAP等知名企业的数据库技术专家联袂推荐，一致认为本书对于理解存储引擎原理、提升数据处理与优化能力具有重要价值，是每一位软件开发者及数据库从业者深入研究存储技术的理想读本。

前　　言
为什么要写这本书
在互联网行业中，存储是一个非常重要的领域。所有的互联网应用都离不开数据的存储和检索。然而，存储系统是计算机中非常复杂的一类系统。想掌握它，不仅需要掌握数据结构、算法、操作系统等知识，还要掌握分布式系统相关知识。因此，存储领域的入门门槛较高，对于初学者或者存储爱好者而言并不友好。不幸的是，我也属于存储爱好者这个行列。此外，在日常工作和求职时，存储相关知识的运用和考察占比非常大。如果对存储系统的原理有深入的理解，在工作时能够更好地编写高效的软件，在求职时也将是明显的优势和加分项。
目前业界的存储系统主要包括关系数据库（如MySQL、Oracle等）、NoSQL数据库（如Redis、MongoDB、InfluxDB、OrientDB等）、NewSQL数据库（如TiDB、OceanBase、CockroachDB等），以及消息队列中间件（如Kafka、RocketMQ、Pulsar等）。这些存储系统绝大部分都是分布式系统，它们将多个单机节点有序地组织在一起来提供服务。如果按照模块化的思路进行拆解，这类系统可以分为单机存储组件和分布式组件。单机存储组件主要针对单个实例，关注数据如何高效地存储和检索，主要考虑数据如何组织、索引如何维护、数据如何在磁盘上布局、单机事务如何支持等问题。而分布式组件则更多关注多个实例之间的数据同步、故障发生后的故障自动迁移、数据一致性的保证、数据分片等问题。
虽然不同类型的存储系统有很多差异，但在本质上它们之间存在一些通用的技术点。市场上有几本相关的书籍介绍这些内容，比如Martin Kleppmann所著的《数据密集型应用系统设计》和Alex Petrov所著的《数据库系统内幕》等。此外，还有一些主要介绍关系数据库的书籍，比如Hector Garcia-Molina等人所著的《数据库系统实现》、Abraham Silberschatz等人所著的《数据库系统概念》和Baron Schwartz等人所著的《高性能MySQL》等。对于第一类书籍，我阅读完后发现其广度非常大，每个技术点都介绍到了，但在具体的技术专题上缺乏深度，需要搜罗其他资料进行深入学习；而第二类书籍更多的是从理论上介绍，读者阅读完以后很难直接上手去剖析任何一款数据库的源码。
2020年年底，由于工作需要，我有幸负责了单机嵌入式的KV（键值对）存储引擎的调研工作，随后接触并研究了BoltDB、LevelDB、RocksDB、PebblesDB、Bitcask等项目。在调研过程中我花费了很多的时间和精力，也走了很多弯路。当时在网上搜索了很多资料，但没有解开我内心的困惑。当时想，如果市面上有一本系统地介绍存储引擎的书就好了（比如存储引擎的分类、适用场景、设计上的共通之处及工程实现等），这样的书可以帮助我少走很多探索的弯路。后来偶然的机会接触到了《数据密集型应用系统设计》这本书，一读就被这本书的内容深深地吸引了。我反复读了第3章，每次读完书中对存储引擎简明扼要的介绍时，都有一种豁然开朗的感觉。在后来不断研究的过程中，我对单机的KV存储引擎有了深入的认识和个人理解。其间，我将其作为一个专题在团队内部和外部社区进行了分享，收到了不错的反馈，也有幸帮助到了一些技术小伙伴。
后来我想，像我当初一样，在入门存储时存在各种疑惑的初学者可能有很多。于是我决定尝试动手写一本解开上述疑惑的书，记录研究过程中的一些经验和感悟。于是，有了这本书。本书将给读者一个全新的视角，秉承大道至简的主导思想，聚焦于单机存储引擎本身，重点分析存储引擎如何处理存储和检索，编写上采用理论结合实践的方式，并给出项目源码分析。本书不仅仅是某种技能的分享，更致力于建立方法论，分享个人的一些想法和见解，希望能够抛砖引玉，为读者拓展出更深入、更全面的思路，帮助存储初学者和爱好者知其然并知其所以然。最后，希望本书能够填补存储领域的一些空白。
本书特色
本书主要有三个目标。首先，分析存储引擎和各种存储系统之间的关系，使读者明确存储引擎在存储系统中的位置和角色。其次，给出存储引擎的整体框架和分类，使读者对存储引擎有全面的了解。最后，对于每种存储引擎，主要关注数据的存储和检索过程，解释每类存储引擎背后的设计思想和方案选择，使读者既知其然又知其所以然。
本书在写作上采用了理论结合实践的方式。每一类存储引擎的介绍，分为理论部分和实践部分。理论部分重点介绍设计方案和思想，不仅告诉读者每一类存储引擎能解决什么问题、适用于什么场景，还告诉读者为什么它们能解决这些问题。在介绍设计原理的基础上，配套一个开源项目进行核心源码的分析，帮助读者更深入地理解存储引擎的原理。
本书的目的不是介绍某个项目或技术，而是阐述存储引擎背后通用的设计思想和方法论。我在前人的基础上抽象和整理出来的方法论可以帮助读者更好、更快、更轻松地理解存储引擎，解决存储领域门槛较高的问题。此外，这些设计思想不局限于存储系统，读者在深刻理解后可以在计算机的其他系统中复用。因此，处于不同工作阶段的不同人群可能有不同的阅读感受，读者可以根据需要在不同阶段多次阅读本书。
读者对象
在阅读本书之前，希望读者对计算机基本知识有一个大致的了解，同时具备一定的编程基础，至少熟悉一种编程语言（如C++或Go）等。如果有一些关系数据库或者其他数据库的经验会更好，否则阅读起来可能有些许困难。本书的读者对象主要包括：
数据库架构师。
开发应用架构师。
数据库开发人员。
后端开发人员。
存储、数据库爱好者。
其他计算机从业人员。
如何阅读本书
本书共9章内容，从逻辑上分为三部分。
第一部分为存储引擎基础，一方面对存储引擎进行概述，另一方面介绍存储引擎中高频使用的数据结构和存储介质。这部分包括以下3章内容。
第1章首先对互联网上的各种存储系统进行不同维度的分类，并在此基础上分析其内部数据存储的核心—存储引擎。接着对存储引擎进行分类。本章是提纲挈领的一章。
第2章按照读/写的时间复杂度从低到高的顺序介绍存储引擎中索引高频使用的数据结构。涉及的数据结构包括数组、链表、Hash（哈希）表、位图、布隆过滤器、二叉搜索树、红黑树、跳表、B树、B+树等。
第3章对存储引擎中的存储介质进行介绍，主要包括内存、持久化内存、磁盘等介质。本章内容涉及了大量的操作系统知识，例如虚拟内存、文件系统等。
第二部分为基于B+树的存储引擎，重点讨论处理读多写少场景的B+树存储引擎的相关内容。这部分包括以下3章内容。
第4章从宏观角度分析B+树存储引擎的原理。这一章采用了逐步推导的思路来展开介绍，告诉读者B+树存储引擎背后的方案选型和取舍。
第5章从微观角度介绍B+树存储引擎中的细节。一方面介绍了B+树存储引擎的正常处理流程、边界条件的处理过程、异常情况的应对方案；另一方面介绍了存储引擎中事务的实现方案和多版本并发控制等内容。
第6章以BoltDB存储引擎为例，分析其核心源码实现逻辑。本章是实践内容，通过对BoltDB核心源码的分析，使读者更好地理解B+树存储引擎的内部工作原理。
第三部分为基于LSM派系的存储引擎，主要介绍处理写多读少场景的LSM派系存储引擎的相关内容。这部分包括以下3章内容。
第7章也采用了逐步推导的方式，首先介绍LSM Tree（LSM树）存储引擎的内部原理和演变过程，其次对LSM Tree的几个核心问题（如数据合并、数据分区、放大问题、写放大优化等）进行详细的介绍。
第8章对LSM派系的各类存储引擎（如LSM Tree、LSM Hash、LSM Array、消息队列Kafka等）进行阐述。其中，在介绍LSM Tree时重点对KV分离存储技术WiscKey进行了详细的讲解。
第9章以LevelDB为例，对其核心源码进行剖析。通过前面两章的理论介绍和本章的源码分析，读者可以深入理解LSM Tree存储引擎的原理。
其中，第1章、第4章、第5章、第7章、第8章为本书的重点。如果你没有充足的时间阅读全书，可以选择性地阅读重点章节。
勘误和支持
由于我的水平有限且编写时间紧张，书中难免会出现一些错误或者不准确的地方，恳请读者批评指正。读者可以通过邮箱2282186474@qq.com反馈宝贵的意见和建议，期待与大家在技术交流中互勉共进。
致谢
感谢那些为开源项目做过分享的技术大咖和发表过学术论文的学者，以及各社区和平台上的技术爱好者，尤其是《数据密集型应用系统设计》的作译者。他们的开源和分享对本书的编写起到了至关重要的作用。在编写本书的过程中，我一方面参考了大量相关论文、项目源码和资料，另一方面也参考了一些非常优秀的博客文章。这些资料对我的研究和探索也起到了非常重要的作用。
感谢我的妻子王淑明女士，为写作这本书，我牺牲了很多陪伴她的时间。也感谢我的其他家人，他们的关怀给了我坚持写作的动力。
特别感谢我职业生涯中的导师杨天琳先生，在本书写作之前的方案调研和准备过程中，他给了我很多建议。此外，在日常工作中我们进行过很多次技术讨论和交流，他给了我很多帮助。没有他在技术上的指导，我估计不会有写作本书的计划。
谨以此书献给我最亲爱的家人、朋友，以及为计算机行业做出巨大贡献的大师们。

文小飞

文小飞，在腾讯负责推荐系统后台核心模块研发工作，擅长go语言，熟悉推荐系统后台工作；对网络编程、微服务rpc框架、存储、分布式共识算法(raft)等技术比较感兴趣。

Contents　　目　　录
前言
第1章　存储引擎概述1
1.1　数据存储体系1
1.1.1　OLTP、OLAP与HTAP1
1.1.2　关系数据库、NoSQL数据库与
　　 　NewSQL数据库2
1.1.3　内存型存储组件与磁盘型存储
　　 　组件8
1.1.4　读多写少组件、写多读少组件
　　 　和读多写多组件9
1.1.5　数据存储与检索10
1.2　数据存储的核心：存储引擎10
1.2.1　存储引擎整体架构10
1.2.2　存储引擎的共性问题13
1.3　存储引擎的分类13
1.3.1　读多写少：基于B+树的存储
　　 　引擎14
1.3.2　写多读少：基于LSM派系的
　　 　存储引擎15
1.4　小结17
第2章　索引数据结构18
2.1　基础数据结构18
2.1.1　数组18
2.1.2　链表20
2.2　Hash类数据结构22
2.2.1　Hash表22
2.2.2　位图27
2.2.3　布隆过滤器28
2.3　二叉树类数据结构32
2.3.1　二叉搜索树33
2.3.2　红黑树36
2.3.3　跳表45
2.4　多叉树类数据结构48
2.4.1　B树49
2.4.2　B+树57
2.4.3　其他多叉树61
2.5　小结61
第3章　数据存储介质64
3.1　内存65
3.1.1　内存的基本内容65
3.1.2　内存管理机制69
3.1.3　虚拟内存管理机制80
3.2　持久化内存92
3.3　磁盘96
3.3.1　磁盘的基本内容97
3.3.2　磁盘管理机制102
3.3.3　加速磁盘访问的方案111
3.4　小结112
第4章　从宏观角度理解B+树存储
　引擎的原理113
4.1　B+树存储引擎产生的起点114
4.1.1　诞生的背景114
4.1.2　设计的目标116
4.2　B+树存储引擎方案选型117
4.2.1　数据结构方案对比117
4.2.2　目光转向磁盘118
4.2.3　索引维护和存储121
4.2.4　选择B树还是B+树125
4.3　B+树存储引擎方案选型结果128
4.3.1　方案选型结果128
4.3.2　反向论证130
4.4　小结130
第5章　从微观角度理解B+树存储
　引擎的工程细节132
5.1　边界条件处理132
5.1.1　B+树在磁盘和内存中的映射132
5.1.2　读操作的处理133
5.1.3　写操作的处理137
5.2　异常情况处理154
5.2.1　异常情况总体分析154
5.2.2　数据部分写入的异常处理156
5.3　事务158
5.3.1　事务的基本概念158
5.3.2　并发控制160
5.4　范围查询与全量遍历170
5.5　小结171
第6章　BoltDB核心源码分析172
6.1　BoltDB整体结构172
6.1.1　BoltDB项目结构172
6.1.2　BoltDB整体实现架构173
6.2　page解析175
6.2.1　page基本结构176
6.2.2　元数据页177
6.2.3　空闲列表页179
6.2.4　分支节点页183
6.2.5　叶子节点页186
6.3　node解析187
6.3.1　B+树结构概述187
6.3.2　node结构分析187
6.3.3　node的增删改查189
6.3.4　node分裂190
6.3.5　node合并195
6.4　Bucket解析199
6.4.1　Bucket结构分析199
6.4.2　Bucket遍历的Cursor核心
　结构分析201
6.4.3　Bucket的增删改查206
6.4.4　KV数据的增删改查210
6.4.5　Bucket的分裂和合并211
6.5　Tx解析213
6.5.1　Tx结构分析213
6.5.2　Commit()方法分析214
6.5.3　Rollback()方法分析217
6.6　DB解析219
6.6.1　DB结构分析219
6.6.2　Open()方法分析221
6.6.3　Begin()方法分析224
6.6.4　Update()和View()方法分析226
6.6.5　Batch()方法分析227
6.7　小结229
第7章　深入理解LSM Tree原理232
7.1　LSM Tree的发展背景232
7.2　从零推导LSM Tree234
7.2.1　存储介质的选择234
7.2.2　写请求的处理234
7.2.3　读请求的处理239
7.3　LSM Tree的架构演进240
7.3.1　数据更新分类240
7.3.2　双组件LSM Tree结构241
7.3.3　多组件LSM Tree结构242
7.3.4　实际的LSM Tree结构243
7.4　LSM Tree的核心问题245
7.4.1　数据压缩/合并245
7.4.2　数据分区246
7.4.3　读放大、写放大和空间放大249
7.4.4　写放大优化251
7.5　小结252
第8章　LSM派系存储引擎253
8.1　LSM Tree存储引擎253
8.1.1　LSM Tree工程应用253
8.1.2　LSM Tree的KV分离存储
　技术WiscKey256
8.2　LSM Hash存储引擎264
8.2.1　LSM Hash的起源264
8.2.2　Bitcask的核心原理265
8.3　LSM Array存储引擎269
8.3.1　LSM Array的设计思想269
8.3.2　Moss的核心原理270
8.4　其他LSM存储引擎274
8.4.1　LSM存储引擎扩展274
8.4.2　消息队列Kafka存储引擎275
8.5　小结277
第9章　LevelDB核心源码分析278
9.1　LevelDB概述278
9.1.1　LevelDB整体架构279
9.1.2　LevelDB项目结构280