Mysql的索引为什么使用B+树而不使用跳表？

╰半橙微兮° 2023-09-28 09:11 156阅读 0赞

在我们的印象中，mysql数据表里无非就是存储一行行的数据。跟个excel似的。

直接遍历这一行行数据，性能就是O(n)，比较慢。为了加速查询，使用了**B+树**来做索引，将查询性能优化到了**O(lg(n))**。

但问题就来了，查询数据性能在 lg(n) 级别的数据结构有很多，比如redis的zset里用到的**跳表**，也是**lg(n)**，并且实现还贼简单。

**那为什么mysql的索引，不使用跳表呢？**

我们今天就来聊聊这个话题。

#### B+树的结构 ####

之前的一篇[文章][Link 1]里，已经提到过**B+树的结构**了。文章不长，如果没看过，建议先看下。

**当然，不看也行。**

在这里，为了混点字数，我简单总结下B+树的结构。

![221f72092044c406cce808f549201423.png][]

B+树查询过程

如上图，一般B+树是由多个页组成的**多层级**结构，每个页`16Kb`，对于主键索引来说，最末级的**叶子结点**放行数据，**非叶子结点**放的则是索引信息（主键id和页号），用于加速查询。

比方说我们想要查找行数据5。会先从顶层页的record们入手。**record里包含了主键id和页号（页地址）**。关注黄色的箭头，向左最小id是1，向右最小id是7。那id=5的数据如果存在，那必定在左边箭头。于是顺着的record的页地址就到了`6号`数据页里，再判断id=5>4，所以肯定在右边的数据页里，于是加载`105号`数据页。

在`105号数据页`里，虽然有多行数据，但也**不是挨个遍历的**，数据页内还有个**页目录**的信息，它可以通过**二分查找**的方式加速查询行数据，于是找到id=5的数据行，完成查询。

从上面可以看出，B+树利用了**空间换时间**的方式（构造了一批非叶子结点用于存放索引信息），**将查询时间复杂度从O(n)优化为O(lg(n))**。

#### 跳表的结构 ####

看完B+树，我们再来看下跳表是怎么来的。

同样的，还是为了存储一行行的数据。

我们可以将它们用**链表**串起来。

![612e70d67ef641e38fbd88526cb92c62.gif][]

单链表

想要查询链表中的其中一个结点，时间复杂度是O(n)，这谁顶得住，于是将**部分**链表结点提出来，再构建出一个新的链表。

![982010c2cbe7437e8d6ea4dd16d65389.gif][]

两层跳表

这样当我想要查询一个数据的时候，我先查上层的链表，就很容易知道数据落在**哪个范围**，然后**跳到下一个层级里进行查询。**这样就把搜索范围一下子缩小了一大半。

比如查询id=10的数据，我们先在上层遍历，依次判断1,6,12，很快就可以判断出10在6到12之间，然后往下一跳，就可以在遍历6,7,8,9,10之后，确定id=10的位置。直接将查询范围从原来的1到10，变成现在的1,6,7,8,9,10，算是砍半了。

![5c9e7c380f37653f4e678a7de0d4a4dd.png][]

两层跳表查找id为10的数据

既然两层链表就直接将查询范围砍半了，那我**多加几层**，岂不妙哉？

于是跳表就这样变成了多层。

![75db5c97452bc80ee1c4cce2a1c23c8b.png][]

三层跳表

如果还是查询id=10的数据，就只需要查询1,6,9,10就能找到，比两层的时候更快一些。

![fafc4d8c1bfc4d6bfbe45b4f8bc853d5.png][]

三层跳表查询id为10的数据

可以看出，跳表也是通过**牺牲空间换取时间**的方式提升查询性能。**时间复杂度都是lg(n)**。

#### B+树和跳表的区别 ####

从上面可以看到，B+树和跳表的**最下面一层，都包含了所有的数据**，且都是**顺序的，适合用于范围查询**。往上的层级都是构建出来用于提升搜索性能的。这两者实在是太像了。但他们两者在**新增和删除数据**时，还是有些区别的。下面我们以新增数据为例聊一下。

B+树新增数据会怎么样

B+树本质上是一种多叉平衡二叉树。关键在于"**平衡**"这两个字，对于多叉树结构来说，它的含义是子树们的高度层级尽量一致（一般最多差一个层级），这样在搜索的时候，不管是到哪个子树分支，搜索次数都差不了太多。

当数据库表不断插入新的数据时，为了维持B+树的平衡，B+树会不断分裂调整数据页。

我们知道B+树分为**叶子结点和非叶子结点**。

当插入一条数据时，叶子结点和它上层的索引结点（非叶子结点）最大容量都是16k，它们都有可能会满。

为了简化问题，我们**假设**一个数据页只能放三条行数据或索引。

加入一条数据，根据数据页会不会满，分为三种情况。

*  **叶子结点和索引结点都没满**。这种情况最简单，直接插入到叶子结点中就好了。

![5cf68ccd2436d2dee87814256a98ab1e.png][]

叶子和非叶子都未满

*  **叶子结点满了，但索引结点没满**。此时需要拆分叶子结点，同时索引结点要增加新的索引信息。

![8170402098750d690037d3dd3dcca6e1.png][]

叶子满了但非叶子未满.drawio

*  **叶子结点满了，且索引结点也满了**。叶子和索引结点都要拆分，同时往上还要再**加一层索引。**

![e62b6d6028f03dabc85c53688a474644.png][]

叶子和非叶子都满了

从上面可以看到，只有在叶子和索引结点**都满了**的情况下，B+树才会考虑加入一层新的结点。

而从之前的[文章][Link 1]知道，要把三层B+树塞满，那大概需要2kw左右的数据。

跳表新增数据

跳表同样也是很多层，新增一个数据时，最底层的链表需要插入数据。

此时，**是否需要在上面的几层中加入数据做索引呢？**

这个就纯靠**随机函数**了。

理论上为了达到**二分的效果**，每一层的结点数需要是下一层结点数的二分之一。

也就是说现在有一个新的数据插入了，它有`50%`的概率需要在`第二层`加入索引，有`25%`的概率需要在`第三层`加个索引，以此类推，直到`最顶层`。

举个例子，如果跳表中插入数据id=6，且随机函数返回第三层（有25%的概率），那就需要在跳表的最底层到第三层都插入数据。

![3f3733a8a80965fe8ad094bd1bd3c84f.png][]