B+ 树

Posted on

MySQL 数据库索引是如何实现的

作为一个软件开发工程师，你对数据库肯定再熟悉不过了。作为主流的数据存储系统，它在我们的业务开发中，有着举足轻重的地位。在工作中，为了加速数据库中数据的查找速度，我们常用的处理思路是，对表中数据创建索引。那你是否思考过，数据库索引是如何实现的呢？底层使用的是什么数据结构和算法呢？

算法解析

思考的过程比结论更重要。所以，今天的讲解，我会尽量还原这个解决方案的思考过程，让你知其然，并且知其所以然。

解决问题的前提是定义清楚问题

除了对问题进行详细的调研，还有一个办法，那就是，通过对一些模糊的需求进行假设，来限定要解决的问题的范围。如果你对数据库的操作非常了解，针对我们现在这个问题，你就能把索引的需求定义得非常清楚。但是，对于大部分软件工程师来说，我们可能只了解一小部分常用的 SQL 语句，所以，这里我们假设要解决的问题，只包含这样两个常用的需求：

  • 根据某个值查找数据，比如 SELECT * FROM user WHERE id=1234；
  • 根据区间值来查找某些数据，比如 SELECT * FROM user WHERE id>1234 and id<2345；

除了这些功能性需求之外，这种问题往往还会涉及一些非功能性需求，我们着重考虑性能方面的需求。性能方面的需求，我们主要考察时间和空间两方面，也就是执行效率和存储空间。在执行效率方面，我们希望通过索引，查询数据的效率尽可能地高；在存储空间方面，我们希望索引不要消耗太多的内存空间。

尝试用学过的数据结构解决这个问题

支持快速查询、插入等操作的动态数据结构，我们已经学习过散列表、平衡二叉查找树、跳表。

散列表的查询性能很好，时间复杂度是 O(1)。但是，散列表不能支持按照区间快速查找数据。所以，散列表不能满足我们的需求；尽管平衡二叉查找树查询的性能也很高，时间复杂度是 O(logn)。而且，对树进行中序遍历，我们还可以得到一个从小到大有序的数据序列，但这仍然不足以支持按照区间快速查找数据。

跳表是在链表之上加上多层索引构成的。它支持快速地插入、查找、删除数据，对应的时间复杂度是 O(logn)。并且，跳表也支持按照区间快速地查找数据。我们只需要定位到区间起点值对应在链表中的结点，然后从这个结点开始，顺序遍历链表，直到区间终点对应的结点为止，这期间遍历得到的数据就是满足区间值的数据：

实际上，数据库索引所用到的数据结构跟跳表非常相似，叫作 B+ 树。不过，它是通过二叉查找树演化过来的，而非跳表。

改造二叉查找树来解决这个问题

为了让二叉查找树支持按照区间来查找数据，我们可以对它进行这样的改造：树中的节点并不存储数据本身，而是只是作为索引。除此之外，我们把每个叶子节点串在一条链表上，链表中的数据是从小到大有序的。经过改造之后的二叉树，就像图中这样：

改造之后，如果我们要求某个区间的数据。我们只需要拿区间的起始值，在树中进行查找，当查找到某个叶子节点之后，我们再顺着链表往后遍历，直到链表中的结点数据值大于区间的终止值为止。所有遍历到的数据，就是符合区间值的所有数据：

但是，我们要为几千万、上亿的数据构建索引，如果将索引存储在内存中，尽管内存访问的速度非常快，查询的效率非常高，但是，占用的内存会非常多。我们可以借助时间换空间的思路，把索引存储在硬盘中，而非内存中。我们都知道，硬盘是一个非常慢速的存储设备。通常内存的访问速度是纳秒级别的，而磁盘访问的速度是毫秒级别的。读取同样大小的数据，从磁盘中读取花费的时间，是从内存中读取所花费时间的上万倍，甚至几十万倍。

二叉查找树，经过改造之后，支持区间查找的功能就实现了。不过，为了节省内存，如果把树存储在硬盘中，那么每个节点的读取（或者访问），都对应一次磁盘 IO 操作。树的高度就等于每次查询数据时磁盘 IO 操作的次数，所以，我们优化的重点就是尽量减少磁盘 IO 操作，也就是，尽量降低树的高度。

如图所示，给 16 个数据构建二叉树索引，树的高度是 4，查找一个数据，就需要 4 个磁盘 IO 操作（假设根节点存储在内存中，其他节点存储在磁盘中）；如果对 16 个数据构建五叉树索引，那高度只有 2，查找一个数据，对应只需要 2 次磁盘操作。如果 m 叉树中的 m 是 100，那对一亿个数据构建索引，树的高度也只是 4，最多只要 4 次磁盘 IO 就能获取到数据。磁盘 IO 变少了，查找数据的效率也就提高了：

我们将 m 叉树实现 B+ 树索引，用代码实现出来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 这是 B+ 树非叶子节点的定义
 *
 * 假设 keywords=[3, 5, 8, 10]
 * 4 个键值将数据分为 5 个区间: (-INF, 3), [3, 5), [5, 8), [8, 10), [10, INF)
 * 5 个区间分别对应：children[0]...children[4]
 *
 * m 值是事先计算得到的，计算的依据是让所有信息的大小正好等于页的大小：
 * PAGE_SIZE = (m-1) * 4[keywords 大小] + m * 8[children 大小]
 */
public class BPlusTreeNode 
{
    public static int m = 5; // 五叉树
    public int[] keywords = new int[m-1]; // 键值，用来划分数据区间
    public BPlusTreeNode[] children = new BPlusTreeNode[m]; // 保存子节点指针
}

/**
 * 这是 B+ 树中叶子节点的定义
 *
 * B+ 树中的叶子节点跟内部节点是不一样的
 * 叶子节点存储的是值，而非区间
 * 这个定义里，每个叶子节点存储 3 个数据行的键值及地址信息
 *
 * k 值是事先计算得到的，计算的依据是让所有信息的大小正好等于页的大小：
 * PAGE_SIZE = k * 4[keywords 大小] + k * (8[dataAddress 大小] + 8[prevAddress 大小] + 8[nextAddress 大小])
 */
public class BPlusTreeLeafNode 
{
    public static int k = 3;
    public int[] keywords = new int[k];      // 数据的键值
    public long[] dataAddress = new long[k]; // 数据地址

    public BPlusTreeLeafNode prev; // 这个结点在链表中的前驱结点
    public BPlusTreeLeafNode next; // 这个结点在链表中的后继结点
}

对于相同个数的数据构建 m 叉树索引，m 叉树中的 m 越大，那树的高度就越小。不管是内存中的数据，还是磁盘中的数据，操作系统都是按页（通常是 4KB）来读取的，一次会读一页的数据。如果要读取的数据量超过一页的大小，就会触发多次 IO 操作。所以，我们在选择 m 大小的时候，要尽量让每个节点的大小等于一个页的大小。读取一个节点，只需要一次磁盘 IO 操作：

数据的写入过程，会涉及索引的更新，这是索引导致写入变慢的主要原因。对于一个 B+ 树来说，m 值是根据页的大小事先计算好的，也就是说，每个节点最多只能有 m 个子节点。在往数据库中写入数据的过程中，这样就有可能使索引中某些节点的子节点个数超过 m，这个节点的大小超过了一个页的大小，读取这样一个节点，就会导致多次磁盘 IO 操作。

实际上，解决方案并不复杂。我们只需要将这个节点分裂成两个节点。但是，节点分裂之后，其上层父节点的子节点个数就有可能超过 m 个。不过这也没关系，我们可以用同样的方法，将父节点也分裂成两个节点。这种级联反应会从下往上，一直影响到根节点。这个分裂过程，你可以结合着下面这个图一块看，会更容易理解：

正是因为要时刻保证 B+ 树索引是一个 m 叉树，所以，索引的存在会导致数据库写入的速度降低。实际上，不光写入数据会变慢，删除数据也会变慢。我们在删除某个数据的时候，也要对应地更新索引节点。这个处理思路有点类似跳表中删除数据的处理思路。频繁的数据删除，就会导致某些节点中，子节点的个数变得非常少，长此以往，如果每个节点的子节点都比较少，势必会影响索引的效率。

我们可以设置一个阈值。在 B+ 树中，这个阈值等于 m/2。如果某个节点的子节点个数小于 m/2，我们就将它跟相邻的兄弟节点合并。不过，合并之后节点的子节点个数有可能会超过 m。针对这种情况，我们可以借助插入数据时候的处理方法，再分裂节点。文字描述不是很直观，我举了一个删除操作的例子，你可以对比着看下：

总结引申

我们讲解了数据库索引实现，依赖的底层数据结构，B+ 树。它通过存储在磁盘的多叉树结构，做到了时间、空间的平衡，既保证了执行效率，又节省了内存。为了方便你掌握和记忆，我这里再总结一下 B+ 树的特点：

  • 每个节点中子节点的个数不能超过 m，也不能小于 m/2；
  • 根节点的子节点个数可以不超过 m/2，这是一个例外；
  • m 叉树只存储索引，并不真正存储数据，这个有点儿类似跳表；
  • 通过链表将叶子节点串联在一起，这样可以方便按区间查找；
  • 一般情况，根节点会被存储在内存中，其他节点存储在磁盘中；

B 树实际上是低级版的 B+ 树，或者说 B+ 树是 B 树的改进版。B 树跟 B+ 树的不同点主要集中在这几个地方：

  • B+ 树中的节点不存储数据，只是索引，而 B 树中的节点存储数据；
  • B 树中的叶子节点并不需要链表来串联；