共计 1639 个字符，预计需要花费 5 分钟才能阅读完成。
家喻户晓，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+ 树或者 跳表。同时每个数据结构都有其对应的侧重点。只有抓住这几个点，就不难剖析出为什么以后存储引擎应用该数据结构作为索引了。
激励一下
如果你感觉这篇文章不错，心愿能够给与我一些激励，在我的 github 博客下帮忙 star 一下。
博客地址
