Redis经典五大类型源码及底层实现

面试常问的

Redis对象object.c

字符串t_string.c

列表t_list.c

字典t_hash.c

集合及有序集合t_set.c和t_zset.c

数据流t_stream.c

---

Redis基本数据结构（骨架）

简单动态字符串sds.c

整数集合intset.c

压缩列表ziplist.c

快速链表quicklist.c

listpack

字典dict.c

---

Redis数据库的实现

数据库的底层实现db.c

持久化rdb.c和aof.c

---

Redis服务端和客户端

事件驱动ae.c和ae_epoll.c

网络连接anet.c和networking.c

服务端程序server.c

客户端程序redis-cli.c

---

其他

主从复制replication.c

哨兵sentinel.c

集群cluster.c

其他数据结构，如hyperloglog.c、geo.c等

其他功能，如pub/sub、Lua脚本

源码分析

Redis中每个对象都是一个redisObject结构

每个键值对都会有一个digtEntry(源码位置:dict.h)

重点:从dictEntry到RedisObjectZ

经典5大数据结构解析

//edis结构
//*redis6相关的底层模型和结构*string = sDs
*set = intset + hashtable
*zset = skipList + zipList
*list = quickList + zipList
*hash = hashtable + zipList
*
===================================
*
*redis7相关的底层模型和结构
*string = SDS
*set = intset + hashtable
*zset = skipList + listpack紧凑列表
*List = quicklist
*Hash = hashtable + Listpack紧凑列表
*/

debug 的开启

String数据结构介绍

SDS简单动态字符串

Hash数据结构介绍

redis6

hash-max-ziplist-entries:使用压缩列表保存时哈希集合中的最大元素个数。
hash-max-ziplist-value:使用压缩列表保存时哈希集合中单个元素的最大长度。

结论

1.哈希对象保存的键值对数量小于512个;
2.所有的键值对的健和值的字符串长度都小于等于64byte (一个英文字母一个字节)
时用ziplist，反之用hashtable
ziplist升级到hashtable可以，反过来降级不可以（一旦从压缩列表转为了哈希表，Hash类型就会一直用哈希表进行保存而不会再转回压缩列表了。在节省内存空间方面哈希表就没有压缩列表高效了。）

源码分析

hset命令解读

ziplist.c

ziplist为了节省内存，采用了紧凑的连续存储。
ziplist是一个双向链表，可以在时间复杂度为O(1）下从头部、尾部进行 pop或push。
新增或更新元素可能会出现连锁更新现象(致命缺点导致被listpack替换)。
不能保存过多的元素，否则查询效率就会降低，数量小和内容小的情况下可以使用。

redis7

源码

明明有ziplist了，为什么出来一个listpack紧凑列表?

Ziplsit的连锁更新问题

结论：listpack 是Redis 设计用来取代掉ziplist 的数据结构，它通过每个节点记录自己的长度且放在节点的尾部，来彻底解决掉了ziplist存在的连锁更新的问题

ziplist内存布局VS listpack内存布局

List数据结构介绍

Set数据结构介绍

ZSet数据结构介绍

总结

skiplist跳表

跳表是可以实现二分查找的有序链表

skiplist是一种以空间换取时间的结构。

由于链表，无法进行二分查找，因此借鉴数据库索引的思想，提取出链表中关键节点(索引)，先在关键节点上查找，再进入下层链表查找，提取多层关键节点，就形成了跳跃表

but

由于索引也要占据一定空间的，所以，索引添加的越多，空间占用的越多

总结来讲跳表=链表＋多级索引

跳表时间+空间复杂度介绍

---