数据库中的数据结构

写在前面

先推荐一下 Christophe 的 How does a relational database work, 把 DBMS 的每个部分都理了一遍,可以让你对 DBMS 有一个大体的印象,不过这篇文章有些地方说法欠妥,看的时候最好带上脑子。

B 树/B+ 树

好,现在假设你已经瞄了一眼上面那个链接(其实不瞄也没关系),并且拥有了基本的操作系统和数据结构的知识。

我们先思考一个问题:现在你手里有一堆无序的 item,每个 item 有 key 和 value 两个属性,你要支持插入、删除、 按 key 查询、查询 key 连续的一段区间,你会选择什么数据结构? 第一想法肯定是各种平衡树、线段树。

然而,我所知的大多数硬盘数据库采用的是 B 树或者 B+ 树。B 树这种数据结构由来已久,从半个世纪前的 IMS 时代就开始用来存储数据。 B+ 树是 B 树的进化版,两者结构大同小异,B+ 树在最底层把所有结点链了起来以加快区间查询的速度。 现代 DBMS 很多采用的是 B+ 树。根据之前的假设,我们已经知道了 B+ 树是怎么实现的。 接下来分析一下为什么要使用 B+ 树而不是人民群众喜闻乐见的红黑树/treap/SBT/线段树等等数据结构。

首先线段树很难胜任这个工作,假设 key 的值域很大(例如 key 是一个 string),为了节省内存只能使用虚线段树, 这样每次访问叶子结点的复杂度都是 log( 值域 ) 的。如果同时 item 的数量远小于值域,线段树的速度是绝对比不上 平衡树或者 B+ 树的。这样一来,B+ 树的对手就只剩下平衡树了。我分别从查询和修改的角度比较一下这两类数据结构。

查询操作

查询操作最主要的就是提高范围查询的速度。

我先小小的得罪一下 Christophe,原文是这样的:

Although this tree works well to get a specific value, there is a BIG problem when you need to get
multiple elements between two values.It will cost O(N) because you’ll have to look at each node in
the tree and check if it’s between these 2 values (for example, with an in-order traversal of the tree).

另外他还认为使用平衡树或者线段树必须把所有数据读到内存,不然每个结点都要做一次 disk I/O

Moreover this operation is not disk I/O friendly since you’ll have to read the full tree.

我在网上还找到一种观点认为 B+ 树把数据顺序存储,在做范围查询的时候,从 disk 读连续的数据要快一些。

观点一纯粹是数据结构没学好。二和三都是 B+ 树的优点,但是其他数据结构也做得到。

比如我将数据分块后顺序存储在 disk,然后建立一个红黑树,节点存的内容为该结点对应的 key 和一个指向其 value 的指针, 范围查询时,先找到所求子串的起点,接下来或者往后一直扫到 key 不在范围内,或者再查询一次子串终点, 总可以达到后两点的效果。

另外一个说法是,B+ 树每个结点可以有很多子结点,使得树的高度比二叉平衡树更小,从而可以减少比较的次数。 这个说法没有考虑到的是,每个结点儿子多了,找到下一个结点所需要的比较次数也会增加。假设一个结点有 d 个儿子, 我们就要花费 log2(d) 次比较才能得到下一个结点,这个比较次数和把这个结点拆分成二叉的形式是一样的。 或许由于取整造成的误差,B+ 树可以节省一两次比较,但与巨大的 disk I/O 相比,这一点加速基本上可以忽略不计了。

说点题外话,我们知道 Clojure 是用一种最多 32 个子结点的函数式线段树来实现函数式的 vector 的,按上面的分析, 其复杂度应该也是 nlog2(n) 才对。但是这个线段树的 key 就是 vector 的 index,是一个从 1 到 n 的连续数列, 因此我们不需要在每个结点二分查找下一个子结点,直接用位运算即可在 O(1) 时间内得到下一个子结点。 在这样一棵函数式线段树中进行查询和修改操作只需要 log32(n) 次操作, 这也是一般将 Clojure 里的 vector 看作常数较大的数组的原因。( 也有人认为这是一种 TRIE)

一个结点有多个儿子还是有好处的。我们知道,操作系统从 disk 读数据不是一个 bit 一个 bit 的读的,从 disk 读取数据的最小单位是一个 page,大多数操作系统的 page size 都是数 KB。如果使用平衡树存储数据的话, 往往一个结点无法占满一个 page。而 B+ 树的每个结点更大 ( 通常 B+ 树一个结点的大小恰好是一个 page), 也就提高了每个 page 的利用率,虽然比较次数没变,但是 disk I/O 的次数比平衡树要小得多。 这也是 B+ 树相对于平衡树的主要优势。

修改操作

B+ 树的修改操作很有意思。它会先把修改作用到最底层,然后从倒数第二层开始(这里我把数据存储的地方看作最底层, 当然你也可以把最后一层结点看作最底层),如果结点的儿子太多就把他分成两半,儿子太少就找边上的兄弟合并。 是不是很像块状链表?你当然可以把 B+ 树的每一层在逻辑上看作一个块状链表。再结合每个结点的 size,我们发现 B+ 树其实就是 meta 进化版的多级页表,区别只是为了支持离散 key 值每个结点都存了多个 key, 以及为了支持插入删除而采用了类似块状链表的分裂/合并算法。这么一看 B+ 树长得和跳跃列表很像, 或许应该叫它 B+ 表才对。

至于 B+ 树和平衡树的性能,一般来说树高更小的 B+ 树所需的 disk I/O 次数小于平衡树。但是在刻意构造的数据下, 一直重复插入/删除同一结点,可以让 B+ 树每次操作都对一条链进行分裂/合并操作,这种情况下 B+ 树的修改效率甚至可能比红黑树更低。现实中的数据库应该不会用这么耿直的条件判断是否分裂/合并, 但是对同一数据的反复插入/删除仍然有可能造成一条链的反复分裂/合并, 我们在数据库中使用索引的时候还是要尽量避免。(别用带 B+ 树索引的数据库做 cache)

在很多情况下,我们可以在 schema 中加入一条 deleted 属性,删除时将 deleted 置为 true, 等到夜深人静的时候再将这些 item 从数据库里删掉。这样不仅避免了反复插入删除, 还可以拿这些数据干点其他事,何乐而不为?

还有一种常见的修改操作是只修改某个 item 的 value,这个操作和查询操作差不多,B+ 树显然优于平衡树。

InnoDB 中的 B+ 树

MySQL 在 5.5 之后的版本都是用 InnoDB 作为预设的存储引擎。InnoDB 中主要使用 B+ 树来实现索引。

实际上,InnoDB 的数据文件就是一个以 primary key 作为 key 的索引 ( 主索引 )。 当你在 InnoDB 中增加新的索引(我们叫辅助索引)时,这些索引最底层存储的是对应元素的 primary key。 数据库在辅助索引中找到 primary key 之后,还要回过头来在主索引找到对应的数据。

显然,primary key 的选择对索引的效率有着巨大的影响。primary key 过长(如 string),会对数据文件产生巨大影响, 包括每个结点儿子数变少,每次比较消耗时间变长,从而整个降低所有操作的速度。

另外,InnoDB 的主索引是一种聚集索引,即数据在物理上的顺序和逻辑上的顺序是一样的。这个特性的设计初衷可能是为了加快 primary key 的范围操作,但是加上这个约束的主索引只能看作一个在 disk I/O 上稍作优化的数组而已。 为了防止乱序插入造成主索引把数据到处移来移去,实践中一般用单调递增的值做 primary key。 这样一来主索引就变成按插入顺序排序了。这么搞确实可以加快按插入顺序的范围操作,但是为了对付这种甚至可能不存在的情况, 使用辅助索引的时候我们不得不查两次索引,我个人认为这种设计至少不够灵活,不知道 InnoDB 是出于什么考虑才选择这种设计的。

[UPDATE:好吧,我之前还是太年轻了。一方面这种情况还是蛮常见的,另一方面做数据库必然要有一个 trade off。想一个工具包揽所有场景是不现实的。 无疑 InnoDB 的这种设计在主键查询很多的情况下效率是很高的。]

在没有指定 primary key 的时候,InnoDB 会选择一个 UNIQUE 的属性作为存储数据文件的 key。如果没有 UNIQUE 的变量,InnoDB 会建立一个隐藏的 column,使用一个 6 byte 的 row ID 作为数据文件的 key。但是,这个 row ID 使用的是一个 全局的计数器 。更蛋疼的是,InnoDB 还在使用这个计数器的时候给它加锁, 并附赠周期性的 log write 操作,具体细节可以看 how-does-innodb-behave-without-a-primary-key。 MyISAM 尚且只给 table 加锁,这东西直接给所有用了这个计数器的 table 加个锁,后果可想而知。 不知道 InnoDB 何时修复这个设计失误,对使用者来说,实在找不到 primary key 的时候, 还是老老实实新建一个 auto increase 的变量当作 primary key 来的稳妥。

在数据库中,你还可以指定多个 parameter 作为 primary key,这时候数据库是将这些 parameter 当成一个向量作为主键用的。 这就产生了一个叫“最左前缀原则”的东西,由此也会产生一系列的索引调优 trick。比如说你需要经常执行一个 where a = x order by b,c 的操作,就可以建一个 a,b,c 的复合索引,数据库的优化器会帮你免去排序的操作。

有时候你要把找到的东西按逆序排序,这就产生一种叫逆序索引的东西。之前 MySQL 一直没有支持物理层面的逆序索引, 要利用逆序索引的话只能新建一个字段 b’=-b。MySQL 5.8 版本似乎开始支持真正的逆序索引了。

哈希表

跟 B+ 树相比,哈希表无疑要大众化的多。照样假设你已经了解哈希表的结构了。

哈希表的用途主要就是快速定位元素,而且只能用完整的 key 来定位。元素定位与修改的速度比 B+ 树快的多,

哈希表一定要处理哈希冲突,目前处理冲突一般用两类方法,一个是另外找个地方把冲突元素放进去,一个就是挂链。 这两个方法不好说谁优谁劣,design 的时候最好还是都实现一遍取最优的。

还听过一个方法叫公共溢出区,是把冲突的元素丢到另一个表,用 map 甚至是另一个哈希表来维护。这东西仔细想想就知道不靠谱。 如果溢出区用数组维护,那就是挂链法的超级退化版。如果用哈希表维护,看起来溢出区冲突少,但是考虑空间开销,和再哈希的开销, 你会发现这玩意其实就是再哈希法的退化版。用 map 也有类似的问题就不说了。

我在某司面试的时候碰到一个有趣的问题,现在的数据库大部分用的啥数据结构。我说数据丢内存的话用哈希多一点,丢硬盘的话用 B+ 树多一点。 面试官又问哈希寻址这么块为啥丢硬盘的不用哈希,只要一次 disk IO 多划算啊。我当时的回答是哈希表里元素超过一个阈值有个扩容的操作, 如果是硬盘数据库的话要把硬盘的数据都读一遍做个哈希,这个操作太慢了忍不了。也有一些方法把哈希表魔法变换一下减少这个操作的开销, 但是你设计来设计去还是发现不如用 B+ 树来得爽快。

根据之前的分析很容易知道,在内存里 B+ 树的优点基本失效(可能红黑树都打不过),单点读写操作被哈希表完爆, 即便要进行区间操作,只要在内存里加个辅助索引就能解决大部分问题,因此 in-memory database(IMDB) 使用哈希来存储数据基本上没有疑问。如果到了硬盘上,哈希表一方面有上面说的扩容巨慢的问题, 另一方面因为数据存储的位置是随机的,没法像 B+ 树一样利用空间局域性,因此在传统硬盘数据库中, 哈希表往往作为一种辅助索引出现。

顺便说一下 IMDB,跟传统的硬盘数据库相比,IMDB 有数据备份和内存价格两方面的弱点。优点很简单,就是一个字快。 这就不难理解为啥 redis 官网第一句话就说 redis 可以用来当 database, cache and message broker 了。 对绝大多数应用来说,用 IMDB 储存一部分数据就够了,总之就是 IMDB 当缓存用,数据还是存在硬盘里。 也有巨头公司把所有数据都丢到内存,确实是有钱。

最后哈希表有个坑,计算时间复杂度的时候要记得考虑哈希函数的复杂度,某些书上说的 O(1) 复杂度还是很 ideal 的。instaparse 的作者就曾经把一棵树直接丢到哈希表里头去,然后复杂度就变成 N^2^ 了。正解是想办法做个 O(1) 的哈希函数出来,这里就不多说了。

Q & A

全文索引是怎么实现的

MySQL 的参见 Inoo DB 的官方文档,个人感觉是一个比较鸡肋的东西。另外,全文索引是一种倒排索引(inverted index)。 建议使用其他更专业的工具代替。

之前在某司实习,接触了一点全文索引的东西,这玩意要优化起来花样还蛮多的, 其中之一是把出现位置差分之后用一个鬼畜编码方式压内存,真的是丧心病狂。

先留个坑吧,不保证填。