B+Tree 与存储索引

Posted on Edited on In Views:

1 硬盘存储知识

计算机的主存基本都是随机访问存储器 (Random-Access Memory，RAM)，分为两类：静态随机访问存储器（SRAM）和动态随机访问存储器（DRAM）。SRAM 比 DRAM 快，但是也贵的多，一般作为 CPU 的高速缓存，DRAM 通常作为内存。这类存储器他们的结构和存储原理比较复杂，基本是使用电信号来保存信息的，不存在机械操作，所以访问速度非常快，具体的访问原理可以查看 CSAPP，另外，他们是易失的，即如果断电，保存 DRAM 和 SRAM 保存的信息就会丢失。

内存的大小限制等原因，若要操作的数据集非常大，内存已经无法完全加载，则需要外部存储磁盘来进行数据存储。磁盘能够保存大量的数据，从 GB 一直到 TB 级，但是磁盘的读取速度比较慢，因为涉及到机械操作，读取速度为毫秒级，从 DRAM 读速度比从磁盘度快 10万倍，从 SRAM 读速度比从磁盘读快 100万倍。磁盘的结构：

image-20220814165957102

如上图，磁盘由盘片构成，每个盘片有两面，又称为盘面 (Surface)，这些盘面覆盖有磁性材料。盘片中央有一个可以旋转的主轴 (spindle)，他使得盘片以固定的旋转速率旋转，通常是 5400 转每分钟 (Revolution Per Minute,RPM) 或者是 7200RPM。磁盘包含多个这样的盘片并封装在一个密封的容器内。上图左，展示了一个典型的磁盘表面结构。每个表面是由一组成为磁道 (track) 的同心圆组成的，每个磁道被划分为了一组扇区 (sector)。每个扇区包含相等数量的数据位，通常是（512）子节。扇区之间由一些间隔 (gap) 隔开，不存储数据。

image-20220814171109054

如上图，磁盘用读 / 写头来读写存储在磁性表面的位，而读写头连接到一个传动臂的一端。通过沿着半径轴前后移动传动臂，驱动器可以将读写头定位到任何磁道上，这称之为寻道操作。一旦定位到磁道后，盘片转动，磁道上的每个位经过磁头时，读写磁头就可以感知到位的值，也可以修改值。对磁盘的访问时间分为 寻道时间，旋转时间，以及传送时间。

由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗时，所以为了提高效率，应尽量减少磁盘 I/O，即减少读写操作。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。 程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高 I/O 效率。

预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为 4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

文件系统及数据库系统的设计者利用了磁盘预读原理，将一个 BTree/B+Tree 节点的大小设为等于一个页，这样每个节点只需要一次 I/O 就可以完全载入。为了达到这个目的，在实际实现中还需要使用如下技巧：

  • 每次新建一个节点的同时，直接申请一个页的空间 (512 或者 1024)，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个 node 只需一次 I/O。

2 BTree 简介

BTree（平衡多路查找树）是为磁盘等外存储设备设计的一种平衡查找树。

按照上节内容介绍的，系统从磁盘读取数据到内存时是以磁盘块（block）为基本单位的，位于同一个磁盘块中的数据会被一次性读取出来，而不是需要什么取什么。

KV 存储或者数据库中，也是以页为基础的基本单位进行磁盘管理（存储中的单页大小是系统页的倍数）。

BTree 结构的数据可以让系统高效的找到数据所在的磁盘块。为了描述 BTree，首先定义一条记录为一个二元组 [key, data] ，key 为记录的键值，对应表中的主键值，data 为一行记录中除主键外的数据。对于不同的记录，key 值互不相同。

特性

一棵 m 阶的 B-Tree 有如下特性：

  1. 每个节点最多有 m 个孩子。
  2. 除了根节点和叶子节点外，其它每个节点至少有 Ceil (m/2)（向上取整）个孩子。
  3. 若根节点不是叶子节点，则至少有 2 个孩子。
  4. 所有叶子节点都在同一层，且不包含其它关键字信息。
  5. 每个非终端节点包含 n 个关键字信息（P0,P1,…Pn, k1,…kn）
  6. 关键字的个数 n 满足：ceil (m/2)-1 <= n <= m-1
  7. ki (i=1,…n) 为关键字，且关键字升序排序。
  8. Pi (i=1,…n) 为指向子树根节点的指针。P (i-1) 指向的子树的所有节点关键字均小于 ki，但都大于 k (i-1)。

BTree 中的每个节点根据实际情况可以包含大量的关键字信息和分支，如下图所示为一个 3 阶的 BTree：

image-20220820213724065

每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例，关键字为 17 和 35，P1 指针指向的子树的数据范围为小于 17，P2 指针指向的子树的数据范围为 [17, 35)，P3 指针指向的子树的数据范围为大于 35。

模拟查找关键字29 的过程：

  1. 根据根节点找到磁盘块1，读入内存。【磁盘 I/O 操作第 1 次】
  2. 比较关键字29 在区间 [17, 35)，找到磁盘块1 的指针 P2。
  3. 根据 P2 指针找到磁盘块3，读入内存。【磁盘 I/O 操作第 2 次】
  4. 比较关键字29 在区间 [26, 30)，找到磁盘块3 的指针 P2。
  5. 根据 P2 指针找到磁盘块8，读入内存。【磁盘 I/O 操作第 3 次】
  6. 在磁盘块8 中的关键字列表中找到关键字29。

分析上面过程，发现需要 3次磁盘 I/O 操作，和 3次内存查找操作。由于内存中的关键字是一个有序表结构，可以利用二分法查找提高效率。而 **3次磁盘 I/O 操作是影响整个 BTree 查找效率的决定因素 **。B-Tree 相对于 AVLTree 缩减了节点个数，使每次磁盘 I/O 取到内存的数据都发挥了作用，从而提高了查询效率。

3 B+Tree

从上一节中的 BTree 结构图中可以看到每个节点中不仅包含数据的 key 值，还有 data 值。而每一个页的存储空间是有限的，如果 data 数据较大时将会导致每个节点（即一个页）能存储的 key 的数量很小，当存储的数据量很大时同样会导致 BTree 的深度较大，增大查询时的磁盘 I/O 次数，进而影响查询效率。

B+Tree 是在 BTree 基础上的一种优化，使其更适合实现外存储索引结构。在 B+Tree 中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储 key 值索引信息，这样可以大大加大每个节点存储的 key 值数量，降低 B+Tree 的高度。减少磁盘的 I/O，提高查找效率。

3.1 特性

B+Tree 与 BTree 不同的几点：

  1. 非叶子节点只存储键值信息。
  2. 所有叶子节点之间都有一个链指针。
  3. 数据记录都存放在叶子节点中。

将上一节中的 B-Tree 优化，由于 B+Tree 的非叶子节点只存储键值信息，假设每个磁盘块能存储 4 个键值及指针信息，则变成 B+Tree 后其结构如下图所示：

image-20220820215539180

通常在 B+Tree 上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。因此可以对 B+Tree 进行两种查找运算：

  1. 一种是对于主键的范围查找和分页查找；
  2. 一种是从根节点开始，进行随机查找；

3.2 B+Tree 的创建与数据插入

假设需要创建 3 阶 B+Tree：

Max Key = M - 1 = 3
Min Key = (M / 2) - 1 = 1
Max Children = 4
Min Children = M / 2 = 2

创建 B+Tree, 依次插入值：1, 4 ,7, 10, 17, 21, 31, 25, 19, 20, 22, 42

首先定义一颗空树，然后依次新增，新增流程如下：

依次插入 1、4、7、10

image-20220820222046768

此时结点关键字已经达到 M（4）个的要求，若继续插入 17，则超过了 Max Children = 4 的规定，此时需要对节点进行分裂，分裂成树形结构，数据保存在 LeafNode 中，索引保存在 IndexNode 中。LeafNode 之间形成单向链表。

image-20220820222954418

继续插入 21、31，新增 31 时，右节点则超过最大阶数 4，则需要继续分裂成两个 LeafNode，同时索引也需要更新。

image-20220820224127106

继续新增 25、19

image-20220820225800977

继续新增 20、22，需要注意，此时不经超过了 Max Children = 4 的规定，Root 中，也超过了 Max Key = M - 1 = 3 的规定需要对 Root 进行分裂，分裂成两个 IndexNode。前面提到过，在 B+Tree 中除了 LeafNode，其他的 Node 存储的都是索引，Root 也是特殊的 IndexNode，所以不应该存在重复的索引，没有意义，因此在 LeafNode 中的 20 的索引，应该删除，具体步骤如下：

image-20220820232047245 image-20220820232123482

继续新增 42，最终 B+Tree 结构如下：

image-20220820232356586

3.3 B+Tree 的数据删除

本节介绍 B+Tree 的删除流程，复用上节的例子，对以下 B+Tree 依次删除：31、42、7、10、17

image-20220820232356586

删除 31 的过程中，即没有打破索引，也没有导致结点关键字少于最小关键字个数，所以整棵树并没有大的改动。

image-20220821212846585

我们删除 42 的时候，结点最关键字小于最小关键字个数。此时就需要借结点或者合并结点。针对删除 42，我们会发现，他的左兄弟结点关键字个数 3 大于最小关键字个数 2，所以可以借用。

借用规则：借用左兄弟最大关键字或者右兄弟最小关键字，如果是借用左兄弟，则更新左兄弟对应父结点的索引值 (因为最大关键字被借走)， 如果借用右兄弟则更新当前结点对应父结点的索引值 (因为借过来的肯定比当前索引值大)。

image-20220821213419714

继续删除 7，LeafNode 关键字个数小于最小值，且最有兄弟结点的关键字个数无法外借 (因为已经是最少关键字 2)，此时只能进行合并。

合并规则：如果合并之后索引结点孩子不足 2，则移除索引结点，合并结点充当新的索引结点，树的高度 - 1，如果合并之后，索引结点孩子大于等于 2， 则将被合并结点对应父结点的索引值移除。

image-20220821214247494

最后删除 10、17，删除 17 时，也触发合并流程，且更新索引时，索引节点也需要合并，索引结点的合并后，树的高度 - 1，并且更新根结点。

image-20220821220406095

3.4 Java 实现

参见 git: https://github.com/MarkHe1222/BPlusTree

3.5 MySql 为什么选择 B+Tree

  1. B+Tree 是 B TREE 的变种，B TREE 能解决的问题，B+TREE 也能够解决（降低树的⾼度，增⼤节点存储数据量）

  2. B+Tree 扫库和扫表能⼒更强。如果我们要根据索引去进⾏数据表的扫描，对 BTree 进⾏扫描，需要把整棵树遍历⼀遍，⽽ B+Tree 只需要遍历他的所有叶⼦节点即可（叶⼦节点之间有引⽤）

  3. B+Tree 磁盘读写能⼒更强。他的根结点和索引结点不保存数据区，所以根结点和索引结点同样⼤⼩的情况下，保存的关键字要⽐ BTree 要多。⽽叶⼦结点不保存索引结点引⽤，能⽤于保存更多的关键字和数据。所以，B+Tree 读写⼀次磁盘加载的关键字⽐ BTree 更多。

  4. B+Tree 排序能⼒更强。B+Tree 天然具有排序功能。

  5. B+Tree 查询性能稳定。B+Tree 数据只保存在叶⼦节点，每次查询数据，查询 IO 次数⼀定是稳定的。但是在 BTree 如果根节点命中直接返回，确实效率更⾼。

3.6 B+Tree 与 LSM-Tree 对比

存储引擎 B+Tree LSM-Tree 备注
优势 读取更快 写入更快
写放大 1. 数据和 WAL 2. 更改数据时多次覆盖整个 Page 1. 数据和 WAL 2. Compaction SSD 不能过多擦除。因此 SSD 内部的固件中也多用日志结构来减少随机写。
写吞吐 相对较低，大量随机写 相对较高：1. 较低的写放大（取决于数据和配置）2. 顺序写入；3. 更为紧凑
压缩率 存在较多内部碎片 1. 更加紧凑，没有碎片；2. 压缩率更大（共享前缀） 但 Compaction 不及时会造成 LSM-Tree 存在很多垃圾
后台流量 更稳定且可预测，不会受后台 Compaction 突发流量影响 1. 写吞吐过高，Compaction 跟不上，会进一步加重读放大； 2. 由于外存总带宽有限，Compaction 会影响读写吞吐；3. 随着数据越来越多，Compaction 对正常写影响越来越大。 RocksDB 写入太过快会引起 write stall，即限制写入，以期尽快 Compaction 将数据下沉。
存储放大 有些 Page 没有用满 同一个 Key 存多遍
并发控制 1. 同一个 Key 只存在一个地方；2. 树结构容易加范围锁 同一个 Key 会存多遍，一般使用 MVCC 进行控制 B+Tree（例如 innodb）在使用中日志记录相同键的多个版本，能够提供更强大的事务语义

4 总结

一般来说，存储索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘 I/O 消耗，相对于内存存取，I/O 存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘 I/O 操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘 I/O 的存取次数。

引用