mirror of
https://github.com/YuhangQ/InvoDB.git
synced 2025-01-26 22:50:56 +00:00
148 lines
6.4 KiB
Markdown
148 lines
6.4 KiB
Markdown
## 数据库功能简介
|
||
|
||
创建多个 JSON 集合，每个集合可以存取任意 JSON 结构（不必格式统一）。
|
||
|
||
```javascript
|
||
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，看看谁更快。
|