对比 B+ Tree 文件组织 / LSM Tree 文件组织(第一篇:B+ Tree)

B+ Tree 与 LSM Tree 是现今各类数据库中使用的比较多的两种数据结构,它们都可以作为数据库的文件组织形式,用于以相对高效的形式来执行数据库的读写。

本文简述了这两种数据结构的操作方式与操作开销,并对比了其自身的优缺点。

B+ Tree

B+ Tree 是我们比较熟悉的一种数据结构,它以节点(node)为单位来存储数据,每个 node 都可以存放多个 k-v 键值对,多个 node 以类似一棵树的形式组成完整的 B+ Tree,node 与 node 之间由指针来连接。

首先我们应当知道的是:B+ Tree 中保存的数据是有序的,我们通过 B+ Tree,可以实施查询、顺序访问、插入、删除的操作。

下图所示的就是一颗 B+ Tree (只保留 key,省略了具体的 value 值,下同):

对于上图,我们有如下解释:

  1. 关于 node:

    • node 中的 key 保持有序,从左至右依次增加。node 之间的 key 也保持有序,左边 node 的 key 小于右边 node

    • 红色 node 代表 internal node,即内部节点。internal node 包含的 k-v 键值对中,value 是指向下一个 node 的指针。在每一个 internal node 的最左边,还有一个指针,指向所有 key 都比本节点中最小 key 还要小的子节点。而 key 右边指针指向的子节点,其最小的 key 一定大于等于当前 key。

    • 蓝色 node 代表 leaf node,即叶子节点。leaf node 包含的 k-v 键值对中,根据具体实现的不同 value 可能代表存放实际数据的文件的偏移量,也可能直接就是实际数据(clustering index)。另外我们会发现,leaf node 本身还是一个双向链表,他们包含了前后指针。

    • B+Tree 是完全平衡的,即所有的 leaf node 都处于同一层级

  2. 图上部的 N=4 代表了这一棵 B+ Tree 的度(degree)是 4(也称 N-way B+ Tree)。

    • degree 的意思是,这棵树中任意一个 internal node,它最多能指向多少个子节点,由于 internal node 最左边还有一个指针,因此一个 internal node 中最多只能包含 N-1 个 key
    • node 中不仅限制了最大 key 数量,同时也限制了最少的 key 应大于 N/2 - 1。即每个 node 都至少是 “半满” 的
    • 假如由于插入、删除等操作导致 node 中 key 的数量不满足要求,则必须对 node 进行 分裂(insert) 合并(delete)
    • root node 既可以是 leaf,也可以是 internal。root node 的节点数不受 N 的限制

B+Tree 的操作

一切对 B+ Tree 的操作,无论如何都需要在操作完成后仍然满足 B+ Tree 的定义要求。

由于 B+ Tree 的有序性,search 操作非常简单,只要从 root 开始,根据需要查询的 key 来比较大小,一层层查找,直到找到 leaf node,之后在 leaf node 中按序找到对应的 k-v pair。

如上图紫色箭头所示的查找路径,我们期望找到 key == 6 的值,那么需要:

  1. 6 > 5 (root_key),进入右边 pointer 指向的子节点
  2. 6 < 7 (far left of internal node),进入中间层 internal node 最左边 pointer 指向的子节点
  3. 当前子节点已经是 leaf node,进入其中,依次对比,最终找到 k == 6 的节点

我们发现,对于一颗高为 h 的 B+ Tree,最多只需要 (h - 1) + (N - 1) 次对比,就能找到(或确定不存在)值。

其中,

  • h - 1 代表了查找 node 的次数,由于实际中磁盘存储的单位即是 node,因此 h - 1 可以看做是 I/O 次数
  • N - 1 代表了在 node 内部查找,由于实际中 node 都会被读入内存,因此 node 内的查找开销几乎可以忽略不计

Sequential Access

由于 leaf node 中包含了指向下一个 leaf node 的指针,因此对于类似 select * from tbl where i > 5这样的 顺序访问,只要找到第一个满足条件的 leaf node 后,就可以直接通过 next 指针来定位下一个 node。

假如是 clustering index (聚集索引)的实现,由于 node 之间的有序性,最佳情况下其数据在磁盘中的实际存储位置也是顺序存储的,那么顺序访问就会非常高效。

当然,如果 leaf node 只是指向了文件 offset,那么对 leaf node 的顺序访问并不代表对文件的顺序访问,这种情况下我们可以将范围内的 leaf node 按 offset 重排序之后再访问,因为多数查询并不要求结果集有序(“无序是关系模型之美” -- Andy Pavlo 如是说),这样就能顺序访问文件了。

Insertion

插入动作是一个多步判断的过程:

  1. 无论插入的是 internal 还是 leaf node,只要 node 中包含的 key 数量没有超过 N-1,那么就可以简单的将其插入:

  2. 一旦插入的 node 已满,这个时候就需要先将 key 插入,之后将 node 从中间一分为二,且:

    • 假如 node 本身是 leaf node,则将分裂出新节点的最左 key 作为新值,插入他们的 parent node

    • 假如 node 本身是 internal node,则将分裂出新节点的最左 key 移除,插入他们的 parent node

Deletion

删除动作,同样也是多步判断:

  1. 假如删除的是 root node,可以不受限制直接删除,如果 root node 为空则需要将下层 node 提升为 root

  2. 假如删除的 node 中 key 的数量 > N/2 - 1,那么可以直接执行删除后结束

  3. 一旦删除的 node 只有半满(half full),就必须执行如下操作:

    • 若其左右 sibling(同属一个 parent 下的兄弟)中有任意一个不是半满,就可以将其内的 key “借调” 到当前 node

      • Leaf:

        • 借左 sibling:将左 sibling 的最后一个 key 迁移至当前 node,更新 parent node 中指向当前 node 的 key 替换为借调来的新 key

        • 借右 sibling:将右 sibling 的第一个 key 迁移至当前 node,更新 parent node 中指向当前 node 的 key 为借调来的新 key,并将 parent node 中指向右 sibling 的 key 替换为右 sibling 新的最左侧 key

      • Internal:

        • 借左 sibling:

          1. 将左 sibling 的最后一个 key 迁出,上移替换 parent 中指向当前 node 的 key
          2. 将 parent 中被替换的 key 下移,与当前最左侧 pointer 合并,添加至当前节点,并更新该 pointer 指向的所有 children node 的 parent。将左 sibling 的最后一个 key 包含的 pointer 作为当前节点的新最左侧 pointer
        • 借右 sibling:

          1. 将右 sibling 的第一个 key 迁出,将该 key 对应的 pointer 作为右 sibling 的新最左侧 pointer,原来的最左侧 pointer 暂存。上移替换 parent 中指向右 sibling node 的 key
          2. 将 parent node 中被替换的 key 下移至当前节点尾部,对应的 pointer 为上一步暂存的 pointer,更新该 pointer 指向的 children node 的 parent
    • 若无 sibling 可借,则必须和左侧或右侧的 sibling 合并:

      • Leaf:

        • 向左合并:直接并入左 sibling,更新链表指针,删除 parent 中指向当前 node 的 key
        • 向右合并:直接并入右 sibling,更新链表指针,删除 parent 中指向当前 node 的 key
      • Internal:

        • 向左合并:将 parent 中指向当前 node 的 key 下移,删除其对应的 pointer,与当前 node 剩余 key 合并至左 sibling,更新当前 node children 的 parent
        • 向右合并:将 parent 中指向右 sibling 的 key 下移,删除其对应的 pointer,与当前 node 剩余 key 合并至右 sibling,更新当前 node children 的 parent

B+ Tree 结合 Buffer Pool 优化性能

基于前文的描述,我们会发现,B+ Tree 最大的优势,如同其他平衡树一样,就是增删查改的时间复杂度都是O(logn) ,这很优秀。

我们需要进一步考虑的是,为什么要用 B+ Tree,而不是其他的类似红黑树(甚至是跳表)之类的数据结构呢?根源主要还是在于存储介质。

优化 B+ Tree 的速度

磁盘相对来讲还是太慢了。假如数据都仅仅存储在内存中,那么哈希表、树、跳表等结构都完全可以,因为读写数据所花费的时间(相对于磁盘而言)非常快。而在面向磁盘(disk-oriented)的数据库设计中,I/O 开销是需要重点考虑的部分。

根据上图(来源)的数据,mem 的速度可以达到 disk(hdd)的上万倍。

在根据上图(来源)从更细分的 sequential 和 random 的角度看,sequential 下 mem 的速度只比 disk 快 10 倍以内,而 random 下差距瞬间扩大到 10 万倍!

鉴于通常我们都无法将数据库中的数据完整的放在 mem 中,因此针对磁盘 I/O 特性而对存储结构进行优化是必须的,通常我们可以想到如下几种方法:

  • 缓存层:最容易想到,使用效果通常也最立竿见影。其本质思想就是将热点数据缓存在内存中,以提高访问速度
  • 尽量使用sequential I/O:鉴于 sequential 与 random 巨大的速度差异,我们当然期望尽可能多的将读写都以 sequential I/O 的形式来实施
  • 尽量减少 I/O 次数:每执行一次 I/O 除了操作磁盘本身的开销外,系统调用相关的开销也很可观,因此用 10 次 I/O 每次读取 1 byte 和 1 次 I/O 读取 10 bytes 相比一定慢得多

与操作系统一样,数据库对磁盘数据的管理也是以 Page 为单位的,一个 Page 的容量从 4kb ~ 64kb 不等,在 B+ Tree 的实现中通常一一个 Page 用以代表一个 node,由于 Page 容量较大,因此大多数情况下 insert 和 delete 都不会涉及到 split 或 merge。同样的,由于 spilt 和 merge 较少发生,整个 B+ Tree 的层数也就相对较低。

再考虑 B+ Tree 的查找过程,我们会发现从 root 开始逐层向下搜索,每下一层都会读取一个不同的 node,产生一次 I/O,我们无法保证不同 node 能紧凑的存放,因此这种 I/O 是 random I/O。

基于此,层数越低,I/O 次数越少

还记得 leaf node 之间存在前后指针,在理想情况下,leaf node 间的范围读取,可以全部以 sequential 的方式进行,而不需要再通过树来搜索。但随着 B+ Tree 中数据的不断变化,leaf node 之间将逐渐失去顺序的特性,产生碎片,这会导致 sequential I/O 逐渐退化为 random I/O,因此需要做碎片整理。

同样的,如果按主键序插入,则都是顺序 I/O(无论是否是 clusterring index),插入效率就会很高(UUID 做主键的另一个弊端)。

最后,为了尽可能的减少不必要的 disk 访问,引入 Buffer Pool 来做缓存层,代理所有的 disk 访问请求。由于 B+ Tree 的 internal node 只存放 key 和 pointer,占用空间非常小,所以一个 Page 中能存放大量 key-pointer pair,这也让 Buffer Pool 中存放下所有的 internal node 成为可能。

假设 Buffer Pool 中存放了所有 internal node,那么每一次点查(point search)最多只需要一次 random I/O。

Buffer Pool

如上图(来源)所示,Buffer Pool 正好处于 disk 和 mem 之间,负责代理上层应用对 disk 数据的读写。其下层的 DiskManager 可以作为 Buffer Pool 的一个组件,而 B+ Tree 位于上层的 Access Method 中,因此 B+ Tree 的操作与 Buffer Pool 并不属于同一个层级。(如下图)

Buffer Pool 的应用,能够为数据库读写带来如下改善:

  1. READ:能够极大的降低 read I/O。对于需要被反复访问的热点数据,良好的算法与合理的 Buffer Pool 容量可以使其尽可能地待在内存中,以降低 disk I/O,理想情况下,甚至可以完全避免访问磁盘。
  2. WRITE:与 read 不同,持久化要求 write 操作迟早要落盘,因此 Buffer Pool 能做的更多的是延缓 write 而不能像消除 read I/O 一样消除 write I/O。但正因为延缓了 write,这能让随机的 write 操作被尽量的集中、合并。对同一块数据的多次写入可以仅在内存中完成,最后再刷盘。不同随机块的数据也许在一段时间后满足了顺序写入的要求,可以一次写入完成。

Buffer Pool 可以由如下几个组件构成:

  • Page Array:Buffer Pool 的主体,是一大块以 Page 为操作单位(称为 Frame)的内存,用于存放数据
  • Free List:用于管理 Page Array 中空闲 Frame 的线性表,期望从 Page Array 中申请 Frame 时优先从 Free List 中获取
  • Page Table:Page id 与 Page Array 中 index(称为 frame id)的映射关系,用于通过 Page id 快速查找数据
  • Disk Manager:和 disk 交互,进行磁盘读写,它可以持有一些 I/O 线程来专门负责 I/O 操作
  • Replacer:当 Page Array full 的时候需要将一些数据换出,以便于换入新数据。替换算法通常有 LRU、Clock 等

有趣的是,在事务型数据库中,为了保证 ACID 事务的 A 和 D,对 Buffer Pool 刷写数据和替换策略的设计上,有如下几种实现方式:

  • 换入换出:
    • No Steal: 某个事务中对 Page 的 uncommitted 修改,在 commit 之前都仅保持在 mem 中,而绝不落盘
    • Steal:在事务执行过程中,Page 可以随时被换出并落盘
  • 刷写数据:
    • Force:在某个事务提交时,所有事务中修改的数据都应全部落盘
    • No Force:事务提交后,其修改也可能还未落盘

为了保证 AD,最简单的实现方式就是 No Steal + Force:未提交的事务在 crash 后一定会丢失(因为未落盘),已提交的事务在 crash 后一定会存在(提交时同步落盘)。

但性能会大受影响:

  • 由于未提交事务中的 Page 不能被换出,则 Buffer Pool 中需要持有所有当前正在执行事务的 Page,导致同时执行的事务数受限
  • 由于事务提交时都要同步刷盘,则会导致大量的随机 I/O

因此更好的策略是 Steal + No Force:Page 可以被随时换入换出,也可以在任意时刻落盘,与事务脱钩。这样性能就可以大幅提升。

为了实现这一点,就需要额外的工作:

  • 为了实现 Steal,需要 UNDO log:假如事务还未提交,其修改的值就已经落盘,此时发生 crash,在恢复后需要用 UNDO log 来回滚该执行了一半的事务。
  • 为了实现 No Force,需要 REDO log:假如事务已经提交,但数据还未落盘,此时发生 crash,在恢复后需要用 REDO log 来重做未落盘的事务。

总结下来就是下图(来源):