实现一个微型数据库

大家好，又见面了，我是全栈君，祝每个程序员都可以多学几门语言。

自己写一个简单的数据库，原理大概有下面几点：

一、数据以文本形式保存

将所要保存的数据写入文本文件，这个文本文件就是数据库。

为了方便读取，数据必须分为记录，每一条记录的长度规定为等长。

举例：假定每条记录的长度是800字节，那么第5条记录的開始位置就在3200字节。

大多数的时候我们不知道某一条记录在第几个位置，仅仅知道主键的值。这时为了读取数据，能够一条条比对记录。可是这样做的效率太低。实际应用中，数据库往往採用B树格式存储数据。

二、关于B树

要理解B树先须要理解二叉查找树

说二叉查找树是一种查找效率很高的数据结构，它有三个特点：

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

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

(3)在n个节点中找到目标值，一般仅仅须要log(n)次比較。

二叉查找树的结构不适合数据库，由于他的查找效率与层数有关。越处在下层的数据，就须要越多次的比較。极端的情况下，n个数据须要n次比較才干找到目标值。对于数据库来说，每进入一层，就要从硬盘读取一次数据，这很致命，由于硬盘的读取时间远远大于数据处理时间，数据库读取硬盘的次数越少越好。

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

B树的特点：

(1)一个节点能够容纳多个值。

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

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

这样的数据结构很有利于降低读取硬盘的次数。假定一个节点能够容纳100个值，那么3层的B树能够容纳100万个数据，假设换成二叉查找树，则须要20层。假定操作系统一次读取一个节点，而且根节点保留在内存中，那么B树在100万个数据中查找目标值，仅仅须要读取两次硬盘。

三、索引

数据库以B树格式存储，仅仅攻克了依照“主键”查找数据的问题。假设想查找其它字段，就须要建立检索(index)。

所谓索引，就是以某个字段为keyword的B树文件，假定一张“雇员表”，包括了员工号(主键)和姓名两个字段，能够对姓名建立索引文件，该文件以B树格式对姓名进行存储，每一个姓名后面是其在数据库中的位置(即第几条记录)。查找姓名的时候，先从索引中找到相应的第几条记录，然后再从表格中读取。这样的索引查找方法，叫做“索引顺序存取方法”，缩写为ISAM。它已经有多种实现，仅仅要使用这些代码库，就能自己写一个最简单的数据库。

四、高级功能

部署了最主要的数据存取(包含索引)以后，还能够实现一些高级功能。

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

(2)数据库连接(join)是指数据库的两张表通过“外键”，建立连接关系。你须要对这样的操作进行优化。

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

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

(5)远程操作：使得用户能够在不同的机器上，通过TCP/IP协议操作数据库。

关于数据库原理思考Q&A:

1、设计一个支持TB级别数据的数据库,并且要能支持高效的区间查询(范围查询).怎么办?

解答:首先要明白,并非全部的字段都能够做区间查询.比方对于一个员工,性别就没有所谓的区间查询,而工资是能够做区间查询的,比如查询工资大于a元而小于b元的员工。

我们将须要做区间查询的字段相应的字段值提取出来作为keyword构建一棵B+树，同一时候保存其相应记录的索引。B+树会对keyword排序，这样我们就能够进行高效的插入，搜索和删除等操作。我们给定一个查询区间，在B+树中找到相应区间開始的结点仅仅须要O(h)的时间，当中h是树高，一般来说都非常小。叶子结点保存着记录的索引，并且是按keyword(字段值)排好序的。当我们找到了相应区间開始的叶子结点,再依次从其下一个块中找到相应数量的记录,直到查询区间右端(即最大值)为止.这一步的时间复杂度由其区间中元素数量决定.

避免使用将数据保存在内部结点的树(B+树将数据都保存在叶子结点),这样会导致遍历树的开销过大(由于树并很驻内存)。

如果这棵B+树上相应的数字表示工资，单位千元。员工相应的工资数据，事实上就都保存在叶子结点上，内部结点和根结点保存的仅仅是其子结点数据的最大值。这里如果每一个叶子结点上的工资值所在的那条记录索引并没有画出来。OK，如今我们要查询工资大于25k小于60k的员工记录。

区间的開始值是25，我们訪问根结点，发现25小于59，于是向左子结点走。然后继续。发现25大于15且小于44，于是向当中间子结点走。最后在叶子结点查找到第一个大于25的值是37。接下来再依次地将结点内部的其它值 (44)，和它下一个叶子结点的值(51,59)相应的记录返回(不再往下查找，由于以下的数已经大于60)。这样一来，即实现了高效的区间查询。

部分内容来自点击打开链接，兴许依旧会不断更新完好。