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

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

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

算法解析

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

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

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

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

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

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

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

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

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

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

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

img

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

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

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

img

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

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

img

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

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

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

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

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

img

img

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

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[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 操作。

img

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

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

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

img

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

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

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

img

数据库索引以及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 叉树。

课后思考

  1. B+ 树中,将叶子节点串起来的链表,是单链表还是双向链表?为什么?

    答:这需要根据具体的场景思考。对于数据库查询问题,经常遇到升序或者降序问题。此时数据底层实现有两种做法:

    1)保证查出来的数据就是用户想要的顺序;

    2)不保证查出来的数据的有序性,查出来之后再排序

    对于第一种方法,需要使用到双向链表,浪费了存储空间。第二种方法节省了空间,但是需要额外的排序,浪费了时间。

  2. 对平衡二叉查找树进行改造,将叶子节点串在链表中,就支持了按照区间来查找数据。散列表(下)中讲到,散列表经常跟链表一起使用。若把散列表中的结点,也用链表串起来,能否支持按照区间查找数据呢?

    答:可以支持区间查询。java中linkedHashMap就是链表链表+HashMap的组合,用于实现缓存的lru算法比较方便,不过要支持区间查询需要在插入时维持链表的有序性,复杂度O(n)。效率比跳表和b+tree差。

------ 本文结束------
坚持原创技术分享,您的支持将鼓励我继续创作!

欢迎关注我的其它发布渠道