本篇继续做第三章的笔记,主要描述 B 树及其应用,以及 B 树和 LSM-Tree 的对比。第三章内容很多而且讲得都很好。

B 树

目前业界最为广泛应用的索引是 B 树

和 SSTables 类似,B 树也维护了按键排序的键值对,这种方式允许高效的键值查询和范围查找。其他地方就没有任何相似的了,B 树拥有一套完全不同的设计哲学。

B 树把数据库分解为大小固定(传统上是 4 KB)的 块(blocks)页(pages),并且每次读或者写都通过单独一个页。这种设计和底层硬件更加接近,因为磁盘也是按照大小固定的块安排的。

每一页都可以用一个地址表示,我们可以用这些页地址来构建一颗页组成的树:
looling up a key using a B-tree index

在 B 树中,有一页是作为树根存在的,任何查询的入口都是这一页。这一页包含了一些键以及它的子页的地址,每个孩子页都负责一连串连续的键,在这些地址之间的键表示这个范围的上下边界。

在 B 树中,每一页里包含的子页地址的数量被称为 branching factor,比如上图的 branching factor 就是 6。在现实世界里,这个值由每一页需要的存储空间和边界决定,不过通常情况下是几百。

更新一个 key 的值比较容易:找到 key, 更新,写回磁盘。

插入一个 key: 找到 key 所在的范围,插入。如果需要插入页的空间不足了,需要将这个页分成两个页,在子页里再插入,并且其父页也要相应的更新以适应这个改动。如下图所示:
Growing a B-tree by splitting a page.

这个算法可以保证一棵树总是平衡的:一颗有 n 个节点的 B 树总是有 O(log n)的查询复杂度。大多数数据库都可以适应一颗 3 到 4 层的 B 树,因此为了查找想要的 key 不需要追很多页(一颗 4 层且每页大小为 4 KB有 500 个 branching factor 的 B 树可以存储 256 TB 的数据)。

B 树可用性

B 树的底层写操作的原理是用新的数据覆盖硬盘上的一页,前提是假设这种覆盖不会改变一页的地址。你可以把这种覆盖操作理解为一种完全的硬件行为。

另外,有些操作需要覆盖多张页:例如,由于插入操作带来的分页,你需要覆盖两张页的数据的同时还要覆盖他们的父亲页(更新两个孩子页的地址)。这种操作是比较危险的:在只有部分页被更新的时候数据库崩溃了,这时索引就是崩坏的。

为了提高 B 树的可用性,一种常见的做法是:

在实现 B 树的同时,在硬盘上附加另外一个数据结构:write-ahead log (WAL,也叫做 redo log)。这是一个只可追加的文件,每个对 B 树的修改都应该在写入页之前追加到 WAL 中。当数据库崩溃恢复的时候,需要用这个 WAL 文件恢复数据。

另一个在原地更新页的麻烦之处是: 多个线程读取的并发控制。通常的做法是:给 B 树 加一个轻量的锁(latches)

B 树的优化

B 树的发展已经很久了,有很多可优化的点,例如:

  • 有些数据库使用 copy-on-write(COW) 机制而不是 WAL。
    COW 的基本概念是: 当有多个不可分辨的调用者读取同一个资源时,可以只给这些调用者资源的引用。直到有调用者试图修改这个资源。这时,重新生成一份这个资源的拷贝单独给这个调用者,这个拷贝对其他调用者是不可见的。并且这些改动对调用者是透明的。这种机制的好处在于如果没有修改的操作,资源没有被创建的必要。

  • 通过存储 Key 的压缩值而不是 Key 来增加 页 的存储空间。Key 只需要提供足够的信息用以描述边界即可。页中的 Key 越多 —> branching factor 越大 —> 树的层级越低

  • 为了使大范围查询的效率变高,一些数据库试图让叶子结点在硬盘上以序列存储的方式存储。但是随着树的大小增加,维护这种方式会非常困难。相对而言,LSM-trees 在这方面非常在行。

  • 添加额外的指针。例如:
    每个叶子结点都有指向自己兄弟节点的指针。这种做法使得范围查询的效率得以提高。

B-Tree vs LSM-Tree

粗略来说,LSM-Tree 对于写操作比 B-Tree 快,B-Tree 对于读操作更加快。但真实性能变现还是取决于存储的数据细节,不能一概而论。

LSM-Tree 的优势

  • B-Tree 索引的写入至少有两次: 写到 WAL 中和写到页本身。如果页需要分裂,次数还会增加。其次,为了修改一页中的一点点数据需要覆盖整个页数据。有些存储引擎为了防止部分更新甚至会覆盖两次。由于有压实合并策略的存在,LSM-Tree 也会数次重写数据。这种对数据库的一次写入造成了硬盘的数次写入的影响,被称为 write amplification(写入放大)。在重写的场景下,性能瓶颈在于硬盘的写入吞吐量,这时写入放大就成了一个主要的瓶颈。
  • 另外,另一个影响吞吐量的重要因素是:往硬盘写入 SSTable 是序列写而 B-Tree 的写入方式大部分是 随机写。关于序列写和随机写的比较可以参考这个问题
  • LSM-Tree 更容易被压缩,因此在硬盘上产生的文件比 B-Tree 更小。B-Tree 会在硬盘上留下碎片:因为某一页没有被用完。相对而言,由于 LSM-Tree 不是基于的形式的,并且会定期重写 SSTable 文件来清理碎片,因此在存储空间上更有优势,尤其是使用 leveled 压缩模式时。
  • 在许多 SSD 上,固件在内部会采用 LSM 算法把随机写变成序列写,但是更小的写入放大效应以及更少的碎片仍然是一大优势。

LSM-Tree 的不足

  • LSM 结构的一个缺点在于,压实的过程有时候会干扰正在进行的读写操作。由于硬盘的资源有限,所以当硬盘在执行昂贵的压实操作时读写请求有时会一直等待。虽然这个影响总的来说非常小,但是当从更高小的概率角度来看的话(p99,p999)延迟会变得很高,而 B 树的这种延迟相对而言更加可预测。

  • 压实操作的另一个问题会在写入量变大的时候显现:硬盘的有限的写入带宽需要被正常写入和压实写入操作共享。当写入一个空的数据库的时候,硬盘的写入带宽可以全部被正常写入占用,随着数据库的量变大,压实操作需要占用更多的带宽。

  • 当写入操作很多而压实操作没有被好好管理的话,压实操作的速度可能会跟不上写入,这样的话硬盘上就会有越来越多的违背合并的分片文件直到硬盘空间被用光。而且读操作也会变慢,因为需要查找更多的文件。由于 基于 SSTable 的数据库一般不会限制写入的量,所以需要有很好的额监测机制来保证这个事情。

  • 由于 B 树的每一 Key 只存在于一个固定的位置而 LSM 树的一个 Key 有可能存在于多个分片文件,因此基于 B 树的数据库要实现强事务会更容易:数据隔离是的键的范围上加锁实现的

其他索引结构

B 树和 LSM 树都属于 键值索引,在关系型数据中,类似于主键:数据库中每一行/每个文档/每个点都可以用一个表示。

为了提升索引效率,创建二级索引是很常见的做法。二级索引可以通过某种键值索引创建,主要差别在于:二级索引可以不唯一。这可以通过:1. 同一键对应的值是个列表;2. 同一键后加上另一个唯一标识来代表键。不管是哪一种,都可以使用 LSM-Tree 或者 B-Tree 实现。

在索引中存储值

值索引中,都是被查询的条件,但可以是:1. 键对应的具体值(具体某一行/某个文档/某个点); 2. 具体值的索引。对于第二种情况,真实数据所处的位置叫做 堆文件。 堆文件中存储的数据没有顺序。采用堆文件的方式很常见,因为在有多个二级索引存在的情况下,这可以避免重复文件的创建。

在一些场景下,从索引到堆文件这额外的一跳可能对读操作有性能影响,所以这时就想要将一行的数据直接存到索引中。这种方式叫做 clustered index(聚合索引)。例如,在 MySQL 的 InnoDB 存储引擎中,一张表的主键总是 clustered index,二级索引直接指向主键而不是堆文件位置。

聚合索引在提升了读操作的效率的同时会增加存储成本并降低写操作的效率,另外,数据库需要额外的操作来保证事务性。

多列索引

类似于复合索引。将多个字段连接在一起形成一个键。由于有顺序的影响,查询所有在复合索引中的字段或者查询从第一个字段开始后连续的字段是可以利用到索引的,但如果只查询后面的字段,是利用不到索引的。

多维索引在同时查询多列时很有用,尤其在地理位置领域。

多维索引通常使用 R-Tree 实现。

所有数据放在内存

有些基于内存的 kv 存储,比如 Memcached,只是作为缓存的目的存在,它允许数据丢失。而另一些有持久化需求的内存型数据库使用各种方法来保证:特殊硬件(电池驱动的内存),往硬盘中写更改日志,往硬盘中写快照将数据复制到其他机器上,等等。

内存型数据库的性能优势不(仅仅)在于它们不用从硬盘读数据。其实,如果你的内存够大的话,基于硬盘的存储引擎也可能永远都不会从硬盘读数据。这是因为操作系统会将最近使用的硬盘块加载在内存中。真正的性能优势在于:内存型的存储引擎避免了数据从内存到硬盘的编码开销

anti-caching 方法采用和 OS 类似的操作:当内存不够用时,把最不常用的数据写入硬盘,当这些数据被读的时候,再加载回来。数据库采用这种方法的效率比 OS 高,因为数据库可控的最小粒度是一条记录,而 OS 是整个内存页。这种方法可以用在可用内存比真实数据量小的情况。

总结

本篇介绍了 B 树,对比了 B 树 和 LSM 树。
另外还介绍了一些其他类型的索引。

(TO BE CONTINUED…)