数据库的最简单实现

标签: Computer | 发表时间:2014-07-04 15:04 | 作者:阮一峰
出处:http://www.ruanyifeng.com/blog/

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

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协议操作数据库。

(完)

文档信息

相关 [数据库] 推荐:

数据库sharding

- - 数据库 - ITeye博客
当团队决定自行实现sharding的时候,DAO层可能是嵌入sharding逻辑的首选位置,因为在这个层面上,每一个DAO的方法都明确地知道需要访问的数据表以及查询参数,借助这些信息可以直接定位到目标shard上,而不必像框架那样需要对SQL进行解析然后再依据配置的规则进行路由. 另一个优势是不会受ORM框架的制约.

数据库索引

- - CSDN博客推荐文章
索引是由用户创建的、能够被修改和删除的、实际存储于数据库中的物理存在;创建索引的目的是使用户能够从整体内容直接查找到某个特定部分的内容. 一般来说,索引能够提高查询,但是会增加额外的空间消耗,并且降低删除、插入和修改速度. 1.聚集索引:表数据按照索引的顺序来存储的. 2.非聚集索引:表数据存储顺序与索引顺序无关.

数据库事务

- - 数据库 - ITeye博客
事务传播发生在类似以下情形:. 假设methodB的配置是:. 如果methodA在事务里,那么methodB也在这个事务中运行. 如果methodA不在事务里,那么methodB重新建立一个事务运行. 如果methodA在事务里,那么methodB也在这个事务中运行. 如果methodA不在是事务里,那么methodB在非事务中运行.

数据库优化

- - 数据库 - ITeye博客
程序运行效率,优化应用程序,在SP编写过程中应该注意以下几点: . a) SQL的使用规范: .   i.尽量避免大事务操作,慎用holdlock子句,提高系统并发能力.   ii.尽量避免反复访问同一张或几张表,尤其是数据量较大的表,可以考虑先根据条件提取数据到临时表中,然后再做连接.   iii.尽量避免使用游标,因为游标的效率较差,如果游标操作的数据超过1万行,那么就应该改写;如果使用了游标,就要尽量避免在游标循环中再进行表连接的操作.

数据库调优

- - 数据库 - ITeye博客
1、1、调整数据结构的设计. 这一部分在开发信息系统之前完成,程序员需要考虑是否使用ORACLE数据库的分区功能,对于经常访问的数据库表是否需要建立索引等. 这一部分也是在开发信息系统之前完成,程序员在这一步需要考虑应用程序使用什么样的体系结构,是使用传统的Client/Server两层体系结构,还是使用Browser/Web/Database的三层体系结构.

MySQL数据库的修复

- Xin - 博客园-首页原创精华区
找到mysql的安装目录的bin/myisamchk工具,在命令行中输入:. 然后myisamchk 工具会帮助你恢复数据表的索引. 好象也不用重新启动mysql,问题就解决了. 当你试图修复一个被破坏的表的问题时,有三种修复类型. 如果你得到一个错误信息指出一个临时文件不能建立,删除信息所指出的文件并再试一次--这通常是上一次修复操作遗留下来的.

Oracle 发布 NoSQL 数据库

- 冷月 - 博客园新闻频道
  Oracle 作为全球最大的关系型数据库提供商,在其产品链条中,也加入了 NoSQL 数据库这一环,而且这个新的数据库名字很霸气,就叫 NoSQL Database,想起了当年新浪微博更换 weibo.com 域名之时的一个笑话:. 原来有三家人做面包,张三家的面包叫三张牌面包,李四家的牌子叫李四牌面包,王五家出品的是王五牌面包,而突然有一天,张三家的面包改名了,叫面包牌面包.

WineHQ 数据库泄漏

- gnawux - LinuxTOY
运行于 *Nix 之上的开源跨平台 Win32 API 兼容层 WineHQ 的 AppDB 和 Bugzilla 数据库被黑客攻击. CodeWeavers CEO Jeremy 在信中提到黑客利用某种方式获取了 WineHQ 的 AppDB 和 Bugzilla 的访问,并且下载了完整数据库文件.

数据库复制-Goldengate

- - 人月神话的BLOG
参考: http://wenku.baidu.com/view/4fd7ea22bcd126fff7050b5d.html. GoldenGate TDM(交易数据管理)软件是一种基于日志的结构化数据复制软件,它通过解析源数据库在线日志或归档日志获得数据的增删改变化,再将这些变化应用到目标数据库,实现源数据库与目标数据库同步、双活.