在我们的印象中，mysql数据表无非就是存储一行数据。就像一个优秀的。直接遍历这一行数据，性能是O(n)，比较慢。为了加快查询速度，使用B+树作为索引，查询性能优化为O(lg(n))。但问题来了。查询数据性能在lg(n)级别的数据结构有很多。比如redis的zset中使用的跳表也是lg(n)，实现起来相当简单。那为什么mysql的索引不用跳表呢？今天就来聊聊这个话题。B+树的结构在上一篇文章中，已经提到了B+树的结构。文章不长，没看过的建议先看一下。当然，不看也没关系。在这里，为了打乱字数，我简单总结一下B+树的结构。B+树查询流程如上图所示。一般来说，B+树是由多个页面组成的多级结构，每个页面16Kb。对于主键索引，最后一级叶子节点释放数据，非叶子节点放置数据。索引信息（主键id和页码），用于加速查询。假设我们要查找行数据5。我们将从首页的记录开始。该记录包含主键id和页码（页地址）。注意黄色箭头，左边最小id为1，右边最小id为7。如果id=5的数据存在，则一定在左边箭头上。于是顺着记录的页地址走到6号数据页，再判断id=5>4，所以肯定是在右边的数据页，所以加载105号数据页。在数据页105中，虽然数据行很多，但是并没有一一遍历。数据页中还有一个页目录信息，可以通过二分查找加快行数据的查询，所以找到id=5的数据就OK了，完成查询。从上面可以看出，B+树以空间换时间（构造一批非叶子节点来存储索引信息），查询时间复杂度从O(n)优化到O(lg(n))。跳表的结构看完了B+树，我们再来看看跳表是怎么来的。同样，它仍然是用于存储逐行数据的。我们可以用链表将它们串起来。单链表要查询链表中的一个节点，时间复杂度为O(n)。谁受得了，于是提出了一些链表节点，新建了一个链表。两级跳表，当我要查询一条数据时，先查看上层链表，很容易知道数据落在哪个区间，再跳到下一级查询。这将搜索范围减少了一半以上。比如查询id=10的数据，我们先在上层遍历，依次判断1、6、12，很快判断出10在6和12之间，然后跳下去遍历6、7、8,9,10之后，确定id=10的位置。直接把查询范围从原来的1到10改成现在的1、6、7、8、9、10就减半了。二层跳表查找id为10的数据，既然二层链表直接把查询范围减半了，再多加几层不是更好吗？所以跳表就变成了这样的多层。如果还是在三级跳表中查询id=10的数据，只需要查询1、6、9、10就可以找到，比二级跳表要快。可以看出，id为10的数据是通过三层跳表查询出来的。可以看出，跳表也是通过牺牲空间换取时间来提高查询性能的。时间复杂度为lg(n)。B+树和跳表的区别从上面可以看出，B+树和跳表的底层包含了所有的数据，而且都是顺序的，适合范围查询。构建上层是为了提高搜索性能。两人太像了。但是两者在增删数据的时候还是有一些区别的。下面以新数据为例来谈一谈。B+树中的新数据会发生什么变化？B+树本质上是一个多叉平衡二叉树。关键就在于“平衡”二字。对于多叉树结构，其含义是子树的高度层级尽量保持一致（一般最多相差一层），这样在查找的时候，无论是哪个子树的Branches，查找的次数没有太大的不同。当不断有新的数据插入到数据库表中时，为了保持B+树的平衡，B+树会不断的分裂和调整数据页。我们知道B+树分为叶节点和非叶节点。插入一条数据时，叶子节点和它的上层索引节点（非叶子节点）最大容量为16k，有可能满了。为了简化问题，我们假设一个数据页只能容纳三行数据或索引。添加一条数据，根据数据页是否会满，分为三种情况。叶节点和索引节点都未满。这是最简单的情况，直接插入叶子节点即可。叶子和非叶子都不是满的。叶节点已满，但索引节点未满。这时需要对叶子节点进行拆分，需要在索引节点中加入新的索引信息。叶满而非叶不满。drawio叶子节点满了，index节点也满了。叶子节点和索引节点都要拆分，同时还要多加一层索引。叶子和非叶子都满了从上面可以看出，只有叶子和索引节点都满了，B+树才会考虑增加新的一层节点。从上一篇文章我们知道，要填满三层B+树，大约需要2kw的数据。向跳表中添加数据跳表也有很多层。添加新数据时，底部链表需要插入数据。这个时候是不是还要往上层添加数据做索引呢？这完全基于随机函数。理论上，为了达到二分法的效果，每一层的节点数需要是下一层节点数的一半。也就是说，现在插入了一条新数据，有50%的概率需要在二级增加索引，有25%的概率需要在三级增加索引，以此类推直到顶层。比如数据id=6插入跳表，随机函数返回到第三层（概率为25%），那么数据需要从底层插入到跳表的第三层桌子。跳表插入数据如果这个随机函数如上设计，当数据样本足够大时，数据分布就会满足我们理想中的“二分法”。与上面的B+树不同的是，是否给跳表加层纯粹是靠随机函数，完全不关心前、后、上、下节点。好了，基础科普结束了，我们可以进入正题了。为什么Mysql索引使用B+树而不是跳表？B+树是多叉树结构，每个节点是一个16k的数据页，可以存储更多的索引信息，所以扇出度很高。大概三层可以存储2kw左右的数据（只知道结论，想知道原因可以看前面的文章）。也就是说，数据被查询一次。如果这些数据页都在磁盘中，那么磁盘IO最多需要查询3次。跳表是一个链表结构，一个数据节点，如果底层需要存储2kw的数据，而且每次查询必须能够达到二分查找的效果，2kw大约是2的24次方，所以高度跳台大约在24层左右。在最坏的情况下，这24层数据会分散在不同的数据页中，即一次数据查询会经过24次磁盘IO。因此，要存储相同量级的数据，B+树的高度要小于跳表的高度。如果放在mysql数据库上，磁盘IO次数少，所以B+树查询速度更快。对于写操作，B+树需要对索引数据页进行拆分合并，独立插入跳表，层数根据一个随机函数确定，没有旋转和保持平衡的开销，所以write跳表的性能会比B+树好。其实mysql的存储引擎是可以改的。以前是myisam，后来是innodb。它们的底层索引都使用了B+树。也就是说，你可以创建一个索引为跳表的存储引擎，安装到mysql中。事实上，facebook构建了一个rocksDB存储引擎，它使用跳表。直接下结论，它的写性能确实比innodb好，但是它的读性能确实比innodb差很多。有兴趣的可以在文末参考资料中看到他们的性能对比数据。为什么redis使用跳表而不是B+树或者二叉树？Redis支持多种数据结构，其中有一个有序集，也叫ZSET。内部实现是跳转表。那为什么要用跳表而不用B+树等结构呢？几乎每次面试都会问这个问题。虽然我已经很熟悉了，但每次都得假装自己以前没有想过，当场想一想就知道答案了。真的，很考验演技。众所周知，redis是一个纯内存数据库。读写数据都是操作内存，与磁盘无关，所以不存在磁盘IO，层高不再是跳表的劣势。而且前面也提到了，B+树有一系列的合并和分裂操作。如果换成红黑树或其他AVL树，也会进行各种轮换，目的是保持树的平衡。在向跳表插入数据时，只需要随机检查一下就知道是否要加索引。完全不需要考虑前后节点的感受，减少了旋转平衡的开销。所以redis选择了跳表而不是B+树。综上所述，B+树是一个多叉的高扇出平衡搜索树。它只需要大约3层就可以存储大约2kw的数据。同样的情况下，跳表大约需要24层。假设层高对应磁盘IO，那么B+树的读取性能会比跳表好，所以mysql选择B+树作为索引。redis的读写操作都是在内存中进行的，没有磁盘IO。同时跳表实现简单。与B+树和AVL树相比，减少了旋转树结构的开销。所以redis使用跳表来实现ZSET，而不是树结构。存储引擎RocksDB在内部使用跳转表。与使用B+树的InnoDB相比，虽然写性能更好，但读性能其实差了一点。在读多写少的场景下，B+树还是YYDS。参考《MYSQL内核：INNODB存储引擎 卷1》。《RocksDB和Innodb引擎性能PK胜负难料?》。https://cloud.tencent.com/developer/article/1813695。
