✅InnoDB为什么不用跳表，Redis为什么不用B+树？

典型回答

Innodb是MySQL的执行引擎，MySQL是一种关系型数据库，而Redis是一种非关系型数据库。这两者之间比较大的区别是：关系型数据库以表的形式进行存储数据，而非关系型数据库以Key-value的形式存储数据。

MySQL是基于磁盘存储的，Redis是基于内存存储的。而B+树是一种磁盘IO友好型的数据结构，跳表则是一种内存友好型的数据结构。

为什么说B+树是磁盘IO友好的呢？

首先，B+树的叶子节点形成有序链表，可以方便地进行范围查询操作。对于磁盘存储来说，顺序读取的效率要高于随机读取，因为它可以充分利用磁盘预读和缓存机制，减少磁盘 I/O 的次数。

其次，由于B+树的节点大小是固定的，因此可以很好地利用磁盘预读特性，一次性读取多个节点到内存中，这样可以减少IO操作次数，提高查询效率。

还有就是，B+树的叶子节点都存储数据，而非数据和指针混合，所以叶子节点的大小是固定的，而且节点的大小一般都会设置为一页的大小，这就使得节点分裂和合并时，IO操作很少，只需读取和写入一页。

所以，B+树在设计上考虑了磁盘存储的特点和性能优化，我们曾经分析过，当Innodb中存储2000万数据的时候，只需要3次磁盘就够了。

而跳表就不一样了，跳表的索引节点通过跳跃指针连接，形成多级索引结构。这导致了跳表的索引节点在磁盘上存储时会出现数据分散的情况，即索引节点之间的物理距离可能较远。对于磁盘存储来说，随机访问分散的数据会增加磁头的寻道时间，导致磁盘 I/O 的性能下降。

那么，为啥Redis要用跳表实现ZSET呢（不只是跳表，详见下面链接）？而不是B+树呢？

因为Redis是一种基于内存的数据结构，他不需要考虑磁盘IO的性能问题，所以，他完全可以选择一个简单的数据结构，并且性能也能接受的，那么跳表就很合适，

因为跳表相对于B+树来说，更简单。相比之下，B+树作为一种复杂的索引结构，需要考虑节点分裂和合并等复杂操作，增加了实现和维护的复杂度。

而且，Redis的有序集合经常需要进行插入、删除和更新操作。跳表在动态性能方面具有良好的表现，特别是在插入和删除操作上。相比之下，B+树的插入和删除需要考虑平衡性，所以还是成本挺高的。

原文: https://www.yuque.com/hollis666/xkm7k3/lcz0grveudyoa16b