数据库索引略知一二

avatar
Chaojie
数据库 索引

说到索引，很多人肯定会立马想到 MySQL 中使用了 B+ 树这种索引结构，毕竟是面试常考题型。我在准备面试的过程中，也只是浅显的了解到 MySQL 在创建主键时会自动创建一个主键索引，除此之外，还有联合索引、唯一索引等索引结构。创建主键索引的时候会通过 B+ 树来存储数据。所以，MySQL 为什么要使用 B+ 树作为索引？还有没有其他索引结构？索引到底是干什么的？带着这些疑问，我查阅了相关的资料，同时以项目背景为出发点，希望对索引做一次重新认识。

要实现一个最最简单的数据库，利用 Bash 函数就可以做到：

#!/bin/bash
db_set () {
	echo "$1,$2" >> database
}

db_get () {
	grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

这两个函数就是一个最简单的键值数据库，存数据时，不断在 database 文件末尾添加一行键值对即可，查数据时，通过 grep 会找到数据及之前所有的修改记录。这个数据库文件就像一个日志，不断的在末尾追加数据，由于传统磁盘对顺序写表现出的优异性能，数据库的写入性能会很高。但是有一个问题，如果一直往该文件中添加数据，久而久之，这个文件会变得异常大，文件中会出现很多重复的数据，同时，查找数据也是个问题，每次都要从头到尾找一次，别人都下班了，你还在等着查询结果。

既然文件很大，把它拆分成一个个小文件不就行了，同时定期对这些小文件进行压缩，剔除掉重复的和不要的数据，节省存储空间。但是查数据的问题怎么解决，现在的方式，每次找数据都要对整个表扫描一次，黄花菜都凉了。解决办法就是使用索引。

索引是什么

索引的本质就像一部字典前面的检索页，查字典时，通过拼音开头的字母可以快速查找到某个字的位置，索引也一样，通过给数据库中的数据添加类似路标的记号，这样从索引中就可以直接检索到该数据的位置。

让我们用最简单的 哈希索引 试试，哈希索引就是 在内存中将每个键都映射到数据文件中的字节偏移量，这个偏移量就是键对应值的位置。查找时，只要通过哈希映射找到偏移量，然后寻找该位置读取即可。

hash 索引

听起来是个不错的办法，但是大部分数据库都不会使用哈希索引，因为实际的数据库系统需要考虑的东西很多，比如发生崩溃后怎么处理，数据如何保证不丢失。除此之外，哈希索引需要整个放进内存中，如果我的键很多，散列冲突的可能性也会变大，同时，对于数据的范围查询支持也不够。

有没有更好的办法？

LSM-Tree 索引

聪明的大脑已经帮我们想出了解决办法。Google 传奇工程师 Jeff Dean 等人开发了一个可持久化的键值数据库 LevelDB。LevelDB 使用了一种称之为 SSTable（Sorted String Table）的表结构，顾名思义，SSTable 中数据会按照键的顺序排列，同时 LevelDB 在内存中维护着一个称之为 LSM-Tree （Log Structured Merge Tree）的索引结构，LSM-Tree 通过某种平衡树（比如基数树）结构保证键的有序，在超出树的容量后，就将其作为 SSTable 写入磁盘中，同时新的数据会被写入一个新的 LSM-Tree 中。

正如文章之前说的，LevelDB 会定期的在后台执行合并操作，将多个 SSTable 压缩为一个，以去除重复的或删除不用的数据。那么如何查找数据呢？既然键是有序的，查找就好办多了，比如使用二分查找，时间复杂度可以降到 O(log2n) 。LevelDB 会先在内存中查找关键字，然后在最近的 SSTable 中查找，然后在之前的表中查找。当然，在实际的实现中，LevelDB 对细节做了很多的优化，比如使用多层压缩来提升性能，这些都是后话了。

除了 LevelDB，Facebook 基于 LevelDB 开发了性能更好的 RocksDB，国内大名鼎鼎的分布式数据库 TiDB 底层存储就使用的 RocksDB。

B+Tree 索引

能不能使用 B+ 树来做索引？

当然可以，开源数据库 BoltDB 就使用 B+ 树来实现索引，而 etcd 的底层就使用的 BoltDB。除此之外，常见的关系型数据库（比如 MySQL、PostgresSQL 等）也常常使用 B+ 树来实现索引。相较于键值数据库，MySQL 等关系型数据库在数据存储上更为复杂，比如 Compact、Dynamic 行格式等，此处不做深究。所以，B+ 树索引有什么优点，为什么要用它来做索引。

基于 LSM-Tree 索引的数据库由于顺序写入的特点，有着很高的写入吞吐量，因为所有的前台写入都发生在内存中，并且所有后台写入都保持着顺序访问的模式。但是对于查询来说，往往需要在多个 SSTable 中依次查找，导致读取的吞吐量下降。而 B+ 树就不同了，在 B+ 树中只有叶子节点存储着数据，并且叶子节点之间通过链表顺序连接，在查找时，通过根节点确定数据的范围，然后顺着叶子节点的链表查找即可。在找到数据行对应的页之后，数据库会把整个页读入到内存中，并在内存中查找具体的数据行。

B+Tree

这就是为什么 MySQL 等数据库不使用 B 树来实现索引的原因，B 树中每个节点都会存储数据，在查找时，总是需要从根节点向下遍历子树查找满足条件的数据行，这个特点带来了大量的随机 I/O。

从 B+ 树的特点中，我们也能看到，其对于读取数据有着很好的性能，同时对于条件范围查询也能很好的支持，但是由于存储数据时会发生重复的随机磁盘写入，写入性能较差。为此，我也通过实验比较了几种使用不同索引结构的数据库，实验设备为公司电脑，环境为 Centos7 虚拟机（4core+4GB+40GB 磁盘）。

chart

可以看到，基于 B+ 树索引的 boltdb 和 bboltdb 的读取吞吐量很高，但是写入吞吐量却很低，而 rocksdb 和 leveldb 等基于 LSM 的数据库在写入吞吐量上表现优异，读取稍逊。

总结

数据库使用索引可以加快查询的速度，LSM 树索引的写入性能优异，而 B+ 树索引的读取性能更高，每条路上都有自己独特的风景，我们需要场景来选择合适的索引结构。除此之外，还存在着为搜索引擎设计的全文索引、模糊索引等。而引入索引的过程也造成了写的缓慢，这也是需要权衡的事。

（由于我的水平有限，文中难免出现错误，还望指正。）

参考文献

  1. https://draveness.me/whys-the-design-mysql-b-plus-tree/
  2. 《design data intensive application》——Martin Kleppmann
  3. https://github.com/boltdb/bolt
  4. https://github.com/google/leveldb
  5. https://shiniao.fun/posts/%E5%9F%BA%E4%BA%8Elsm%E7%9A%84%E6%95%B0%E6%8D%AE%E5%BA%93%E9%94%AE%E5%80%BC%E5%AD%98%E5%82%A8/
  6. https://yetanotherdevblog.com/lsm/

© CC BY-NC-SA 4.0 | Chaojie