写点什么

Redis 学习笔记 08:数据结构与对象小结

发布于: 2021 年 01 月 20 日
Redis 学习笔记 08:数据结构与对象小结

我是架构精进之路,点击上方“关注”,坚持每天为你分享技术干货,私信我回复“01”,送你一份程序员成长进阶大礼包。


通过前面几篇文章,主要介绍了 Redis 基础数据结构知识。

Redis 有 5 个基本数据结构,string、list、hash、set 和 zset。它们是日常开发中使用频率非常高应用最为广泛的数据结构,需要吃透才行。

string

Redis 的字符串是动态字符串,是可以修改的字符串,内部结构实现上类似于 Java 的 ArrayList,采用预分配冗余空间的方式来减少内存的频繁分配,如图中所示,内部为当前字符串实际分配的空间 capacity 一般要高于实际字符串长度 len。当字符串长度小于 1M 时,扩容都是加倍现有的空间,如果超过 1M,扩容时一次只会多扩 1M 的空间。需要注意的是字符串最大长度为 512M。

计数器

如果字符串的内容是一个整数,那么还可以将字符串当成计数器来使用。

计数器是有范围的,它不能超过 Long.Max,不能低于 Long.MIN

过期和删除 字符串可以使用 del 指令进行主动删除,可以使用 expire 指令设置过期时间,到点会自动删除,这属于被动删除。可以使用 ttl 指令获取字符串的寿命。

list


Redis 将列表数据结构命名为 list 而不是 array,是因为列表的存储结构用的是链表而不是数组,而且链表还是双向链表。因为它是链表,所以随机定位性能较弱,首尾插入删除性能较优。如果 list 的列表长度很长,使用时我们一定要关注链表相关操作的时间复杂度。

负下标 链表元素的位置使用自然数 0,1,2,....n-1 表示,还可以使用负数-1,-2,...-n 来表示,-1 表示「倒数第一」,-2 表示「倒数第二」,那么-n 就表示第一个元素,对应的下标为 0。

队列/堆栈 链表可以从表头和表尾追加和移除元素,结合使用 rpush/rpop/lpush/lpop 四条指令,可以将链表作为队列或堆栈使用,左向右向进行都可以

快速列表

如果再深入一点,你会发现 Redis 底层存储的还不是一个简单的 linkedlist,而是称之为快速链表 quicklist 的一个结构。首先在列表元素较少的情况下会使用一块连续的内存存储,这个结构是 ziplist,也即是压缩列表。它将所有的元素紧挨着一起存储,分配的是一块连续的内存。当数据量比较多的时候才会改成 quicklist。因为普通的链表需要的附加指针空间太大,会比较浪费空间。比如这个列表里存的只是 int 类型的数据,结构上还需要两个额外的指针 prev 和 next。所以 Redis 将链表和 ziplist 结合起来组成了 quicklist。也就是将多个 ziplist 使用双向指针串起来使用。这样既满足了快速的插入删除性能,又不会出现太大的空间冗余。

hash


哈希等价于 Java 语言的 HashMap 或者是 Python 语言的 dict,在实现结构上它使用二维结构,第一维是数组,第二维是链表,hash 的内容 key 和 value 存放在链表中,数组里存放的是链表的头指针。通过 key 查找元素时,先计算 key 的 hashcode,然后用 hashcode 对数组的长度进行取模定位到链表的表头,再对链表进行遍历获取到相应的 value 值,链表的作用就是用来将产生了「hash 碰撞」的元素串起来。Java 语言开发者会感到非常熟悉,因为这样的结构和 HashMap 是没有区别的。哈希的第一维数组的长度也是 2^n。

set


Java 程序员都知道 HashSet 的内部实现使用的是 HashMap,只不过所有的 value 都指向同一个对象。Redis 的 set 结构也是一样,它的内部也使用 hash 结构,所有的 value 都指向同一个内部值。

  • 增加元素 可以一次增加多个元素

  • 读取元素 使用 smembers 列出所有元素,使用 scard 获取集合长度,使用 srandmember 获取随机 count 个元素,如果不提供 count 参数,默认为 1

  • 删除元素 使用 srem 删除一到多个元素,使用 spop 删除随机一个元素

  • 判断元素是否存在 使用 sismember 指令,只能接收单个元素

sorted set

SortedSet(zset)是 Redis 提供的一个非常特别的数据结构,一方面它等价于 Java 的数据结构 Map<String, Double>,可以给每一个元素 value 赋予一个权重 score,另一方面它又类似于 TreeSet,内部的元素会按照权重 score 进行排序,可以得到每个元素的名次,还可以通过 score 的范围来获取元素的列表。

zset 底层实现使用了两个数据结构,第一个是 hash,第二个是跳跃列表,hash 的作用就是关联元素 value 和权重 score,保障元素 value 的唯一性,可以通过元素 value 找到相应的 score 值。跳跃列表的目的在于给元素 value 排序,根据 score 的范围获取元素列表。

跳跃列表

zset 内部的排序功能是通过「跳跃列表」数据结构来实现的,它的结构非常特殊,也比较复杂。


- END -



作者:架构精进之路,专注软件架构研究,技术学习与个人成长,关注并私信我回复“01”,送你一份程序员成长进阶大礼包。



Thanks for reading!


发布于: 2021 年 01 月 20 日阅读数: 20
用户头像

坚持分享接地气儿的架构技术文章! 2018.02.26 加入

同名微信公众号「架构精进之路」,专注软件架构研究,技术学习与职业成长!坚持原创总结、沉淀和分享,希望能带给大家一些引导和启发,感谢各位的支持(关注、点赞、分享)!

评论

发布
暂无评论
Redis 学习笔记 08:数据结构与对象小结