翻译自《build your own database from scratch》, 转代码为C++

Introduction

0.1 这本书是关于什么的？

　　数据库不是黑盒。通过从头开始构建自己的来理解它们！本书介绍了一个最小持久性数据库实现。我们从B树开始，然后是一个简单的KV存储，最后是一个小型关系数据库。这本书关注的是重要的想法，而不是实施细节。真实世界的数据库很复杂，很难掌握。我们可以从数据库的分条版本中更快、更容易地学习。“从头开始”的方法迫使你学习得更深。尽管这本书篇幅很短，实施也很少，但它旨在涵盖三个重要主题：

　　1、持久化：如何不丢失或损坏您的数据。从崩溃中恢复。

　　2、索引：高效查询和操作数据。（B-树）。

　　3、并发：如何处理多个（大量）客户端和事务。

　　如果你想理解“数据库如何存储我的数据”或“索引为什么这么快”的话，这本书很适合你。

　　‍

0.2 如何使用这本书？

　　这本书采取了循序渐进的方法。每一步都建立在前一步的基础上，并添加了一个新的概念。本书使用Golang作为示例代码，但主题与语言无关。建议读者编写自己版本的数据库代码，而不仅仅是阅读文本。章节草案可访问官方网站：https://build-your-own.org

0.3 主题一：持久化

　　为什么我们需要数据库？为什么不直接将数据转储到文件中？我们的第一个主题是持久化。

　　假设您的进程在写入文件时中途崩溃，或者您失去了电源，那么文件的状态是什么？

• 文件是否刚刚丢失最后一次写入？
• 或者最终得到一个写了一半的文件？
• 或者最终处于更加糟糕的状态？

　　任何结果都是可能的。当您简单地写入文件时，不能保证您的数据能够持久保存在磁盘上，这是数据库关心的问题。数据库在意外关闭后启动时将恢复到可用状态。

　　我们可以在不使用数据库的情况下实现持久性吗？有一种方法：

1. 将整个更新后的数据集写入一个新文件。
2. 对新文件调用fsync。
3. 通过将新文件重命名为旧文件来覆盖旧文件，这是由文件系统保证的原子性。

　　
只有当数据集很小时，这才是可以接受的。像SQLite这样的数据库可以进行增量更新。

0.4 主题二：索引

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

• 分析型（OLAP）查询通常涉及大量数据，包括聚合、分组或联接操作。
• 相反，事务性（OLTP）查询通常只涉及少量索引数据。最常见的查询类型是索引点查询和索引范围查询。

　　请注意，正如您所知，“transactional”一词与数据库事务无关。计算机术语经常被不同的含义所淹没。本书只关注OLTP技术。虽然许多应用程序不是实时系统，但大多数面向用户的软件应该使用合理数量的资源（内存、IO）在合理（少量）的时间内做出响应。这属于OLTP类别。即使数据集很大，我们如何快速找到数据？（在O（log（n））中），这就是我们需要索引的原因。

　　如果我们忽略持久性方面，并假设数据集适合内存，那么快速找到数据就是数据结构的问题。在数据库系统中，持久存在于磁盘上以查找数据的数据结构称为“索引”。数据库索引可以大于内存。有句话说：如果你的问题符合记忆，那就是一个容易的问题。用于索引的常见数据结构包括B-树和LSM树。

0.5 主题三：并发

　　现代应用程序不只是按顺序执行所有操作，数据库也不一样。有不同的并发级别：

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

　　即使是基于文件的SQLite也支持一些并发性。但在一个进程中并发更容易，这就是为什么大多数数据库系统只能通过“服务器”访问的原因。在并发的情况下，应用程序通常需要以原子方式进行操作，例如读-修改-写操作。这为数据库添加了一个新概念：事务

　　‍