使用Go从零开发一个数据库 说明

(opens new window)

内容简介

数据库并非黑匣子。通过从头开始构建自己的数据库来理解它们！

本专栏详细介绍了一个极简的持久化数据库实现过程。这个实现过程是循序渐进的。我们从B树开始，接着构建一个简单的键值（KV）存储，最终实现一个小型关系型数据库。

本专栏侧重于重要概念，而非实现细节。现实世界中的数据库很复杂，较难理解。从一个简化版的数据库入手，我们能学得更快、更轻松。而且 “从头开始构建” 的方式能让你学得更深入。

虽然本专栏篇幅较短，实现也很精简，但它旨在涵盖三个重要主题：

1. 持久化：如何避免数据丢失或损坏，以及从崩溃中恢复数据。
2. 索引：高效地查询和操作数据（如B树的应用）。
3. 并发：如何处理多个（大量）客户端请求，以及事务处理。

如果你对数据库只有诸如 “数据库用于存储数据” 或 “索引查询速度很快” 这类模糊的概念，那么本专栏很适合你。

如果你缺少项目经验，同时开发语言是Go，那么本专栏特别适合你。

如何使用本专栏？

本专栏采用循序渐进的讲解方式。每一步都建立在前一步的基础上，并引入新的概念。本专栏示例代码使用的是Go语言，但讲解的主题与具体编程语言无关。

建议读者自己动手编写数据库代码，而不只是阅读文本。

本专栏主题

本专栏一共包括三个方面的主题。

主题一：持久化

我们为什么需要数据库呢？为什么不直接把数据写入文件呢？我们的第一个主题就是持久化。

假设在向文件写入数据的过程中，程序崩溃了，或者突然停电了，那么文件会处于什么状态呢？

• 文件仅仅是丢失了最后一次写入的数据吗？
• 还是会变成一个只写了一半的文件？
• 又或者文件会损坏得更严重？

任何结果都有可能发生。当你只是简单地将数据写入文件时，并不能保证数据一定会持久保存在磁盘上。这是数据库需要关注的问题。而且，数据库在意外关机后重新启动时，能够恢复到可用状态。

不使用数据库，我们能实现持久化吗？有办法：

1. 将整个更新后的数据集写入一个新文件。
2. 对新文件调用 fsync 函数（确保数据写入磁盘）。
3. 将新文件重命名为旧文件，覆盖旧文件，文件系统保证这个重命名操作是原子性的。

只有在数据集非常小的情况下，这种方法才可行。像SQLite这样的数据库可以进行增量更新。

主题二：索引

数据库查询主要有两种不同类型：分析型（OLAP）和事务型（OLTP）。

• 分析型（OLAP）查询：通常涉及大量数据，会进行聚合、分组或连接操作。
• 事务型（OLTP）查询：相比之下，这类查询通常只涉及少量有索引的数据。最常见的查询类型是索引点查询和索引范围查询 。

注意，这里的 “事务型（transactional）” 与你可能知道的数据库事务并无关联。计算机术语的含义常常很丰富。本专栏仅关注OLTP技术。

虽然许多应用程序并非实时系统，但大多数面向用户的软件都应该在合理（较短）的时间内响应，并使用合理的资源（内存、输入输出）。这就属于OLTP范畴。即使数据集很大，我们如何快速（时间复杂度为O(log(n))）找到数据呢？这就是我们需要索引的原因。

如果忽略持久化因素，并且假设数据集能全部放入内存，那么快速查找数据就只是数据结构的问题。在数据库系统中，那些持久存储在磁盘上用于查找数据的数据结构被称为 “索引”。而且数据库索引可能比内存还大。有句话说：如果你的问题能在内存中解决，那它就是个简单问题。

常见的索引数据结构包括B树和LSM树。

主题三：并发

现代应用程序不会按部就班地顺序处理所有任务，数据库也是如此。并发存在不同的级别：

• 读操作之间的并发。
• 读操作和写操作之间的并发：写操作是否需要对数据库进行独占访问？

即使是基于文件的SQLite也支持一定程度的并发。但在一个进程内实现并发更容易，这就是为什么大多数数据库系统只能通过 “服务器” 来访问。

随着并发的引入，应用程序通常需要以原子操作的方式执行某些任务，例如 “读取 - 修改 - 写入” 操作。这给数据库带来了一个新概念：事务。

目录

• 引言
• 第一部分：简单键值存储
  1. 文件与数据库
  2. 索引
  3. B树：原理
  4. B树：实践（第一部分）
  5. B树：实践（第二部分）
  6. 持久化到磁盘
  7. 空闲列表：重用页面
• 第二部分：小型关系型数据库 8. 行与列 9. 范围查询 10. 二级索引 11. 原子事务 12. 并发读写 13. 查询语言：解析器 14. 查询语言：执行