6.4 KiB
数据库功能简介
创建多个 JSON 集合，每个集合可以存取任意 JSON 结构（不必格式统一）。
const invodb = require('invodb')
// 博客文章存储示例
let col = invodb.createCollection('articles')
col.insert({
'id': '1',
'title': 'invodb设计原理简介',
'author': 'YuhangQ',
'content': '这里是 invodb 的设计原理的文章内容',
'catalog': '技术文章',
'tags': ['C++', '数据库', 'database']
})
数据库文件系统设计
页式管理
块（页）大小为 4kb
每一个块编号为 32 位 (4 byte)，低两位置 0。
理论最大文件大小为 2^30 * 4KB = 2^22 MB = 2^12 GB = 4TB
其中固定 0 号页用于存储该数据库中不同集合的信息，集合信息结构如下。
| 表项 | 集合名(字符串) | 第一条记录的逻辑地址 |
|---|---|---|
| 占用空间 | 28 byte | 4 byte |
一条表项占据 32b，所以本数据库最多支持 128 个数据集合。
虚拟页式管理
将数据库文件块分为两种，按照顺序编号
物理块：存在于实际的磁盘文件块
逻辑块：虚拟的文件块地址，所有软件逻辑编写均采用逻辑块地址
页表在文件中的存储
为了实现逻辑块编号到物理块的编号映射，文件中需要存储页表。
页表第一页放在物理 1 号页上，它的逻辑页也定义为 1 号页。
文件存储采用最简单的方式，顺序结构。每个表项有三个字段
| 表项 | 逻辑地址(隐含) | 物理地址 | 链接地址 |
|---|---|---|---|
| 占用大小 | 0 byte | 4 byte | 4 byte |
页表每个表项占 8byte，一个页存储的的表项数量为 4kb / 8b = 512 个。
极限情况下，4TB文件的页表，拥有 2^30 个逻辑地址，占用 2^30 * 8b = 2^33b = 2^3 GB = 8GB
页表采用单链表结构，由链接地址指向下一个页。
考虑到页表查询超级常用，页表需要加速索引，我们通过下文介绍的技术增快页表的查询速度。
- 内存加速
- 利用特性保证页表在磁盘文件中连续
紧凑的文件结构
引入虚拟页式管理是为了实现以下的操作：
- 删除表项时，会释放一个或多个物理块，造成文件空洞，将最后一个或几个物理块删除并填充进空洞，然后修改页表映射信息即可缩小文件大小，文件信息在文件中依然紧凑。
- 索引数据结构 B+ 树的链接信息比较多，如果没有虚拟编号，那么移动物理块的时候，索引信息需要全部更新，会需要引入更多索引信息的存储，并且会多次访问修改磁盘中的链接信息，严重拖慢速度。
- 磁盘中页表保证连续，从物理 1 号页面开始，连续的一片空间都用于存储页表。当新增页表块的时候，在文件尾新建一个块，然后将紧挨着页表空间的数据块移动到文件尾，然后将新页表块载入前方，保证页表连续且可扩展。
数据库索引算法设计
B+ 树
B+ 树是一种平衡树，拥有对数级的复杂度，对比普通平衡树，单个节点存储的信息量更大，这样树的高度明显降低。
由于 B+ 树的优秀特性，我们将节点的大小定为 4k，装入一个页内，然后存储到文件中。
由于树高较低，随机访问磁盘文件的次数显著降低，极其有利于数据库的效率。
主键
对于 JSON 而言，要求用户去设定主键是非常不合理的，由于 JSON 集合没有固定的表结构，可以存入任意形状的 JSON 信息，并不一定拥有一个同名且不冲突的字段。
所以我们为每个 JSON 添加隐藏字段 __Object_ID__，值为随机的 UUID，将其设定为主键。
主树
按照字段 __Object_ID__ 的大小关系建立一颗 B+ 树，存储在数据库文件中。
依据任意的一个 __Object_ID__ 值，可以快速索引到对应文件块的逻辑块号。
然后依据逻辑块号查询页表得到物理块号，之后读取对应的文件内容返回 JSON 数据。
从树
为需要查询的每一个字段在第一次查询时分别建立一颗 B+ 树用于索引。这颗 B+ 树同样要存储到数据库文件中。
索引的值指向 __Object_ID__ ，而不是物理块号。
查询某个字段时，如查询 “成绩大于 60，且小于 90 的所有信息”，按照如下步骤执行：
- 查询
成绩对应的 B+ 树，然后得到所有符合条件的__Object_ID__集合 - 使用
__Object_ID__查询主树，得到所有符合条件的逻辑块号 - 使用
逻辑块号查询页表，得到物理块号 - 读取文件，构造文件集合，返回结果
内存加速
以上数据库系统的设计中，并没有提到内存。这是因为我们的数据库设计的时候就是把所有的信息存储到文件中。
所以我们的数据库可以在一个最小模式上，以极低的内存占用依然高效地正常运行。
在相对内存充裕的机器上，使用一部分内存进行数据库的加速是非常有必要的，一些情况下可以加速数个数量级。
页表查询加速
使用 Map 数据结构在内存中构造 逻辑地址 - 物理地址 的直接映射，作为 Cache。
Cache 的大小可以设定的激进一些，在 128M 的页表 Cache 下，大概可以索引 1000 万个文件块。
利用少量的内存，使得页表的查询开销可以忽略不计。Cache 空间非常大，直接采用最简易 FIFO 淘汰策略也能得到非常好的缓存性能。
文件块加速
使用 Map 数据结构在内存中构造 逻辑地址 - 文件块信息 的直接映射，作为 Cache。
由于我们的所有算法都是通过文件块访问磁盘文件的，使用文件块 Cache 可以对本程序所有部分进行加速。
同样在 128m 的文件块 Cache 下，可以缓存 3 万个左右的文件块。
在充分预热的情况下，我们可以推测：内存的命中率是非常高的，本数据库的效率会非常好。
INVODB 技术总结
InvoDB 的架构设计还是非常精巧的，使用了并不复杂的多种技术实现了大部分操作复杂度达到常数级。
对于较复杂的查询，经过预热，均摊情况下也是对数复杂度，可以说本数据库也具有一定实际使用的价值。
开发完工后我们会和 MySQL、SQLite、MongoDB 等常用数据库进行跑分 PK，看看谁更快。