江苏龙网

  1. 主页 > 生活百科 > >

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

Redis

Innodb是MySQL的执行引擎 ， MySQL是一种关系型数据库 ， 而redis是一种非关系型数据库 。这两者之间比较大的区别是：关系型数据库以表的形式进行存储数据 ， 而非关系型数据库以Key-value的形式存储数据 。【InnoDB为什么不用跳表，Redis为什么不用B+树？】

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

文章插图
作为开发人员 ， 我们每天都要开发大量的接口 ， 其中包括了读接口和写接口 ， 而对于写接口来说 ， 除了要保证他的性能、可用性以外 ， 还需要有一个重要的问题 ， 那就是考虑如何保证接口的幂等性
Innodb是MySQL的执行引擎 ， MySQL是一种关系型数据库 ， 而Redis是一种非关系型数据库 。这两者之间比较大的区别是：关系型数据库以表的形式进行存储数据 ， 而非关系型数据库以Key-value的形式存储数据 。
在InnoDB中 ， 索引是采用B+树实现的 ， 在Redis中 ， ZSET是采用跳表（不只是跳表）实现的 ， 无论是B+树 ， 还是跳表 ， 都是性能很好的数据结构 ， 那么 ， 为什么InnoDB为什么不用跳表 ， Redis为什么不用B+树？
我们都知道 ， MySQL是基于磁盘存储的 ， Redis是基于内存存储的 。
而之所以Innodb用B+树 ， 主要是因为B+树是一种磁盘IO友好型的数据结构 ， 而Redis使用跳表 ， 是因为跳表则是一种内存友好型的数据结构 。
B+树次磁盘友好？首先 ， B+树的叶子节点形成有序链表 ， 可以方便地进行范围查询操作 。对于磁盘存储来说 ， 顺序读取的效率要高于随机读取 ， 因为它可以充分利用磁盘预读和缓存机制 ， 减少磁盘 I/O 的次数 。
其次 ， 由于B+树的节点大小是固定的 ， 因此可以很好地利用磁盘预读特性 ， 一次性读取多个节点到内存中 ， 这样可以减少IO操作次数 ， 提高查询效率 。
还有就是 ， B+树的叶子节点都存储数据 ， 而非数据和指针混合 ， 所以叶子节点的大小是固定的 ， 而且节点的大小一般都会设置为一页的大小 ， 这就使得节点分裂和合并时 ， IO操作很少 ， 只需读取和写入一页 。
所以 ， B+树在设计上考虑了磁盘存储的特点和性能优化 ， 我曾经分析过 ， 当Innodb中存储2000万数据的时候 ， 只需要3次磁盘就够了 。
而跳表就不一样了 ， 跳表的索引节点通过跳跃指针连接 ， 形成多级索引结构 。这导致了跳表的索引节点在磁盘上存储时会出现数据分散的情况 ， 即索引节点之间的物理距离可能较远 。对于磁盘存储来说 ， 随机访问分散的数据会增加磁头的寻道时间 ， 导致磁盘 I/O 的性能下降 。
为啥Redis用跳表？既然B+树这么多优点 ， 为啥Redis要用跳表实现ZSET呢（不只是跳表 ， 详见下面链接）？而不是B+树呢？
主要是因为Redis是一种基于内存的数据结构 。他其实不需要考虑磁盘IO的性能问题 ， 所以 ， 他完全可以选择一个简单的数据结构 ， 并且性能也能接受的  ， 那么跳表就很合适 。
因为跳表相对于B+树来说 ， 更简单 。相比之下 ， B+树作为一种复杂的索引结构 ， 需要考虑节点分裂和合并等复杂操作 ， 增加了实现和维护的复杂度 。
而且 ， Redis的有序集合经常需要进行插入、删除和更新操作 。跳表在动态性能方面具有良好的表现 ， 特别是在插入和删除操作上 。相比之下 ， B+树的插入和删除需要考虑平衡性 ， 所以还是成本挺高的 。
总结以上 ， 就是关于《InnoDB为什么不用跳表 ， Redis为什么不用B+树？》这个问题的我的一些理解 ， 其实这个问题想要回答好还挺难的 。
首先要知道为啥Innodb使用红黑树 ， 其次还要了解Redis中的Zset数据结构 ， 还需要知道跳表的原理 。




    推荐阅读


    上一篇：全世界海外华人有多少个

    下一篇：跨境电商文案、翻译、模特受冲击 ChatGPT是如何把饭碗抢走的？