视频来源:原理篇[2,15]
文章目录
- 1.动态字符串SDS
- 1.1 内部结构:
- 2.IntSet
- 3.Dict
- 3.1 dict的内部结构
- 3.2 dict的扩容
- 4.ziplist压缩列表
- 5.QuickList
- 6.SkipList跳表
- 7.RedisObject对象
- 8.Redis的五种数据结构
- 8.1 String
- 8.2 List
- 8.3 Set
- 8.4 Zset 有序集合
- 8.5 Hash
底层实现
1.动态字符串SDS
Redis的key是字符串,value总是字符串或者字符串的集合。
redis没有直接使用c语言字符串。c语言字符串的缺点:获取字符串长度需要运算;非二进制安全;不可修改。
Redis自己构建的字符串,叫做简单动态字符串SDS。优点是可以直接获取长度,可以动态扩容。
1.1 内部结构:
动态扩容示例:
2.IntSet
是set集合的一种实现方式。基于整数数组来实现,特点:长度可变、有序等。
结构:
扩容过程:
3.Dict
3.1 dict的内部结构
Dict由三部分组成:哈希表(dict hash table)、哈希节点(dict entry)、字典(dict)。
3.2 dict的扩容
除了扩容,也会收缩
4.ziplist压缩列表
可以看成一种特殊的双端列表(它没有指针)。由特殊编码的连续内存块组成。可以在任意一端进行压入、弹出操作,并且复杂度为O(1)。
各种编码的最终目的就是节省内存。
依然是逐个遍历的。
entry中记录前一个节点的长度,这样可以支持倒序遍历。
ziplist可能引发 连锁更新 问题,原因:前一个节点的长度决定了这一个节点的previous_entry_length。新增/删除可能导致连锁更新的产生。
5.QuickList
ziplist申请连续内存空间时,如果内存占用较大,申请不到连续的,但我们要存的数据超过了ziplist的上限,怎么办?我们可以分片思想,用多个ziplist分别申请空间。那么分散的数据如何建立联系?
QuickList本质是双端链表,但每个节点都是一个ziplist。
通过配置,quicklist可以对ziplist的大小进行限制,还可以对节点ziplist进行压缩。
6.SkipList跳表
ziplist和quicklist都是为了节省内存,但是是链表是逐个遍历的。
skiplist特点:依然是链表
(1)元素升序排列;
(2)节点可能包含多个指针,指针跨度不同;
7.RedisObject对象
数据类型:string, list, set, zset, hash
8.Redis的五种数据结构
8.1 String
(1)RAW编码
需要申请、释放两次内存空间。RedisObject和SDS。
(2)EMBSTR编码
总共不超过64字节
(3)INT编码
8.2 List
List类型可以从首、尾操作列表中的元素。
使用quicklist实现list。
8.3 Set
无序、唯一
Redis中dict是哈希表。set采用HT编码(dict),dict中的key用来存储元素,value统一为null。
如果是存储整数,并且数量没超,就使用IntSet编码。
8.4 Zset 有序集合
score值越小,排名越靠前;member唯一。
方法一:使用dict+skiplist。两份数据冗余,可以实现功能,但是内存占用太高。
方法二:ziplist,数量有限时,节省内存。
但是它本身没有排序、没有键值对,需要业务逻辑来做。
排好序插入;元素element后面接着score
两种方式的转换:
8.5 Hash
默认采用ziplist方法。
超过大小,转为dict。(与zset相比,不用排序,所以不需要加跳表)