数据库的最简单实现

2020-06-19

Ann Ann

数据库的最简单实现

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

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

但是,实现一个最简单的数据库,其实并不难。Reddit上面有一个帖子,只用了几百个字,就把数据库原理讲清楚了。

下面是我根据这个帖子整理的内容。

一、数据以文本形式保存

数据库用来储存数据。最简单的做法,就是把数据写入文本文件。

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

大多数时候,我们不知道某一条记录在第几个位置,只知道主键(primary key)的值。这时为了读取数据,可以一条条比对记录。但是这样做的效率太低。

为了提高效率,数据库往往采用B树(B-tree)格式储存数据。

二、什么是B树?

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

二叉查找树是一种查找效率非常高的数据结构。在n个数据中找到目标,一般只需要log(n)次比较。但是,这种结构不适合数据库,原因在于二叉查找树的效率与层数相关,越处在下层的数据,需要越多次比较。极端情况下,n个数据需要n次比较才能找到一个值。

对于数据库来说,每进入二叉查找树的一层,就要从硬盘读取一次数据,这对数据库的效率非常致命。因为硬盘的读取时间远远大于数据处理时间,数据库读取硬盘越少越好。

B树就是在二叉查找树的基础上,适应这种需要而产生的。它的设计思想就是,将相关数据尽量集中在一起,一次读取多个数据,以减少硬盘读取次数。

B树的特点有三个。

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

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

(3)子节点中的值,与父节点中的值,有严格的大小对应关系。一般来说,如果父节点有a个值,那么就有n+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协议操作数据库。

近期开课hot

Python零基础入门

start2025/02/12 03:14 (Sydney)

Web全栈班24期 NodeJS方向

start2024/12/08 11:30 (Sydney)

logo

Follow Us

linkedinfacebooktwitterinstagramweiboyoutubebilibilitiktokxigua

We Accept

/image/layout/pay-paypal.png/image/layout/pay-visa.png/image/layout/pay-master-card.png/image/layout/pay-stripe.png/image/layout/pay-alipay.png

地址

Level 10b, 144 Edward Street, Brisbane CBD(Headquarter)
Level 8, 11 York st, Wynyard, Sydney CBD
Business Hub, 155 Waymouth St, Adelaide SA 5000

Disclaimer

footer-disclaimerfooter-disclaimer

JR Academy acknowledges Traditional Owners of Country throughout Australia and recognises the continuing connection to lands, waters and communities. We pay our respect to Aboriginal and Torres Strait Islander cultures; and to Elders past and present. Aboriginal and Torres Strait Islander peoples should be aware that this website may contain images or names of people who have since passed away.

匠人学院网站上的所有内容,包括课程材料、徽标和匠人学院网站上提供的信息,均受澳大利亚政府知识产权法的保护。严禁未经授权使用、销售、分发、复制或修改。违规行为可能会导致法律诉讼。通过访问我们的网站,您同意尊重我们的知识产权。 JR Academy Pty Ltd 保留所有权利,包括专利、商标和版权。任何侵权行为都将受到法律追究。查看用户协议

© 2017-2024 JR Academy Pty Ltd. All rights reserved.

ABN 26621887572