从零实现一个数据库(DataBase) Go语言实现版 0.介绍

英文源地址

数据库实现步骤细分

1.持久化(Persistence)

我们为什么需要数据库?为什么不是直接把数据dump进文件中.
第一个话题就是持久化.
我们将讨论如果写入文件的过程中程序崩溃了, 或者电源断电了, 文件的状态会是什么样的呢?

• 文件是否只是丢失了最后一次写操作?
• 或者以写了一半的文件结束
• 或者是以更差的状态结束

任何结果都有可能.当你仅仅是简单写入文件的话, 你的数据并不能保证会持久化到磁盘上. 这对数据库是至关重要的.而且数据库在一次意外宕机后将会恢复到可用的状态.
我们是否有办法不适应数据库而做到持久化呢? 是有办法的:

1. 将所有更新的数据集写入一个新文件
2. 在新文件上调用fsync
3. 通过将新文件重命名为旧文件的方式覆盖旧文件, 这在操作系统层面是原子操作.

这只有当数据集很小的时候才是可行的.像SQLite这样的数据库可以做增量更新

2.索引(Indexing)

有两种不同类型的数据库查询: 分析式的(OLAP) 和 事务式的(OLTP). (这里补充一个链接, 数据库是OLTP应用的场景, 数据仓库是OLAP的应用场景: OLAP/OLTP)

• 分析式查询(OLAP)通常涉及巨量的数据, 会使用聚合, 分组或者join连接操作
• 相比之下, 事务式查询(OLTP)通常只使用少量的索引数据. 最普遍的查询类型是索引的位置查询或索引的范围查询.

注意单词’transactional’和你知道的数据库事务并无联系.计算机领域的术语常常会涵盖多种不同的涵义.本文关注的焦点在与OLTP技术.
当需要应用不是实时(real-time)系统时, 大多数面向用户的软件应当在合理(小)的时间内做出响应, 并使用合理的资源总量(内存, IO).这些属于OLTP的范畴.我们如何快速地查找数据(在Ologn内), 即使数据集是巨大的情况下?这就是我们需要索引(indexes)的原因.
如果我们忽视持久化的层面并且假设数据集很适合存在内存中, 快速地找到数据就是一个数据结构地问题. 持久化存在磁盘上的,用于查找数据的数据结构在数据库系统中就称为索引(indexes).而且数据库索引的大小可以超过内存的大小.这也就是说,如果你的问题适合使用内存解决, 那就是个比较容易的问题.
一般索引的数据结构使用B树(B-Trees)或者LSM树(LSM-Trees).

并发性

现代应用并不是顺序地做任何事情的, 数据库也是.有不同级别的并发性:

• 在读操作之间的并发性
• 在读操作与写操作之间的并发性, 写操作是否需要独占数据库呢?

即使是基于文件的数据库SQLite也支持一些并发性. 但并发性在一个进程中更易实现, 也是为什么大多数数据库系统只能通过一个’server’服务端访问.
加入了并发性后, 应用经常需要原子地做某件事, 比如读-修改-写操作.这为数据库引入了新的概念: 事务(transactions).