1

欢迎笑寒回到课堂我们直接切入主题：从零开始构建一个数据库。这听起来可能有点像在玩乐高，但实际上，它能帮助我们彻底理解数据库是如何工作的。今天，我们将聚焦于三个核心概念：持久性、索引和并发。这本书的核心思想很简单：数据库不是黑盒子，我们可以通过亲手构建一个来理解它。我们不会追求一个复杂到令人望而却步的实现，而是通过一个最小化的、逐步构建的版本来学习。从基础的B-Tree开始，逐步构建一个简单的键值存储，最终目标是实现一个迷你版的关系型数据库。重点在于理解那些重要的设计思想，而不是陷入具体的实现细节。因为真实世界的数据库太复杂了，反而更容易让人迷失。通过这种方式，我们能更快、更深刻地掌握核心原理。这本书大致分为两大部分。第一部分是构建一个简单的键值存储，我们会从最基础的文件与数据库的比较开始，然后深入探讨索引，特别是B-树的原理和实现。接着，我们会学习如何将数据持久化到磁盘，并引入页回收机制。第二部分则会更进一步，构建一个迷你关系型数据库，涉及行、列、范围查询、二级索引、原子事务、并发控制以及简单的查询语言解析和执行。整个过程是循序渐进的，每个章节都是在前一个基础上的扩展。我们这本书的核心内容，可以概括为三个关键词：持久性、索引和并发。持久性，就是确保数据不丢失、不损坏，即使系统崩溃也能恢复。想象一下，如果一个关键的交易记录因为一次意外关机就丢失了，后果不堪设想。索引，是让数据查找变得飞快的关键。没有索引，查找数据就像大海捞针，效率低下。我们主要会用B-树来实现这个功能。并发，是处理多用户同时访问数据库的能力。现代应用几乎不可能是单线程的，数据库必须能同时服务多个客户端，甚至还要保证读写操作的原子性。如果你对这些概念还只是停留在数据库存数据、索引很快这种模糊认识，那这本书非常适合你。这本书的使用方法也很直接。它采用的是步步为营的方式，每个章节都是在前一个章节的基础上增加新的概念或功能。代码示例是用Golang写的，但别担心，我们讨论的原理和数据结构是通用的，不局限于任何特定语言。最重要的，也是我强烈建议大家做的，就是不要光看，要动手！尝试自己编写代码，跟着我们一起走一遍这个构建过程。这不仅能加深理解，还能让你真正掌握这些知识。所有章节的草稿都可以在官网找到。我们来看第一个核心主题：持久性。为什么我们需要数据库，而不是直接把数据写到文件里？很简单，想想看，如果一个进程正在写入一个文件，突然崩溃了，或者更糟，断电了，这个文件会变成什么样？最坏的情况可能是文件损坏，数据丢失，甚至变成一堆乱码。你辛辛苦苦写入的数据，可能因为一次意外就付诸东流。这就是数据库要解决的问题：它必须保证数据在意外发生后能够恢复到一个可用的状态。当然，对于非常小的数据集，你可以尝试用一种更简单的方法：先写到一个临时文件，然后同步到磁盘，最后用原子操作重命名覆盖旧文件。但这在数据量大时就不可行了。第二个主题：索引。数据库查询大致可以分为两种：OLAP（分析型）和OLTP（事务型）。OLAP通常处理大量数据，做复杂的聚合、分组、连接等操作，比如生成报表。而OLTP，我们日常应用中遇到的更多，比如电商下单、银行转账，这类操作通常只涉及少量数据，而且需要快速响应。我们这本书主要关注的是OLTP，也就是如何快速找到数据。如果数据量很大，每次都全盘扫描，那效率肯定不行。所以，我们需要索引，一种存储在磁盘上的数据结构，它能帮助我们快速定位数据，比如B-Tree或LSM-Tree。记住，如果数据能装进内存，那问题就简单了，但如果数据量巨大，就必须靠索引。第三个主题是并发。现在的应用，谁还是一条道走到黑呢？数据库也一样，必须能处理多用户同时访问。并发涉及到多个方面：比如多个用户同时读取同一个数据，或者读写操作同时发生，甚至还有写操作之间如何协调。即使是像SQLite这样的文件数据库，也支持一定的并发，但通常不如数据库服务器内部进程管理的并发控制来得高效。更重要的是，当并发出现时，我们常常需要保证操作的原子性，比如先读取一个值，然后修改它，再写回，这整个过程要么全部成功，要么全部失败。这就是事务的概念，它为数据库带来了强大的数据一致性保障。好了，我们进入第一部分：构建一个简单的KV存储。首先，我们从最基础的问题开始：文件 vs.数据库。很多人可能会想，写个文件不就完了？简单直接。但事实远非如此。直接写文件，看似简单，但背后隐藏着不少坑。这是最典型的文件写入方式：打开文件，截断，然后写入新数据。看起来没问题，但仔细想想，问题来了。第一，它会截断文件，如果同时有其他进程在读取，那读取到的就是旧数据，或者干脆读不到任何数据。第二，文件写入本身可能不是原子操作，特别是写入大块数据时，操作系统可能分多次写入，导致读取进程看到的是不完整的数据。第三，也是最隐蔽的，write系统调用返回了，不代表数据真的写到硬盘上了。操作系统可能还在缓存里，万一系统崩溃，数据可能就丢失了。这三点，就是直接用文件存储数据的致命弱点。为了解决写入非原子性的问题，有人想出了一个更聪明的办法：先写到一个临时文件，等写完，再用原子操作重命名，把临时文件变成目标文件。这样，即使系统崩溃，原来的文件也还在，读取进程不会受影响。听起来不错，但问题依然存在。数据什么时候写入磁盘？我们还是不知道。更糟糕的是，文件的元数据，比如文件大小，可能会先于实际数据写入磁盘。如果系统崩溃，就可能在文件里留下一堆乱七八糟的零，这就是文件损坏。所以，这个方法虽然比直接写入文件好，但还不够完美。要解决数据写入时机的问题，我们需要一个强制同步的命令：fsync。在重命名之前，先对文件调用fsync，强制操作系统把缓冲区里的数据刷到磁盘上。这样，我们就能确保数据在重命名前是安全的。但是，问题还没完。文件的元数据，比如文件名、权限、修改时间，这些也需要同步到磁盘吗？如果文件在一个目录里，这个目录的元数据也需要同步吗？这一连串的问题，把我们带入了一个很深的兔子洞。你看，仅仅是文件持久化，就有这么多细节要考虑。这就是为什么数据库，作为一个专门设计的系统，比直接操作文件更可靠、更高效。还有一种方法，叫做仅追加日志。顾名思义，就是只往文件里追加数据，不修改已有的数据。这种方式的好处是，它不需要复杂的重命名操作，也不容易损坏，因为数据总是写在最后面。但是，它的缺点也很明显：查询效率极低，只能从头到尾读一遍，才能找到需要的数据。而且，数据也不能无限增长，总得想办法处理删除和过期的数据。所以，虽然日志在某些场景下有用，但它本身并不能构成一个完整的数据库。我们需要更强大的工具，比如索引。我们进入第二部分：索引。关系型数据库支持各种查询，但如果我们把它们拆解成对磁盘的操作，其实可以归结为三种：全表扫描，也就是没有索引时的暴力搜索；点查询，根据一个特定的键查找；还有范围查询，比如查找某个区间内的所有数据。索引的核心作用，就是加速这两种查询。点查询和范围查询，本质上都是在有序的数据上查找。如果我们能构建一个支持有序查找的索引结构，就能轻松实现KV存储。而关系型数据库，其实也可以在KV存储的基础上，通过添加行、列、约束等特性来构建。在设计KV存储时，我们首先会想到哈希表，毕竟它查找速度快，平均时间复杂度是O(1)。但是，对于通用的KV存储，哈希表有个致命的缺点：它不支持排序。很多应用场景，比如时间序列数据，或者需要按某种顺序访问的数据，哈希表就无能为力了。当然，哈希表在某些专用场景下是可用的，比如缓存。但哈希表的扩容问题也很麻烦。简单粗暴的扩容是O(n)，会导致磁盘空间和IO突然飙升，性能急剧下降。而且，哈希表通常不会自动缩小，即使数据量减少，也会浪费大量空间。所以，对于需要排序和动态调整大小的场景，哈希表不是最佳选择。这就是我们接下来要重点介绍的B-树。它是一种平衡的n-叉树，而不是二叉树。为什么要用n叉而不是二叉？好处多多。首先，空间利用率更高。二叉树的每个节点通常需要两个指针，而B-树的节点可以包含多个键和多个指针，平均下来每个节点的指针数量更少。其次，磁盘IO更少。B-树的树高通常比二叉树矮，这意味着查找时需要的磁盘寻道次数更少。而且，由于磁盘最小读写单位通常是页，通常4KB，B-树的节点大小可以设计成至少一个页，这样就能充分利用每次读写的带宽。最后，在内存中，由于CPU缓存和现代硬件的特性，n-叉树的访问速度也可能比二叉树更快。这三点使得B-树成为磁盘存储场景下非常理想的索引结构。除了B-树，还有一种非常流行的索引结构，叫做LSM-Tree，日志结构合并树。它的思路是：先写入一个内存中的日志，然后定期将这些日志合并到磁盘上的一个有序结构中。最简单的版本是用两个文件：一个写入速度很快的内存文件，用来接收最近的更新，另一个是磁盘上的大文件，存储历史数据。更新时，先写入内存文件，满了之后，再合并到大文件。查询时，先查内存文件，再查大文件。删除操作通常是标记删除，真正删除是在合并时。LSM-Tree的优势在于写入性能非常高，因为大部分写入操作都是追加到内存或小文件，而合并操作可以异步进行，大大降低了写入放大。当然，它也有缺点，比如查询性能可能不如B-树，因为需要查找多个文件，而且合并操作会增加额外的写入。实际的数据库，比如LevelDB、RocksDB等，通常会采用多层的LSM结构，进一步优化性能，但也会在写入放大和查询性能之间进行权衡。