InnoDB为什么不用跳表,Redis为什么不用B+树?

2023-06-08 0 1,198

InnoDB为什么不用跳表,Redis为什么不用B+树?

作者 l Hollis来源 l Hollis(ID:hollischuang)

作为开发人员,我们每天都要开发大量的接口,其中包括了读接口和写接口,而对于写接口来说,除了要保证他的性能、可用性以外,还需要有一个重要的问题,那就是考虑如何保证接口的幂等性

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数据结构,还需要知道跳表的原理。

银河教育 网络技术 InnoDB为什么不用跳表,Redis为什么不用B+树? https://www.edufly.cn/data/tutorial/822.html

常见问题

相关文章

发表评论
暂无评论
官方客服团队

为您解决烦忧 - 24小时在线 专业服务