前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >redis灵魂拷问:聊一聊redis底层数据结构

redis灵魂拷问:聊一聊redis底层数据结构

作者头像
jinjunzhu
发布2020-09-25 14:12:50
4370
发布2020-09-25 14:12:50
举报
文章被收录于专栏:个人开发

redis能具有很好的性能表现,一个重要的原因就是redis底层的数据结构的使用非常巧妙,今天,我们来聊一聊这些数据结构。

基本数据类型和数据结构对应

我们知道,redis有5种数据类型,包括字符串、列表、集合、有序集合和字典。同时redis底层的数据结构有6种,包括动态字符串、双向链表、压缩列表(ziplist)、hash表、跳表(skip list)和整数数组。

下面我们就看一下对应关系:

1.毋庸置疑,字符串类型使用的底层数据结构就是动态字符串。

2.关于列表,如果同时满足下面条件,就使用压缩列表,否则使用双向链表。

列表中单个元素小于64字节

列表中元素个数少于 512

3.关于集合,如果同时满足下面条件,就使用有序整数数组,否则使用hash表。

集合中元素都是整数类型

集合中元素个数不超过512

4.关于有序集合,如果同时满足下面2个条件,就使用压缩列表,否则使用跳表。

集合中元素都小于64字节

集合中元素个数小于128个

注意:有序集合还有一个hash表用于保存集合中元素的分数,做ZSCORE操作时,查询的就是这个hash表,所以效率很高。看下t_zset.c文件中这段注释:

* The elements are added to a hash table mapping Redis objects to scores. * At the same time the elements are added to a skip list mapping scores * to Redis objects (so objects are sorted by scores in this "view").

5.关于字典类型,如果同时满足下面2个条件,就使用压缩列表,否则使用hash表。

字典中每个entry的key/value都小于64字节

字典中元素个数小于512个

关于压缩列表

压缩列表并不是基础的数据结构,而是redis自己实现的,压缩列表跟数组相似,在内存中也是一块儿连续的内存空间,结构如下:

zlbytes

zltail

zllen

entry

entry

entry

....

entry

zlend

可以看到,在这块连续内存空间中,表头有3个字段,zlbytes表示压缩列表长度,zltail表示表尾的偏移量,zllen则表示列表中元素的个数。所以,压缩列表时间复杂度跟数组一样,都是o(n)。它的优势是实现了压缩存储。

关于hash表

hash表这种数据结构我们并不陌生,尤其是我们java程序员,HashMap可以说是面试的高频考题。其实redis中的hash表思想跟java中HashMap非常相似,我们一起看一下。

1.全局hash表

大家知道hash是时间复杂度最低的数据结构,复杂度是o(1), 底层使用一个数据存放hash桶。redis为了提高查询效率,使用了一个全局hash表,支持快速查询,而hash的key和value保存了指向实际key和value的指针*key和*value。

2.hash冲突

redis处理hash冲突的方法使用的是链表法,即如果2个key的hashcode一样,则在同一个hash桶中用一个链表组织起来,链表查找的时间复杂度是o(n),所以当hash桶中的元素越来越多时,查找性能会下降。这时redis就会做rehash。

3.rehash操作

redis会申请一个新的hash表,大小一般是当前hash的2倍,然后把就hash表的元素拷贝到新的hash表中,之后释放就hash表的空间。跟java中HashMap不一样的是,redis是单线程的,所以不用考虑并发问题。

当然,如果redis一次性拷贝这么多的元素,肯定造成线程阻塞,访问效率急剧下滑。所以,redis使用了渐进式的拷贝,就是每当访问一个entry时,顺带把这个entry拷贝到新的hash表中。

关于跳表

上面我们讲了,redis把所有的元素都组织在一个hash表中,所以对于字符串类型,查找效率直接就是o(1),非常快。但是通过key查找到对应的value后,对于value是压缩列表、整形数组、双向链表的情况,时间复杂度都是o(n),性能还是比较差的。为了提高性能,redis引入了跳表这种数据结构。

跳表这种数据结构,结构看起来跟B+树非常像,见下图:

下面是一颗B+树:

下面是一个跳表:

上面的跳表第一层是一级索引,第二层是二级索引。从上图中看出,如果我们不加索引,查找10这个数字需要查询10次,使用了二级索引,查找10这个数字需要5次,而使用一级索引,需要查询3次。跳表插入、删除、查询的时间复杂度是o(logN),效率还是很高的。但是跳表需要存储额外的索引节点,会增加额外的空间开销,所以也是空间换时间的一种数据结构。

总结

了解了redis底层的数据结构,我们使用的时候也就心里有数了。

对于redis的list数据类型,它用到了压缩列表和双向链表,时间复杂度是o(n),我们做随机读写是不太合适的,但是pop和push效率高,作为队列是很好的选择。

数组和压缩列表虽然查询复杂度高,但是都是连续的内存空间,对内存存储和缓存还是非常友好的。

最后,个人对redis理解有限,欢迎大佬们批评指正。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-09-24,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 jinjunzhu 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
云数据库 Redis
腾讯云数据库 Redis(TencentDB for Redis)是腾讯云打造的兼容 Redis 协议的缓存和存储服务。丰富的数据结构能帮助您完成不同类型的业务场景开发。支持主从热备,提供自动容灾切换、数据备份、故障迁移、实例监控、在线扩容、数据回档等全套的数据库服务。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档