聊聊存储引擎的实现要素

[wsafight]

众所周知，MySQL 的 InnoDB 存储引擎使用了 B+ 树作为索引实现，那么为什么不使用其他的数据结构呢？数组、链表或者哈希表。实现存储引擎究竟需要什么条件呢？

我们现在先以存储最简单的数据为例，这里的数据类似于 json 对象。有 key 和 value。

{
    "0": "value1",
    "1": "value2" 
}

最简单的存储引擎必须实现以下三个方法：

• read: (key: number) => value 查找 key 并返回 value
• write: (key: number, value) => void 查找并插入 key 以及 value
• scan: (begin: number, end: number) => value[] 查找返回 key 范围内数据

简单数据结构

对于开发项目来说，能使用最简单的数据结构完成项目是非常棒的，这意味着更少的 bug 和更少的时间。

有序数组

如果当前有序数组的位置和存储的 key 可以一一对应的话，也就是数组 index 对应 key（没有对应也就是稀疏数组），我们的 read 和 write 方法的时间复杂度会是 O(1)，scan 方法也是 O(1)。但数据量稍大就扛不住了。

退而求其次，不存在位置对应主键的情况下，有序数组紧密存储，这样可以通过二分查找，read 和 scan 方法的时间复杂度为 O(log2n)。但 write 方法成本会高到离谱。

综上所属，有序数组是在数据量少的情况下可以用来做存储引擎的。

哈希表

不考虑空间是不可能的，那么直接舍弃 scan 方法呢？在某些业务场景下是可以不使用 scan 方法的。

哈希表使用一对多的组织方式来实现 read 和 write。先对 key 进行 hash 运算然后再寻址，性能基本接近于 O(1)。

综上所属，哈希表在不考虑 scan 方法的情况下是可以用来做存储引擎的。

二叉平衡树

二叉平衡树相对 hash 和有序数据来说是一个折衷方案。该数据结构是通过链表实现的，所以不需要大块内存。它的 read 和 write 都是 O(log2n)，虽然 scan 遍历慢的难以忍受，但是它能够实现这三个方法了。

综上所属，二叉平衡树是可以用来做存储引擎的，但有一定的局限性。

要素分析

在分析上面几种数据结构后，我们不难得出结论。

• 有序性是实现 scan 方法的前提条件
• 局部性是提升 scan/read 方法性能的必要条件

这里我们提到了局部性，那么局部性究竟是什么呢？

通常来说，良好的计算机程序需要良好的局部性，局部性主要有：

• 时间局部性 ：指的是同一个内存位置，从时间维度来看，它能够在较短时间内被多次引用
• 空间局部性 ：指的是同一个内存位置，从空间维度来看，它附近的内存位置能够被引用

仔细分析一下，scan 方法和空间局部性有关。如果使用平衡二叉树来作为查询的数据结构。scan 的性能是非常差的，但是使用有序数组来作为数据结构 scan 可以直接遍历获取两者之间的数据，性能非常高。

同时，局部性也和 read 性能有很大关系。使用二分法来查询数据。局部性较低的情况下，read 需要多次从磁盘加载数据。如果局部性高，直接一次加载数据即可。

那是不是局部性越高越好呢？不是这样的。一方面局部性高会占用较高的内存。另一方面，局部性过高会导致 write 方法变慢，因为局部性高了，write 方法需要移动的数据也就多了。

平衡二叉树是唯一能在现实世界中实现 3 个方法的数据结构，局部性是提升 scan 方法性能的必要条件。那么把两者结合呢？把平衡二叉树的结点构造成一个个有序数组，这样就可以得到两个方案的优点了。

• 对于有序数组来说，通过拆分数组，使得在 write 方法的成本大大减少
• 对于平衡二叉树来说，通过节点替换，大大增加了局部性，让 scan 方法性能成本大大减少

事实上，只要能够低成本且高效的维持数据有序的数据结构都可以作为存储引擎。无论是 B 树, B+ 树或者 跳表。同时每个数据结构都有其对应的侧重点。只要抓住这几个点，就不难分析出为什么当前存储引擎使用该数据结构作为索引了。