数据库的最简单实现

作者: 阮一峰

日期: 2014年7月 4日

珠峰培训

所有应用软件之中,数据库可能是最复杂的。

MySQL的手册有3000多页,PostgreSQL的手册有2000多页,Oracle的手册更是比它们相加还要厚。

但是,自己写一个最简单的数据库,做起来并不难。Reddit上面有一个帖子,只用了几百个字,就把原理讲清楚了。下面是我根据这个帖子整理的内容。

一、数据以文本形式保存

第一步,就是将所要保存的数据,写入文本文件。这个文本文件就是你的数据库。

为了方便读取,数据必须分成记录,每一条记录的长度规定为等长。比如,假定每条记录的长度是800字节,那么第5条记录的开始位置就在3200字节。

大多数时候,我们不知道某一条记录在第几个位置,只知道主键(primary key)的值。这时为了读取数据,可以一条条比对记录。但是这样做效率太低,实际应用中,数据库往往采用B树(B-tree)格式储存数据。

二、什么是B树?

要理解B树,必须从二叉查找树(Binary search tree)讲起。

二叉查找树

二叉查找树是一种查找效率非常高的数据结构,它有三个特点。

(1)每个节点最多只有两个子树。

(2)左子树都为小于父节点的值,右子树都为大于父节点的值。

(3)在n个节点中找到目标值,一般只需要log(n)次比较。

二叉查找树的结构不适合数据库,因为它的查找效率与层数相关。越处在下层的数据,就需要越多次比较。极端情况下,n个数据需要n次比较才能找到目标值。对于数据库来说,每进入一层,就要从硬盘读取一次数据,这非常致命,因为硬盘的读取时间远远大于数据处理时间,数据库读取硬盘的次数越少越好。

B树是对二叉查找树的改进。它的设计思想是,将相关数据尽量集中在一起,以便一次读取多个数据,减少硬盘操作次数。

B-tree

B树的特点也有三个。

(1)一个节点可以容纳多个值。比如上图中,最多的一个节点容纳了4个值。

(2)除非数据已经填满,否则不会增加新的层。也就是说,B树追求"层"越少越好。

(3)子节点中的值,与父节点中的值,有严格的大小对应关系。一般来说,如果父节点有a个值,那么就有a+1个子节点。比如上图中,父节点有两个值(7和16),就对应三个子节点,第一个子节点都是小于7的值,最后一个子节点都是大于16的值,中间的子节点就是7和16之间的值。

这种数据结构,非常有利于减少读取硬盘的次数。假定一个节点可以容纳100个值,那么3层的B树可以容纳100万个数据,如果换成二叉查找树,则需要20层!假定操作系统一次读取一个节点,并且根节点保留在内存中,那么B树在100万个数据中查找目标值,只需要读取两次硬盘。

三、索引

数据库以B树格式储存,只解决了按照"主键"查找数据的问题。如果想查找其他字段,就需要建立索引(index)。

所谓索引,就是以某个字段为关键字的B树文件。假定有一张"雇员表",包含了员工号(主键)和姓名两个字段。可以对姓名建立索引文件,该文件以B树格式对姓名进行储存,每个姓名后面是其在数据库中的位置(即第几条记录)。查找姓名的时候,先从索引中找到对应第几条记录,然后再从表格中读取。

这种索引查找方法,叫做"索引顺序存取方法"(Indexed Sequential Access Method),缩写为ISAM。它已经有多种实现(比如C-ISAM库和D-ISAM库),只要使用这些代码库,就能自己写一个最简单的数据库。

四、高级功能

部署了最基本的数据存取(包括索引)以后,还可以实现一些高级功能。

(1)SQL语言是数据库通用操作语言,所以需要一个SQL解析器,将SQL命令解析为对应的ISAM操作。

(2)数据库连接(join)是指数据库的两张表通过"外键",建立连接关系。你需要对这种操作进行优化。

(3)数据库事务(transaction)是指批量进行一系列数据库操作,只要有一步不成功,整个操作都不成功。所以需要有一个"操作日志",以便失败时对操作进行回滚。

(4)备份机制:保存数据库的副本。

(5)远程操作:使得用户可以在不同的机器上,通过TCP/IP协议操作数据库。

(完)

一灯学堂

优达学城

留言(57条)

没有搞清楚索引的意思。
索引的意思是说,先按照姓名的值在B树中进行查找,找到姓名的索引号。再按照姓名的索引号在雇员表中找到雇员的所有信息吗?这和把姓名作为主键进行查找有何区别?

@Nuk:

改写了几句话,现在应该好懂一些了吧。

笔误:
一般来说,如果父节点有a个值,那么就有n+1个子节点。
应为:
一般来说,如果父节点有a个值,那么就有a+1个子节点。
或者:
一般来说,如果父节点有n个值,那么就有n+1个子节点。

transaction的翻译应该是事务不是交易...

在RSS里看到有几个错字,本想来报告的,没想到已经更正了。

这样实现后,就是一个sqlite了

好厉害的样子。连着看了几篇文章写的都很好。

这是关系型数据库的,非关系型可以更简单

@碧浪飞虹,@John:

谢谢指出,已经改过来了。

>二叉查找树是一种查找效率非常高的数据结构,它有两个特点。

应该是三个特点吧?

引用afu1982的发言:


应该是三个特点吧?


谢谢指出,已经更正了。

确实挺有意思,不过自己写个数据库有必要吗,或者在什么情况下,我们应该自己写个数据库,我是一个ERP实施顾问,工作中主要用到的就是数据库。都是商业级的。oracle要比sqlserver好很多。母鸡为什么

引用土木坛子的发言:

在RSS里看到有几个错字,本想来报告的,没想到已经更正了。

刚过来就看到更正了(我这是不是在找别人的茬?而忘了自己)

引用nickey的发言:

这是关系型数据库的,非关系型可以更简单

同意,非关系型的可能更简单,例如Google的leveldb,是一个较为简单的键值对型数据库,写得非常好

真是好文章,最近正好要自己实现一个微型数据库,无从下手,搜索引擎搜索出来的好多资料都很扯,每次读您的文章都大有收获,感觉您比我的大多数专业计算机老师都强的多,

好文章!问个问题
"每个姓名后面是其在数据库中的位置(即第几条记录)" 这里的第几条记录是索引吗?

"在n个节点中找到目标值,一般只需要log(n)次比较。"
该怎么理解,是最少需要log(n)次比较吗?

要不要实现一个呢?给个具体例子呗

这篇写得有点外行了。
首先,数据库 有很多种,这里其实想说的是 mysql oracle这种关系数据库的实现。

但是B+树其实只是一种查找数据的数据结构,和任何一种数据库没有必然的关系,使用这种数据结构的不一定就是关系数据库。

我觉得要说实现了一个关系数据库的底线是描述这种实现,对于从第一范式到BCNF的符合度。

引用Nuk的发言:
没有搞清楚索引的意思。索引的意思是说,先按照姓名的值在B树中进行查找,找到姓名的索引号。再按照姓名的索引号在雇员表中找到雇员的所有信息吗?这和把姓名作为主键进行查找有何区别?

关键是姓名不是主键啊

引用hello的发言:

这篇写得有点外行了。
首先,数据库 有很多种,这里其实想说的是 mysql oracle这种关系数据库的实现。

但是B+树其实只是一种查找数据的数据结构,和任何一种数据库没有必然的关系,使用这种数据结构的不一定就是关系数据库。

我觉得要说实现了一个关系数据库的底线是描述这种实现,对于从第一范式到BCNF的符合度。


我倒是觉得范式也未必体现关系数据库本质吧,更加本质的应该是基于数学的关系演算,是集合论的一种体现。关系数据库因为用严格的数学推导证明,所有更合适存储关键的,重要的数据,这应该的和文档数据库等其他数据库不同的地方。

引用Nuk的发言:

没有搞清楚索引的意思。
索引的意思是说,先按照姓名的值在B树中进行查找,找到姓名的索引号。再按照姓名的索引号在雇员表中找到雇员的所有信息吗?这和把姓名作为主键进行查找有何区别?

Hi, Nuk. 正好看到, お久しぶり。IIUC,姓名不可以做主键,数据是按照姓名排序,所以index姓名,得到第一个entry地址,然后开始sequential读取。

不错啊,mysql就有一个MYISAM(Indexed Sequential Access Method),这么说用的是B树哈

早上好啊

没啥这方面的基础,感觉云绕雾罩的。
收藏下,学习的时候再来看。

(2)除非数据已经填满,否则不会增加新的层。也就是说,B树追求"层"越少越好。

为什么第一层只有2个值,还没有填满4个,就有第二层了呢?

个人觉得可以通过《Database System:the completing book》(中文名:《数据库系统全书》),同时参考H2数据库的源代码(pure Java)来学习写一个简单的数据库。

那张图片,圆柱空间怎么并列放长方体抽屉

引用wffger的发言:

那张图片,圆柱空间怎么并列放长方体抽屉

扇区

好文章!!

引用hello的发言:

这篇写得有点外行了。
首先,数据库 有很多种,这里其实想说的是 mysql oracle这种关系数据库的实现。

但是B+树其实只是一种查找数据的数据结构,和任何一种数据库没有必然的关系,使用这种数据结构的不一定就是关系数据库。

我觉得要说实现了一个关系数据库的底线是描述这种实现,对于从第一范式到BCNF的符合度。


这个就有点吹毛求疵了。明明是原理贴的,都知道文章的目的,却要求完全和paper一样的严谨。那还不如去搜论文库了

好文,点个赞!

一般我就用现成的CMS,没有需要搭建数据结构。

在看到您关于“复杂”的软件后,我产生了一个问题:
应用软件中最复杂的是数据库了。
那,复杂的软件到底是怎么评判的呢?我们平常用的软件中还有更复杂的软件吗?

引用q的发言:

(2)除非数据已经填满,否则不会增加新的层。也就是说,B树追求"层"越少越好。

为什么第一层只有2个值,还没有填满4个,就有第二层了呢?

当只有不到4个值的时候就只有第一层,但当他插入第五个值的时候,就会在第一层保留一个中间的数并将剩余按二叉树规则分到左右子树

(2)除非数据已经填满,否则不会增加新的层。也就是说,B树追求"层"越少越好。


2,6

0,1 || 3 || 7, 8


这时候在来一个数据9 , 是新增一层还是重建上面的索引呢


索引文件是怎么存储的可以讲讲么?

写得超级棒的,现在学完数据库再来看这些东西就有一个整体的思路了。
谢谢分享。

这个还太high-level,要更深入地了解还是要去看源码,比如SharpHSql数据库。

MySQL是php的好搭档 学学蛮不错

还有更详细的介绍吗,比如说MySQL innoDB的介绍,联合索引的原理是什么,还有一条SQL语句进去,数据库优化器是如果进行识别的。很期待接下来的文章

假定每条记录的长度是800字节,那么第5条记录的开始位置就在3201字节吧?

阮一峰先生你好, 我是你的忠实读者(包括博客与翻译作品)
首先感谢您撰写了这么多好的作品, 其次呢, 在浏览您的文章的时候发现了一个小问题,想探讨一下
在这个文章http://www.ruanyifeng.com/blog/2012/08/blogging_with_jekyll.html中
结尾的两句命令
[code]
  $ git remote add origin https://github.com/username/jekyll_demo.git
  $ git push origin gh-pages
[/code]
这个地方我今天尝试了一下, 似乎第二条指令的用法似乎还有些问题, 我直接使用git push origin gh-pages是要报错的
改成git push -u origin gh-pages就对了
看帮助文档, 似乎这里的-u参数是指将文章提交到哪一个分支上,
希望有用
祝好!

@刘子龙:

-u是绑定远程主机,不加它应该不会报错。我会试一下,看看到底行不行。

引用xjhns的发言:

"在n个节点中找到目标值,一般只需要log(n)次比较。"
该怎么理解,是最少需要log(n)次比较吗?

就是从上到下,需要读几个节点才能找到所需的数据,一般二叉树或B树有n层,最多需要要读n次。

文章在B树部分的讲解还是通俗易懂的,实际数据库中要复杂些如B+,B*等。另外文章开头“一、数据以文本形式保存”,这个形象化描述不大恰当,一方面数据库支持的数据类型起码分为数值、字符、日期时间这三类,所以文本形式保存不能涵盖这些,例如字符'1'以选定的字符编码存储,而数字1直接以其机器值存储;另一方面,大多数数据库系统为了提高处理效率都是以其内部所能识别的二进制文件来存储数据,比如sql Server的mdf、ndf文件我们就不能直接拿哪个文本处理软件去直接读取它们。

可能我理解的也不全对,支持交流一下!

簡易明瞭!
當初在當學生時,老師講的太理論
在業界闖蕩了十多年
再來看這篇文章就覺得站長寫的真好

我也连续看来好多文章,感觉都写的太好了,我怎么才能达到老师的境界呢!

化繁为简,是为大道!喜欢!

理解力强就是能将简单的原理从复杂的文章中提取出来,赞

然而并没有什么卵用,因为没实现

那些所谓的高级特性应该多说一些的,前面的对于已经学习过数据库理论的大概都知道,但对于一个想要实现数据库系统的还是没有get到醍醐灌顶的点。希望对在实现DBMS多指点一下,谢谢

有些纳闷啊,一个节点一百个值。100万个数据确实三层就完成了。但是找到其中的一个需要比较次数又增加了。这个是在比较数据和读取硬盘次数之前做平衡吗?

阮老师,好文章!

感谢,对数据库有基本的了解!

麻烦问下:3层的B树可以容纳100万个数据,这个100w的数据是怎么计算出来的?非常感谢

b树跟二叉树的解释很有意思

一个好的搜索算法主要考虑的是搜索时间
如果是小型数据库,完全可以一次性加载到内存中,用二叉搜索,
实际生产中的数据库例如mysql,数据量动辄千万,肯定不能一次性加载到内存中,而是以物理文件形式存储硬盘中,这个时候搜索时间就主要分为两部分:数据从硬盘加载到内存的时间,从加载到内存的数据中找到匹配数据的时间,内存的速度远远大于硬盘IO的速度, 用b树,每个节点假设m个关键字,这个m的大小设计很关键,每次I/O读取一个页的数据(操作系统),在m尽可能大,又刚好装够这一个页的数据,就能减少I/O的次数, 当然还要考虑一点,我们希望每次搜索的时候尽可能时间代价不要差异过大,所以这个时候就要用到平衡树,每次加载到内存的数据再在内存中使用二叉搜索(m叉平衡树节点内是有序的)

我要发表看法

«-必填

«-必填,不公开

«-我信任你,不会填写广告链接