索引

数据库是我们广大程序员日常开发中必不可少的组件，作为数据持久化的基石，在互联网应用中，大部分的业务数据都以结构化的方式存储在数据库中，而数据库为我们提供了良好的数据查询、管理、持久化、事务的能力。在数据库场景下，我们存储的都是大量的数据，显然没有办法一次性把所有的数据全部加载到内存中，用内存高效的数据结构或者算法进行搜索。那数据库是如何快速查询数据的呢？比如：

  1. select * from student where id = 5130309492

如果我们逐一遍历数据库的每个记录逐个对比，也就是常说的“全表扫描”，查找速度肯定很慢。如何提高查找指定 ID 记录的速度呢？通常为了提高查找速度，我们需要设计一种适合磁盘场景的数据结构，对业务数据进行某种有序性的维护，在磁盘读写次数不多的情况下，结合内存，就能快速找到需要查询的记录在磁盘中所在的位置。这就是我们常说的“索引”。那索引一般是用什么样的数据结构实现的呢？

因为在数据库中，我们随时可能需要删除或者修改某个字段的值，如果要保持索引的线性有序性的要求，就要不断调整索引文件的前后顺序，在磁盘上，这个代价是非常高的。所以，为了能适配需要随机修改插入的数据库场景，我们的索引结构不能是线性的了。实际上，我们使用的是树形索引。

B+ 树实现

但是，普通的二叉查找树虽然能以 O(logn) 的时间复杂度查找指定数据，但对于范围查询就无能为力了。为了让二叉查找树支持按照区间来查找数据，我们对它进行改造：树中的非叶子节点并不存储数据本身，只是用来作为索引。数据都存储在叶子节点上，此外每个叶子节点串在一条链表上，链表中的数据是从小到大有序的。经过改造之后的二叉树就是类似于跳表的数据结构。
image.png
改造之后，如果我们要获取某个区间的数据。我们只需拿区间的起始值，在树中进行查找，当查找到某个叶子节点后，顺着链表往后遍历，直到大于区间的终止值为止。所有遍历到的数据就是符合区间值的所有数据。

但是，我们要为上亿的数据构建索引，如果将索引存储在内存中，尽管内存访问的速度非常快，但占用的内存也会非常多。为了解决索引占用太多内存的问题，我们可以用时间换空间，把索引存储在硬盘中。但硬盘是一个非常慢速的存储设备，读取同样大小的数据，从磁盘中读取花费的时间是内存访问的上万倍。这种将索引存储在硬盘中的方案，尽管减少了内存消耗，但是在数据查找的过程中，需要读取磁盘中的索引，因此数据查询效率就相应地降低了很多。

1. 多叉树

二叉查找树经过改造后，支持了区间查找的功能。但为了节省内存，如果把树存储在硬盘中，那么每个节点的读取都对应一次磁盘 IO 操作。树的高度就等于每次查询数据时磁盘 IO 操作的次数。由于磁盘 IO 操作非常耗时，所以优化重点就是尽量减少磁盘 IO 操作，也就是尽量降低树的高度。那如何降低树的高度呢？

如果我们把索引构建成 m 叉树，高度是不是比二叉树要小呢？如下图所示，给 16 个数据构建二叉树索引，树的高度是 4，查找一个数据，就需要 4 个磁盘 IO 操作（如果根节点存储在内存中，其他节点存储在磁盘中），如果对 16 个数据构建五叉树索引，那高度只有 2，查找一个数据，对应只需要 2 次磁盘操作。磁盘 IO 变少了，那查找数据的效率也就提高了。
image.pngimage.png
对于相同个数的数据构建 m 叉树索引，m 叉树中的 m 越大，树的高度就越小，那 m 是不是越大越好呢？不管是内存还是磁盘中的数据，操作系统都是按页（一页大小通常是 4KB）来读取的，一次会读一页的数据。如果要读取的数据量超过一页的大小，就会触发多次 IO 操作。所以，我们在选择 m 大小的时候，要尽量让每个节点的大小等于一个页的大小。这样读取一个节点，就只需要一次磁盘 IO 操作。
image.png
对于非叶子节点来说，节点大小为数据区间和子节点指针；对于叶子节点来说，节点大小为数据指针。

一个页的大小通常是 4K～16K，能包含的键数可以高达几千条。以 InnoDB 通常采用的 16K 大小的页为例，如果我们的索引字段和指针域大小为 8B，B- 树上的每个节点能包含的键数高达 2048 个，这就意味着用 4 层的高度，就可以存储接近 10 亿级别的记录，在索引字段大小更大的时候，我们通常也只需要 5 层以内，就可以构造大部分表的索引。这就是 B+ 树的主要优点，利用磁盘的预读能力和树状结构，我们通过 3～5 次磁盘 IO 就可以在 10 亿级的数据表中进行快速检索了。

如下为 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]
 */
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个数据行的键值及地址信息。
 */
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; // 这个结点在链表中的后继结点
}

2. 节点分裂

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

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

实际上，处理思路并不复杂。我们只需要将这个节点分裂成两个节点。但是，节点分裂之后，其上层父节点的子节点个数就有可能超过 m 个。我们可以同样将父节点也分裂成两个节点。这种级联反应会从下往上，一直影响到根节点。如下图所示，图中的 B+ 树是一个三叉树。我们限定叶子节点中，数据的个数超过 2 个就分裂节点；非叶子节点中，子节点的个数超过 3 个就分裂节点。
image.png

3. 节点合并

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

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

总结

由于数据库需要经常对数据进行增删改，我们的索引数据结构要能高效地变动，而且数据库本身存储的海量数据也意味着，索引结构不会只存在内存中，需要在二级存储中存储。相比于传统的二叉搜索树，B+ 树通过存储在磁盘的多叉树结构，做到了时间、空间的平衡，既保证了执行效率，又节省了内存。因此 B+ 树比起红黑树更加适合构建存储在磁盘中的索引。因为对相同个数的数据构建索引，B+ 树的高度要低于红黑树，从而读取 B+ 树索引需要的磁盘 IO 次数会更少。所以，大部分关系型数据库的索引，比如 MySQL、Oracle，都是用 B+ 树来实现的。

此外，利用磁盘的预读特性每次都可以加载一整个节点中全部的键，到内存进行二分查找，这样我们只需要通过 3～ 5 次的磁盘 IO 就可以查询加了索引的字段，非常高效。下面来总结下B+树的特点：

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

除了 B+ 树，你可能还听说过 B 树、B-树。实际上，B-树就是 B 树，英文翻译都是 B-Tree，这里的“-”并不是相对于B+树中的“+”，而只是一个连接符。B+ 树是 B 树的改进版，它们的不同点主要集中在这几个地方：

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

B+ 树，相比于 B- 树的主要特点就是，只在叶子结点存储数据，而且叶子节点间用首尾相连的指针串联成双向链表，可以获得良好的范围查询的效果，背后的本质就是索引和数据的分离。