47B+树：MySQL数据库索引是如何实现的

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

为了加速数据库中数据的查找速度，常常对表中数据创建索引。那么数据库索引是如何实现的呢？底层使用的是什么数据结构和算法呢？

算法解析

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

如何定义清楚问题呢？除了对问题进行详细的调研，还可以通过对一些模糊的需求进行假设，来限定要解决的问题的范围。

对于数据库操作非常了解的，可以把索引的需求定义得非常清楚。一般人只了解一小部分常用的 SQL 语句，所以假设要解决的问题，只包含这样两个常用的需求：

根据某个值查找数据，比如 select * from user where id=1234；
根据区间值来查找某些数据，比如` select * from user where id > 1234 and id < 2345。

除了功能性需求外，这还会涉及一些非功能性的需求——安全、性能、用户体验等。这里我们只考虑性能方面的需要，主要考察时间和空间复杂度，也就是执行效率和存储空间。

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

问题的需求大致定义清楚了，那么能够利用已经学过的数据结构解决这个问题呢？

支持快速查询、插入等操作的动态数据结构，有散列表、平衡二叉查找树、跳表。

首先，对于散列表。其查询时间复杂度为$O(1)$，性能很好。但不支持按照区间快速查找数据。所以散列表不能满足需求。

再来看平衡二叉查找树。它查询时间复杂度为$O(logn)$，性能也很好。而且，对树进行中序遍历，可以得到一个从小到大有序的数据序列。但是仍然不支持按照区间快速查找数据。

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

这样看，跳表可以解决这个问题。但实际上，数据库索引用到的数据结构跟跳表非常相似，叫作 B+ 树。不过，它是通过二叉查找树演化过来的，而非跳表。从二叉查找树讲起，看如何改造成 B+ 树的。

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

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

改造之后，想要查找某个数据，直接按照二叉查找树的查找方式即可。

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

但是若为几千万、上亿的数据构建索引，如果将索引存储在内存中，尽管内存访问的速度非常快，查询的效率非常高，但是，占用的内存会非常多。怎么解决这个问题呢？

这里可以借助时间换空间的思路，将索引存储在硬盘中，而非内存中。

经过这样的改造，二叉查找树支持区间查找的功能就实现了。不过为了节省内存，如果把树存储在硬盘中，那么每个节点的读取（或者访问），都对应一次磁盘 IO 操作。对于快速查找某个数据的功能，每次查询数据消耗的操作数是磁盘 IO 操作的次数，也等于树的高度。

但是硬盘IO操作非常耗时，所以优化的重点就变成了减少磁盘IO操作，也就是尽量减少树的高度。

那如果我们把索引构建成 m 叉树，而非二叉树，高度是不是就减少了？如下所示，给 16 个数据构建二叉树索引，树的高度是 4，查找一个数据，就需要 4 个磁盘 IO 操作（如果根节点存储在内存中，其他结点存储在磁盘中）。若对 16 个数据构建五叉树索引，那高度只有 2，查找一个数据，对应只需要 2 次磁盘操作。如果 m 叉树中的 m 是 100，那对一亿个数据构建索引，树的高度也只是 3，最多只要 3 次磁盘 IO 就能获取到数据。磁盘 IO 变少了，查找数据的效率也就提高了。

若我们将 m 叉树实现 B+索引，对应的代码如下（假设我们给 int 类型的数据库字段添加索引，所以代码中的 keywords 是 int 类型的）：

/**
 * 这是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[keywordss大小]+m*8[children大小]
 * 上式中4表示int占用4个字节大小，而8表示指针占用内存大小
 */
public class BPlusTreeNode {
  public static int m = 5; // 5叉树
  public int[] keywords = new int[m-1]; // 键值，用来划分数据区间
  public BPlusTreeNode[] children = new BPlusTreeNode[m];//保存子节点指针
}

/**
 * 这是B+树中叶子节点的定义。
 *
 * B+树中的叶子节点跟内部结点是不一样的,
 * 叶子节点存储的是值，而非区间。
 * 这个定义里，每个叶子节点存储3个数据行的键值及地址信息。
 *
 * k值是事先计算得到的，计算的依据是让所有信息的大小正好等于页的大小：
 * PAGE_SIZE = k*4[keyw..大小]+k*8[dataAd..大小]+8[prev大小]+8[next大小]
 * int类型占用4个字节，long类型占用8个字节，指针占用8个字节
 */
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越大，树的高度越小。那m是不是越大越好呢？应该如何约束呢？

不管是内存中的数据，还是磁盘中的数据，操作系统都是按页（一页大小通常是 4KB，可以通过 getconfig PAGE_SIZE 命令查看）来读取的，一次会读一页的数据。如果要读取的数据量超过一页的大小，就会触发多次 IO 操作。所以，在选择 m 大小的时候，要尽量让每个节点的大小等于一个页的大小。读取一个节点，只需要一次磁盘 IO 操作。

尽管索引可以提高数据库的查询效率，但是索引也会让写入数据的效率降低。数据的写入过程，会涉及索引的更新，这是索引导致写入变慢的主要原因。

对于一个B+树，m值是根据页的大小事先计算好的。也就是每个节点最多只能有 m 个子节点。若往数据库写入数据时，导致索引中某些节点的子节点个数超过 m，该节点大小就超过了一个页的大小，读取这样一个节点，会导致多次磁盘 IO 操作。怎么解决这个问题呢？

实际上，只需要将这个节点分裂成两个节点。若分裂后，其上层父节点的子节点个数也超过 m 个，则用相同的方法将父节点也分裂成两个节点。这种级联反应会从下往上，一直影响到根节点。如下所示，图中的 B+ 树是一个三叉树。我们限定叶子节点中，数据的个数超过 2 个就分裂节点；非叶子节点中，子节点的个数超过 3 个就分裂节点。

正是因为时刻保证B+树索引是一个m叉树，所以索引的存在会导致数据库写入的速度降低。实际上，不光写入数据会变慢，删除数据也会变慢。这是为什么呢？

我们在删除某个数据时，也要对应的更新索引节点。这个处理思路有点类似跳表中删除数据的处理思路。频繁的数据删除，就会导致某些结点中，子节点的个数变得非常少，长此以往，如果每个节点的子节点都比较少，势必会影响索引的效率。

针对这个问题，可以设置一个阈值。在B+树中，该阈值为 m/2。如果某个节点的子节点个数小于 m/2，就将它跟相邻的兄弟节点合并。不过，合并之后结点的子节点个数有可能会超过 m。针对这种情况，可以借助插入数据时候的处理方法，再分裂节点。如下所示为一个删除操作的例子。图中的 B+ 树是一个五叉树。我们限定叶子节点中，数据的个数少于 2 个就合并节点；非叶子节点中，子节点的个数少于 3 个就合并节点。

数据库索引以及B+树的由来，本节就讲完了。其实B+ 树的结构和操作，跟跳表非常类似。理论上讲，对跳表稍加改造，也可以替代 B+ 树，作为数据库的索引实现的。

总结引申

本节主要介绍了数据库索引实现，依赖的底层数据结构，B+树。它通过存储在磁盘的多叉树结构，做到了时间、空间的平衡，既保证了执行效率，又节省了内存。其主要有如下特点：

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

除了B+树，还有B树、B-树。实际上，B-树就是B树，英文翻译都是B-Tree，这里的“-”并不是相对 B+ 树中的“+”，而只是一个连接符。

而B树实际上是低级版的B+树，B 树跟 B+ 树的不同点主要集中在这几个地方：

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

也就是说，B 树只是一个每个节点的子节点个数不能小于 m/2 的 m 叉树。

课后思考

B+ 树中，将叶子节点串起来的链表，是单链表还是双向链表？为什么？
答：这需要根据具体的场景思考。对于数据库查询问题，经常遇到升序或者降序问题。此时数据底层实现有两种做法：
1）保证查出来的数据就是用户想要的顺序；
2）不保证查出来的数据的有序性，查出来之后再排序
对于第一种方法，需要使用到双向链表，浪费了存储空间。第二种方法节省了空间，但是需要额外的排序，浪费了时间。
对平衡二叉查找树进行改造，将叶子节点串在链表中，就支持了按照区间来查找数据。散列表（下）中讲到，散列表经常跟链表一起使用。若把散列表中的结点，也用链表串起来，能否支持按照区间查找数据呢？
答：可以支持区间查询。java中linkedHashMap就是链表链表+HashMap的组合，用于实现缓存的lru算法比较方便，不过要支持区间查询需要在插入时维持链表的有序性，复杂度O(n)。效率比跳表和b+tree差。