使用 B+ 树 or 使用跳表？

B+ 树和跳表的区别

首先，B+ 树和跳表的最下面一层都包含了所有的数据，而且都是顺序的，适用于范围查询。

此外，往上构建出来的层级都是用于提升搜索性能的。

但二者在新增和删除数据时，还是有些区别的。

B+ 树新增数据

B+ 树本质上就是一颗多路平衡二叉树。关键在于“平衡”，对于多叉树结构来说，它的含义是：子树们的高度层级应尽量保持一致（一般最多差一个层级），这样在搜索时，不管是到哪个子树分支，搜索次数都差不了太多。

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

而 B+ 树又可分为叶子节点和非叶子节点，在插入一条数据时，叶子节点和它上层的索引节点（非叶子节点）的最大容量都是 16k，它们都有可能会被占满。

这里假设一个数据页只能放三条行数据或者索引，加入一条数据，根据数据页会不会被占满，可分为以下三种情况。

• 叶子节点和索引节点都没被占满

这种情况最简单，直接插入到叶子节点中就好了。

• 叶子节点满了，但索引节点没满

此时需要拆分叶子节点，同时索引节点还要增加新的索引信息。

• 叶子节点满了，并且索引节点也满了

此时叶子节点和索引节点都要进行拆分，同时还要往上再加一层索引。

简单来说，只有当叶子节点和索引节点都满了的情况下，B+ 树才会考虑加入一层新的节点，而如果要把三层的 B+ 树塞满，那大概需要 2kw 左右的数据。

跳表新增数据

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

此时，判断是否需要在上面的几层中加入数据做索引，就纯靠随机函数了，不关心前后上下的节点。

理论上为了达到二分的效果，每一层的节点数应当是下一层节点数的二分之一。

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

当数据量样本足够大的时候，数据的分布就能符合理想中的“二分”效果。

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

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

B+ 树是多叉树结构，每个节点都是一个 16k 的数据页，能存放较多的索引信息，所以扇出很高，大概三层就可以存储 2kw 左右的数据。也就是说，查询一次数据，如果这些数据页都在磁盘中，那么最多需要经过三次磁盘 I/O。

跳表是链表结构，一条数据一个节点，如果最底层要存放 2kw 的数据，并且每次查询都要能达到二分查找的效果，那么跳表的大概高度在 24 层左右（2kw 大概是 2 的 24 次方）。最坏的情况下，这 24 层数据会分散在不同的数据页里，即查一次数据会经过 24 次磁盘 I/O。

因此存放同样量级的数据，B+ 树的高度比跳表要小，对于 MySQL 数据库来说，就是磁盘 I/O 次数更少，因此 B+ 树查询更快。

但针对写操作，由于 B+ 树需要进行拆分合并索引数据页，跳表则是独立插入，并且是根据随机函数来确定层数，没有旋转和维持平衡的开销，所以跳表的写入性能会比 B+ 树更好。

当然，也可以造一个以跳表为索引的存储引擎装到 MySQL 里。事实上，Facebook 的 RocksDB 的存储引擎就使用到了跳表。

Redis 为什么使用跳表而不使用 B+ 树或二叉树？

Redis 支持多种数据结构，其 zset（有序集合）的内部实现就是跳表。

首先，Redis 是内存数据库，进行读写数据时都是操作内存，跟磁盘无关，因此也不存在磁盘 I/O，所以层高就不再是跳表的劣势。

此外，B+ 树有一系列的合并拆分操作，即使换成红黑树或其他 AVL 树也是要经过各种旋转，其目的也是为了保持树的平衡。

而跳表插入数据时，只需要经过随机函数，就能判断要不要往上加索引，根本不用考虑前后上下的节点，也就少了旋转平衡的开销。

因此，Redis 选择使用跳表，而不是 B+ 树。

总结

B+ 树是多叉平衡搜索树，扇出高，只需要大概 3 层就能存放 2kw 左右的数据，而同样情况下跳表则需要 24 层左右，假设层高对应着磁盘 I/O，那么 B+ 树的读性能会比跳表更好，因此 MySQL 选择 B+ 树做为索引。

Redis 的读写操作全在内存中进行，不涉及磁盘 I/O，同时跳表的实现简单，相比于 B+ 树、AVL 树，减少了旋转树结构的开销，因此 Redis 使用跳表来实现 zset，而不是采用树结构。

存储引擎 RocksDB 内部使用了跳表，对比使用 B+ 树的 InnoDB 存储引擎，虽然其写性能更好，但读性能属实较差。在读多写少的场景下，还是应当选择 B+树。

（扇出性：是指该模块直接调用的下级模块的个数。扇出大表示模块的复杂度高，需要控制和协调过多的下级模块。）

参考文档

• https://mp.weixin.qq.com/s/ROakvDKW2B3QKMlo7zH41Q