怎么实现一个简单的数据库系统？

想从头开始搭建一个属于自己的数据库系统？听起来有点像个大工程，但别担心，这其实是一个循序渐进的过程。我来跟你好好聊聊，怎么从最基础的概念出发，一点一点地构建一个能用的、简单的数据库系统。这篇文章不会像那些冷冰冰的AI教程，咱们就当是老朋友之间聊技术，把事情说透了。

首先，我们得明确“数据库系统”到底是个啥？

简单来说，它就是一套软件，负责帮你：

1. 存储数据： 把你想要的信息稳妥地放好。
2. 管理数据： 让你能方便地找到、修改、删除这些数据。
3. 保护数据： 确保数据不会丢失、不会被乱改。
4. 提供接口： 让其他程序或者你本人能跟它“对话”。

我们今天要做的是一个“简单”的系统，这意味着我们不会去追求像MySQL、PostgreSQL那样极致的性能、复杂的分布式特性或者事务 ACID 级别的高可靠性。我们要的是理解核心原理，能够实现基本的增删改查（CRUD）功能。

核心组件：我们要搭什么骨架？

一个简单的数据库系统，至少需要几个关键的“零件”：

存储引擎 (Storage Engine): 这是最底层的东西，负责实际的数据读写。你可以把它想象成一个非常“勤劳”的图书管理员，知道书（数据）放在哪个书架（文件）的哪个位置。
查询处理器 (Query Processor): 这是你的“指挥官”。当你发出一个指令（比如“给我找所有年龄大于30的人”），它会解析你的指令，决定怎么去找数据，然后把指令传递给存储引擎。
索引 (Indexes): 这是“加速器”。就像书的目录一样，有了索引，你就能快速找到你想要的数据，而不是从头到尾翻一遍。
事务管理器 (Transaction Manager) （可选，初期可以简化）： 如果你追求更复杂一点的功能，就需要它来管理一系列操作，确保它们要么全部成功，要么全部失败，保持数据的一致性。对于我们这个“简单”系统，初期可以先忽略这个。
并发控制 (Concurrency Control) （可选，初期可以简化）： 当多个用户同时访问数据库时，需要它来协调，避免大家互相干扰。初期我们也可以简化，比如一次只允许一个人操作。

第一步：从存储开始，最原始的“数据保姆”

最简单的存储方式是什么？直接把数据写到文件里。

1. 数据模型：我们怎么“摆放”数据？

关系型数据库（我们最熟悉的）通常使用“表”来组织数据，每个表有“行”（记录）和“列”（字段）。

比如，我们要存储用户信息：

| ID | 姓名 | 年龄 | 城市 |
| : | : | : | : |
| 1 | 张三 | 30 | 北京 |
| 2 | 李四 | 25 | 上海 |

2. 存储格式：文件里的“样子”

简单文本文件 (CSV): 这是最容易想到的。用逗号分隔字段，每行一条记录。
```csv
1,张三,30,北京
2,李四,25,上海
```
优点: 易于理解和生成。
缺点: 查找、修改、删除效率极低。每次都要读整个文件。

固定长度文件: 假设姓名最长10个字符，城市最长8个字符，年龄是数字。
```
001张三 30北京
002李四 25上海
```
优点: 知道偏移量就能直接定位到某一行（如果行数是固定的）。
缺点: 浪费空间（如果实际数据很短），修改长度不一致的字段（比如城市）会很麻烦。

分隔符或定长结合: 比如，ID是定长的4个字节，姓名是变长的，用一个特殊的字符（比如‘’）来分隔。
```
[4字节ID][姓名][4字节年龄][城市]...
```
这种方式开始有点数据库文件的味道了，但依然有很多问题。

更“数据库”一点：页(Page)和记录(Record):
现代数据库内部，数据不是一股脑儿地存在一个大文件里，而是被分成固定大小的“页”（比如 4KB、8KB）。每一页可以存储多条记录。

页结构: 一个页里面，通常会有一个“头部”，记录页的信息（比如有多少条记录，下一页是哪个），然后是实际的记录数据，记录之间可能还有一些指针。
记录结构: 每条记录也需要一个结构，包含字段的数据，以及一些元数据（比如这条记录的长度）。

示例（极简版页结构）：
假设一页是100字节，每条记录包含ID(4字节), 姓名(可变长, 以结尾), 年龄(4字节)。

```
[页头部: 记录数量 = 2, 记录偏移量列表 (指向记录的起始位置)]
[记录1: ID=1, 姓名="张三", 年龄=30] [记录2: ID=2, 姓名="李四", 年龄=25] ...
```
或者更精细一点，记录本身也包含字段长度信息，以便变长字段正确解析。

我们的简单实现思路：
我们可以选择一个相对简单的方式。比如，我们用一个文件来存储所有数据。每一条记录，我们先写上它占用的总字节数，然后是各个字段的数据。字段之间用特殊分隔符，或者我们预先定义好每个字段的最大长度（虽然这不太灵活，但简单）。

举个例子（简单文件存储）：
假设我们只存“ID”、“姓名”、“年龄”三个字段。ID是4字节整数，姓名最多10字节ASCII，年龄是4字节整数。

一个记录就可能是这样：
`[4字节ID][10字节姓名][4字节年龄]`

比如，“张三”, 30岁。
ID: `00 00 00 01` (4 bytes)
姓名: `张三` (假设是UTF8编码，这里为了简单，我们先假设是ASCII，比如"ZhangSan"，长度是8字节。如果用ASCII，不足10字节就用空格填充)。
姓名填充后: `ZhangSan ` (10 bytes)
年龄: `00 00 00 1E` (30 的 4字节表示)

把这些字节连起来，就构成了一条记录。我们把多条这样的记录顺序写到文件里。

第二步：查询处理器——“翻译官”与“指挥家”

现在我们有了文件，需要有人能理解我们的指令，然后去文件里找东西。

1. SQL 语法的简化:
我们就不支持完整的 SQL 了，来一个更简单的“查询语言”。
比如：
`GET ALL`: 获取所有数据。
`GET WHERE <字段> <操作符> <值>`: 根据条件查询。
操作符：`=`, `>`, `<`, `>=`, `<=`, `!=`

2. 查询处理流程：

解析 (Parsing): 把用户输入的查询字符串，比如 `GET WHERE 年龄 > 25`，转换成一个内部能理解的结构。
`Command: GET`
`Condition: { Field: "年龄", Operator: ">", Value: 25 }`

优化 (Optimization): （对我们这个简单系统来说，这步基本省略，或者很简单，比如直接顺序扫描）。

执行 (Execution): 根据解析后的结构，调用存储引擎。

3. 存储引擎的接口：
我们的存储引擎需要提供一些函数：
`open_file(filename)`: 打开数据文件。
`read_record(record_id)`: 读取指定记录（这里record_id可以是文件偏移量，或者一个简单的行号）。
`write_record(data)`: 写入新记录，返回记录ID。
`update_record(record_id, new_data)`: 更新记录。
`delete_record(record_id)`: 删除记录（可以标记为删除，或者实际抹掉）。
`get_all_records()`: 获取所有记录。

4. 实现 `GET WHERE`:
当收到 `GET WHERE 年龄 > 25` 的指令时：
查询处理器会要求存储引擎“给我所有记录”（或者，如果能知道记录的位置，就去逐个读取）。
存储引擎读出一条记录。
查询处理器取出这条记录的“年龄”字段，检查是否大于25。
如果满足条件，就把这条记录返回给用户。
重复直到所有记录都检查完。

第三步：索引——让查找飞起来

直接扫描整个文件太慢了。我们需要索引。

1. 索引的数据结构：
最常见的索引结构是 BTree 或 B+Tree。它们能很高效地在有序数据中查找、插入、删除。

BTree 概念:
它是一种多路平衡查找树。
每个节点可以有多个子节点。
节点中的键（key）是排序的。
查找时，从根节点开始，根据键的大小在节点内选择合适的子节点继续查找，直到找到包含目标键的叶子节点。
叶子节点存储着键值以及指向实际数据记录的指针。

举例（以ID索引为例）：
如果我们对ID建立索引，那么索引会存储 (ID, 记录在文件中的位置)。

假设我们有三条记录：
ID=1, offset=100
ID=2, offset=200
ID=3, offset=300

一个简单的BTree（简化表示）可能长这样：

```
[ 2 ]
/
[ 1 ] [ 3 ]
```
（这里简化成二叉树了，实际BTree一个节点可以存多个键和指针）

当我们要查找 ID=2 的记录时：
从根节点 `[ 2 ]` 开始。
发现要查找的 2 和节点中的 2 相等。
找到指向数据记录的指针（offset=200）。
直接去文件偏移量200的位置读取数据。

2. 索引的维护：
插入: 当你插入一条新记录时，不仅要把数据写入文件，还要在所有相关的索引中也插入新的 (键, 记录位置) 条目。
删除: 删除记录时，不仅要从文件里删除，还要从所有索引中删除对应的条目。
更新: 更新记录时，如果被更新的字段是索引字段，那么索引也需要跟着更新（这比较复杂，可能需要先删除旧的索引条目，再插入新的）。

3. 如何使用索引：
当收到 `GET WHERE ID = 5` 这样的查询时，查询处理器会先查看是否有 ID 索引。
如果有，就使用索引快速找到 ID=5 的记录位置，然后直接去文件读取。
如果查询条件涉及到多个字段，或者没有合适的索引，就可能需要进行全表扫描（扫描所有记录）。

第四步：更进一步（可以先简化或跳过）

数据类型: 我们需要定义字段的数据类型（整数、字符串、布尔值等），并确保存储和读取时正确处理。
并发控制: 如果要允许多个用户同时访问，就需要锁机制。比如，当一个用户在修改一条记录时，其他用户就不能修改它。
事务: 如果需要原子性（allornothing），就需要事务管理器。一个简单的实现可以是：
写前日志 (WriteAhead Logging WAL): 在修改数据之前，先将修改操作记录到一个日志文件中。如果系统崩溃，可以通过回放日志来恢复。
两阶段提交 (2PC): 用于分布式事务，保证多个节点上的操作一致。对于单机简单系统，这过于复杂了。

简单系统可以怎么实现？

1. 语言选择: Python 是个不错的选择，它的字符串处理、文件 I/O、数据结构都比较方便。

2. 存储引擎 (Python 示例思路):

```python
class SimpleStorageEngine:
def __init__(self, filename):
self.filename = filename
记录文件中的偏移量 > (记录ID, 记录实际数据) 的简单映射
实际数据库不会这么简单，可能会用更复杂的数据结构来管理文件
self.records = {}
self.next_id = 1
self._load_data()

def _load_data(self):
try:
with open(self.filename, 'rb') as f:
while True:
假设每条记录的格式是：[4字节ID][N字节数据][ ]
id_bytes = f.read(4)
if not id_bytes: break
record_id = int.from_bytes(id_bytes, 'big')

data_bytes = b''
while True:
char = f.read(1)
if char == b' ': break
data_bytes += char

self.records[record_id] = data_bytes
self.next_id = max(self.next_id, record_id + 1)
except FileNotFoundError:
pass 文件不存在，从空开始

def _save_data(self):
with open(self.filename, 'wb') as f:
for record_id, data in self.records.items():
写入ID，然后是数据，以 结尾
f.write(record_id.to_bytes(4, 'big'))
f.write(data)
f.write(b' ')

def insert(self, data_bytes):
record_id = self.next_id
self.records[record_id] = data_bytes
self.next_id += 1
self._save_data() 每次写入都保存，效率不高，实际数据库会批量或更复杂
return record_id

def get_all(self):
return list(self.records.items()) 返回 (ID, data_bytes) 列表

def get_by_id(self, record_id):
return self.records.get(record_id)

... 其他方法如 update, delete
```

3. 查询处理器 (Python 示例思路):

```python
class QueryProcessor:
def __init__(self, storage_engine):
self.storage_engine = storage_engine

def process_query(self, query_string):
parts = query_string.split()
command = parts[0].upper()

if command == "GET":
if len(parts) == 2 and parts[1].upper() == "ALL":
return self.handle_get_all()
elif len(parts) >= 4 and parts[1].upper() == "WHERE":
假设查询格式是 GET WHERE <字段> <操作符> <值>
这里简化，假设我们只关心ID，并且数据是字符串
field = parts[2]
operator = parts[3]
value = parts[4]

if field.lower() == "id":
try:
target_id = int(value)
if operator == "=":
record_data = self.storage_engine.get_by_id(target_id)
if record_data:
return {target_id: record_data}
else:
return {}
else:
return "Unsupported operator for ID"
except ValueError:
return "Invalid ID value"
else:
return "Only ID filtering is supported in this simple version"
else:
return "Invalid GET query format"
elif command == "INSERT":
假设 INSERT 后面直接跟着数据，比如 INSERT "张三,30"
data_str = " ".join(parts[1:])
实际存储需要将字符串转换为字节，并按预定格式编码
例如，我们存储 "ID姓名年龄"
这里的例子更简单，假设我们直接存储传入的字符串作为value
record_id = self.storage_engine.insert(data_str.encode('utf8'))
return f"Record inserted with ID: {record_id}"
else:
return "Unknown command"

def handle_get_all(self):
all_records = self.storage_engine.get_all()
将字节数据解码成可读格式
decoded_records = {}
for record_id, data_bytes in all_records:
try:
decoded_records[record_id] = data_bytes.decode('utf8')
except UnicodeDecodeError:
decoded_records[record_id] = str(data_bytes) 无法解码就显示原始字节
return decoded_records
```

如何让它看起来不那么AI？

多用“我”、“你”、“咱们”等口语化表达。
多举生活中的例子来比喻抽象的概念。
解释时，可以带入一些“思考过程”或“为什么这样做”的逻辑。
可以提到一些“早期遇到过的问题”或者“曾经想过但最终放弃的方案”。
结构上，可以更像是“聊天”或者“讲故事”，而不是“结构化报告”。

总结一下我们这个简陋的“数据库”能干啥：

把一些数据（字符串）按照ID存进一个文件里。
可以读取所有数据。
可以通过ID精确查找某条数据。
可以插入新的数据，并自动分配ID。

这离一个真正的数据库系统还差很远很远，比如：

数据格式非常固定，不够灵活。 真正的数据库能处理各种数据类型，日期、浮点数、二进制等。
没有索引。 查找是顺序扫描，效率低。
没有查询语言的完整解析。 只能执行非常简单的命令。
没有错误处理、事务、并发控制、安全性等。
存储效率很低。 每次增删改都可能重写整个文件（在上面的Python示例里）。

但是，这已经足够让你体验到数据库的核心流程了：
1. 数据怎么存在文件里。
2. 怎么根据指令去文件里找数据。
3. 为什么需要索引来加速。

要从这个基础上继续完善，你可以考虑：
实现一个简单的BTree索引。
设计更复杂的数据格式，支持多种数据类型。
实现更丰富的查询条件（比如字符串匹配、范围查询）。
考虑如何更高效地写入数据，比如批量写入，或者在内存中缓冲。

一步一步来，先从最简单的“能存进去、能找出来”开始，你会逐渐发现其中的乐趣和挑战。希望这篇“唠叨”般的讲解，能让你对数据库系统有个更直观的理解，而不是只会背那些定义。祝你玩得开心！

自己动手写SQL执行引擎

前言

在阅读了大量关于数据库的资料后，笔者情不自禁产生了一个造数据库轮子的想法。来验证一下自己对于数据库底层原理的掌握是否牢靠。在笔者的github中给这个database起名为Freedom。

整体结构

既然造轮子，那当然得从前端的网络协议交互到后端的文件存储全部给撸一遍。下面是Freedom实现的整体结构，里面包含了实现的大致模块:

最终存储结构当然是使用经典的B+树结构。当然在B+树和文件系统block块之间的转换则通过Buffer(Page) Manager来进行。当然了，为了完成事务，还必须要用WAL协议，其通过Log Manager来操作。
Freedom采用的是索引组织表，通过DruidSQL Parse来将sql翻译为对应的索引操作符进而进行对应的语义操作。

MySQL Protocol结构

client/server之间的交互采用的是MySQL协议，这样很容易就可以和mysql client以及jdbc进行交互了。

query packet

mysql通过3byte的定长包头去进行分包，进而解决tcp流的读取问题。再通过一个sequenceId来再应用层判断packet是否连续。

result set packet

mysql协议部分最复杂的内容是其对于result set的读取，在NIO的方式下加重了复杂性。
Freedom通过设置一系列的读取状态可以比较好的在Netty框架下解决这一问题。

row packet

还有一个较简单的是对row格式进行读取，如上图所示,只需要按部就班的解析即可。

由于协议解析部分较为简单，在这里就不再赘述。

SQL Parse

Freedom采用成熟好用的Druid SQL Parse作为解析器。事实上，解析sql就是将用文本表示
的sql语义表示为一系列操作符(这里限于篇幅原因，仅仅给出select中where过滤的原理)。

对where的处理

例如where后面的谓词就可以表示为一系列的以树状结构组织的SQL表达式，如下图所示:

当access层通过游标提供一系列row后，就可以通过这个树状表达式来过滤出符合where要求的数据。Druid采用了Parse中常用的visitor很方便的处理上面的表达式计算操作。

对join的处理

对join最简单处理方案就是对两张表进行笛卡尔积，然后通过上面的where condition进行过滤，如下图所示:

Freedom对于缩小笛卡尔积的处理

由于Freedom采用的是B+树作为底层存储结构，所以可以通过where谓词来界定B+树scan(搜索)的范围(也即最大搜索key和最小搜索key在B+树种中的位置)。考虑sql

       select a.*,b.* from t_archer as a join t_rider as b where a.id>=3 and a.id<=11 b.id and b.id>=19 b.id<=31     

那么就可以界定出在id这个索引上,a的scan范围为[3,11],如下图所示:

b的scan范围为[19,31],如下图所示(假设两张表数据一样，便于绘图):

scan少了从原来的15*15(一共15个元素)次循环减少到4*4次循环,即循环次数减少到7.1%

当然如果存在join condition的话，那么Freedom在底层cursor递归处理的过程中会预先过滤掉一部分数据，进一步减少上层的过滤。

B+Tree的磁盘结构

leaf磁盘结构

Freedom的B+Tree是存储到磁盘里的。考虑到存储的限制以及不定长的key值，所以会变得非常复杂。Freedom以page为单位来和磁盘进行交互。叶子节点和非叶子节点都由page承载并刷入磁盘。结构如下所示:

一个元组(tuple/item)在一个page中分为定长的ItemPointer和不定长的Item两部分。
其中ItemPointer里面存储了对应item的起始偏移和长度。同时ItemPointer和Item如图所示是向着中心方向进行伸张，这种结构很有效的组织了非定长Item。

leaf和node节点在Page中的不同

虽然leaf和node在page中组织结构一致，但其item包含的项确有区别。由于Freedom采用的是索引组织表，所以对于leaf在聚簇索引(clusterIndex)和二级索引(secondaryIndex)中对item的表示也有区别,如下图所示:

其中在二级索引搜索时通过secondaryIndex通过index-key找到对应的clusterId,再通过
clusterId在clusterIndex中找到对应的row记录。
由于要落盘，所以Freedom在node节点中的item里面写入了index-key对应的pageno,
这样就可以容易的从磁盘恢复所有的索引结构了。

B+Tree在文件中的组织

有了Page结构，我们就可以将数据承载在一个个page大小的内存里面，同时还可以将page刷新到对应的文件里。有了node.item中的pageno，我们就可以较容易的进行文件和内存结构之间的互相映射了。
B+树在磁盘文件中的组织如下图所示:

B+树在内存中相对应的映射结构如下图所示:

文件page和内存page中的内容基本是一致的,除了一些内存page中特有的字段，例如dirty等。

每个索引一个B+树

在Freedom中，每个索引都是一颗B+树，对记录的插入和修改都要对所有的B+树进行操作。

B+Tree的测试

笔者通过一系列测试case,例如随机变长记录对B+树进行插入并落盘，修复了其中若干个非常诡异的corner case。

B+Tree的todo

笔者这里只是完成了最简单的B+树结构，没有给其添加并发修改的锁机制，也没有在B+树做操作的时候记录log来保证B+树在宕机等灾难性情况下的一致性,所以就算完成了这么多的工作量，距离一个高并发高可用的bptree还有非常大的距离。

Meta Data

table的元信息由create table所创建。创建之后会将元信息落盘，以便Freedom在重启的时候加载表信息。每张表的元信息只占用一页的空间，依旧复用page结构，主要保存的是聚簇索引和二级索引的信息。元信息对应的Item如下图所示:

如果想让mybatis可以自动生成关于Freedom的代码，还需实现一些特定的sql来展现Freedom的元信息。这个在笔者另一个项目rider中有这样的实现。原理如下图所示:

实现了上述4类SQL之后，mybatis-generator就可以通过jdbc从Freedom获取元信息进而自动生成代码了。

事务支持

由于当前Freedom并没有保证并发，所以对于事务的支持只做了最简单的WAL协议。通过记录redo/undolog从而实现原子性。

redo/undo log协议格式

Freedom在每做一个修改操作时，都会生成一条日志，其中记录了修改前(undo)和修改后(redo)的行信息，redo用来回滚,redo用来宕机recover。结构如下图所示:

WAL协议

WAL协议很好理解，就是在事务commit前将当前事务中所产生的的所有log记录刷入磁盘。
Freedom自然也做了这个操作，使得可以在宕机后通过log恢复出所有的数据。

回滚的实现

由于日志中记录了undo，所以对于一个事务的回滚直接通过日志进行undo即可。如下图所示:

宕机恢复

Freedom如果在page全部刷盘之后关机，则可以由通过加载page的方式获取原来的数据。
但如果突然宕机,例如kill -9之后，则可以通过WAL协议中记录的redo/undo log来重新
恢复所有的数据。由于时间和精力所限，笔者并没有实现基于LSN的检查点机制。

Freedom运行

       git clone https://github.com/alchemystar/Freedom.git // 并没有做打包部署的工作，所以最简单的方法是在java编辑器里面 run alchemystar.freedom.engine.server.main     

以下是笔者实际运行Freedom的例子:

join查询

delete回滚

Freedom todo

Freedom还有很多工作没有完成，例如有层次的锁机制和MVCC等，由于工作忙起来就耽搁了。
于是笔者就看了看MySQL源码的实现理解了一下锁和MVCC实现原理，并写了两篇博客。比起
自己动手撸实在是轻松太多了^_^。

MVCC

https:// my.oschina.net/alchemys tar/blog/1927425

二阶段锁

https:// my.oschina.net/alchemys tar/blog/1438839

尾声

在造轮子的过程中一开始是非常有激情非常快乐的。但随着系统越来越庞大，复杂性越来越高，进度就会越来越慢，还时不时要推翻自己原来的设想并重新设计，然后再协同修改关联的所有代码，就如同泥沼，越陷越深。至此，笔者才领悟了软件工程最重要的其实是控制复杂度！始终保持简洁的接口和优雅的设计是实现一个大型系统的必要条件。

收获与遗憾

这次造轮子的过程基本满足了笔者的初衷，通过写一个数据库来学习数据库。不仅仅是加深了理解，最重要的是笔者在写的过程中终于明白了数据库为什么要这么设计，为什么不那样设计，仅仅对书本的阅读可能并不会有这些思考与领悟。
当然，还是有很多遗憾的，Freedom并没有实现锁机制和MVCC。由于只能在工作闲暇时间写，所以断断续续写了一两个月，工作一忙就将这个项目闲置了。现在将Freedom的设计写出来，希望大家能有所收获。

欢迎大家关注我公众号，里面有各种原创干货

想要学习怎么写数据库？那当然是看下面这本:

github链接

https:// github.com/alchemystar/ Freedom

码云链接

https:// gitee.com/alchemystar/F reedom