扫码关注微信公众号

回复“面试手册”,获取本站PDF版

回复“简历”,获取高质量简历模板

回复“加群”,加入程序员交流群

回复“电子书”,获取程序员类电子书

当前位置: 计算机基础 > Redis高频面试题 > 8.Redis的数据结构有哪些?

很多人都会把数据结构和数据类型混为一谈,包括很多面试官问的时候也没有刻意区分这两个。Redis的数据结构比较多,篇幅有限,这里只重点介绍面试常问的跳跃表。

Redis的数据结构有简单动态字符串链表字典跳跃表整数集合压缩列表等。

简单动态字符串:大家都知道,Redis的底层是用C语言编写,但Redis并没有直接使用C语言传统的字符串表示,而是构建了一种名为简单动态字符串的抽象类型。

链表:链表提供了高效的节点重排能力,以及顺序性的节点访问方式,并且可以通过增删节点来灵活地调整链表的长度。链表是列表的底层实现之一

字典:字典,又称为符号表(symbol table)、关联数组(associativearray)或映射(map),是一种用于保存键值对(key-value pair)的抽象数据结构。字典在Redis中的应用相当广泛,比如Redis的数据库就是使用字典来作为底层实现的,对数据库的增、删、查、改操作也是构建在对字典的操作之上的。

整数集合: 整数集合(intset)是集合键的底层实现之一,当一个集合只包含整数值元素,并且这个集合的元素数量不多时,Redis就会使用整数集合作为集合键的底层实现。

压缩列表(ziplist):压缩列表是Redis为了节约内存而开发的,是由一系列特殊编码的连续内存块组成的顺序型(sequential)数据结构。

对象:可能看到这里,很多人在想Redis的数据结构和数据类型的区别,其实上面介绍的是Redis的底层数据结构,但Redis并没有直接使用这些数据结构来实现键值对数据库,而是基于这些数据结构创建了一个对象系统,这个系统包含字符串对象、列表对象、哈希对象、集合对象有序集合对象这五种类型的对象,每种对象都用到了至少一种我们前面所介绍的数据结构,是不是这就和前面对上了。

看到这里很多人会好奇,为什么不直接使用这些底层数据结构,而是要创建对象系统。对象系统主要有以下优点:

  • 通过这五种不同类型的对象,Redis可以在执行命令之前,根据对象的类型来判断一个对象是否可以执行给定的命令。
  • 我们可以针对不同的使用场景,为对象设置多种不同的数据结构实现,从而优化对象在不同场景下的使用效率。
  • 实现了基于引用计数技术的内存回收机制,当程序不再使用某个对象的时候,这个对象所占用的内存就会被自动释放,了解Java虚拟机的垃圾回收机制看到这里是不是很熟悉。
  • edis还通过引用计数技术实现了对象共享机制,这一机制可以在适当的条件下,通过让多个数据库键共享同一个对象来节约内存。

对象这部分占了比较大的篇幅,其实面试中问的也不多,但为了更方便理解,介绍地多些。顺便看下这些底层数据结构和对象系统的对应关系。

Redis数据类型的底层数据结构
Redis数据类型的底层数据结构

最后介绍下面试中常问的跳跃表。

跳跃表(skiplist):跳跃表(skiplist)是一种有序数据结构,它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。跳跃表支持平均O(logN)、最坏O(N)复杂度的节点查找,还可以通过顺序性操作来批量处理节点。跳跃表作是序集合键的底层实现之一

和链表、字典等数据结构被广泛地应用在Redis内部不同,Redis只在两个地方用到了跳跃表,一个是实现有序集合键,另一个是在集群节 点中用作内部数据结构,除此之外,跳跃表在Redis里面没有其他用途。

跳跃表本质上采用的是一种空间换时间的策略,是一种可以可以进行二分查找有序链表,跳表在原有的有序链表上增加了多级索引,通过索引来实现快速查询。跳表不仅能提高搜索性能,同时也可以提高插入和删除操作的性能。

这是一个原始的有序列表,时间复杂度为O(n)。

为了提高查找效率,可以对链表建立一级索引,如下图,在之前找到11这个元素需要遍历6个节点,现在需要5个。链表越长,效率提升越明显。

为了继续提高查找效率可以继续增加索引

对于理想的跳表,每向上一层索引节点数量都是下一层的1/2,跳表的时间复杂度为o(logn),空间复杂度为o(n),虽然是空间换时间的策略,这里举例存储的只是数字,如果是存储比较大的对象,浪费的空间就不值得一提了,因为索引结点只需要存储关键值和几个指针,并不需要存储对象。

跳表相比于红黑树的优点(redis为什么用跳表不同红黑树):

  • 内存占用更少,自定义参数化决定使用多少内存
  • 查询性能至少不比红黑树差
  • 简单更容易实现和维护

上面这三个优点是我在一篇博客中看到,这个问题redis作者本人也回应过。我这蹩脚的英文水平就不翻译了,以免跑偏了。

  • They are not very memory intensive. It’s up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.
  • A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.
  • They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.

最后,说下Redis中的跳跃表和普通的跳跃表有什么区别?

  • Redis中的跳跃表分数(score)允许重复,即跳跃表的key允许重复,如果分数重复,还需要根据数据内容来进字典排序。普通的跳跃表是不支持的。
  • 第1层链表不是一个单向链表,而是一个双向链表。这是为了方便以倒序方式获取一个范围内的元素。
  • 在Redis的跳跃表中可以很方便地计算出每个元素的排名。

篇幅有限,关于跳表的实现细节就不过多介绍了,有兴趣的同学可以自行了解,本小节部分内容参考《Redis设计与实现》


点击面试手册,获取本站面试手册PDF完整版