type
status
date
slug
summary
tags
category
icon
password
Redis（Remote Dictionary Server）是一种开源的内存数据结构存储系统，它提供了多种灵活且高效的数据结构，使得开发人员能够在应用程序中快速存储和检索数据。Redis的数据结构不仅仅是简单的键值对，它还支持更复杂的数据结构，如字符串、哈希表、列表、集合和有序集合等。这些数据结构不仅可以满足常见的数据存储需求，还可以支持更高级的操作，如排序、计数、范围查询等。
一、顶层数据结构1.1 常用的基本结构StringListSetHashSorted set1.2 额外的基本结构二、底层数据结构SDS与C字符串的区别链表字典跳跃表整数集合压缩列表（ZipList）三、对象系统类型编码和底层实现字符串对象编码转换字符串命令的实现列表对象编码转换哈希对象编码转换集合对象编码的转换有序集合对象编码的转换参考书籍
一、顶层数据结构
1.1 常用的基本结构
String
Redis 字符串存储字节序列，包括文本、序列化对象和二进制数组。 因此，字符串是最基本的 Redis 数据类型。 它们通常用于缓存，但它们支持额外的功能，让您也可以实现计数器并执行按位操作。
By default, a single Redis string can be a maximum of 512 MB.
常用命令：
获取或者设置字符串
- SET
- SETNX
- GET
- MGET
计数器
- INCRBY
- INCR
- DECR
- DECRBY
List
用于实现队列或者栈
The max length of a Redis list is 2^32 - 1 (4,294,967,295) elements.
常用命令
- LPUSH
- LPOP
- LLEN
- LMOVE
- LTRIM
Set
无序无重复集合。
场景：去重、集合操作，抽奖
The max size of a Redis set is 2^32 - 1 (4,294,967,295) members.
常用命令
- SADD
- SREM
- SISMEMBER 测试一个String是否是set成员
- SINTER 返回两个set的交集
- SCARD 返回set数量
SMEMBER 在set数量比较大的情况下慎用，考虑使用SSCAN用于替换
Hash
用于记录键值对。也可以用于基础对象以及它的计数器，或者其他。
Every hash can store up to 4,294,967,295 (2^32 - 1) field-value pairs. In practice, your hashes are limited only by the overall memory on the VMs hosting your Redis deployment.
常用命令
- HSET
- HGET
- HMGET
- HINCREBY
HKEYS、HVALS、HGETALL O(N) 复杂度
Sorted set
有序Set，带有一个权重的值。
场景：排行榜、限速器
常用命令
- ZADD
- ZRANGE
- ZRANK 获取zset 中某个键的排行，正序（低到高）
- ZREVRANK 获取zset 中某个键的排行，倒序 （高到低）
1.2 额外的基本结构
HyperLogLog
Bitmap
Geospatial indexe
二、底层数据结构
SDS、双端链表、字典、压缩列表、整数集合
SDS与C字符串的区别
- 常数复杂度获取字符串长度
- 杜绝缓冲区溢出
- 减少修改字符串时带来的内存重新分配次数
- 二进制安全
- 兼容部分C字符串函数
Redis只会使用C字符串作为字面量，在大多数情况下，Redis使用SDS（Simple Dynamic String，简单动态字符串）作为字符串表示。
链表
Redis的链表实现的特性
- 双端：
- 无环：
- 带表头指针和表尾指针：获取链表头尾的时间复杂度 O(1)
- 带链表长度计数器：使用 len 属性获取，O(1) 时间复杂度
- 多态：链表节点使用 void* 指针保存节点值，可以保存各种不同类型的值
字典
hashtable
字典
ht属性数一个包含两个项的数组，数组中的每个项都是一个
dictht 哈希表，一般情况下，字典只使用 ht[0] 哈希表， ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。如果没有在进行
rehash 那么它的值为 -1哈希算法
Redis 使用 MurmurHash2 算法来计算哈希值。随机性分布，且计算速度快。
解决键冲突
链地址法，同一个哈希值的，每个新节点都放置在头指针位置。（因为没有尾指针，考虑到性能
）
服务一般是分多次进行 rehash，也就是渐进性hash。这里用到了 rehashidx 索引，也就是时候一个一个索引进行 迁移。
跳跃表
zskiplist 和 zskiplistNode 两个结构组成
前者保存跳跃表信息（表头节点、表尾节点、长度）
后者是跳跃表节点
整数集合
升级（超过 encoding 的数值插入后，会进行升级，整个数组会被重新分配）
好处：提升整数集合的灵活性，尽可能节约内存
降级（不支持降级）
压缩列表（ZipList）
连锁更新
连锁更新在最坏情况下需要对压缩列表执行N次空间重分配操作，而每次空间重分配的最坏复杂度为O(N)，所以连锁更新的最坏复杂度为 O(N^2)。
尽管这个复杂度很高，但它真正出现的几率是很低的：
- 首先，压缩列表里要恰好有多个连续的、长度介于250-253字节之间的节点，连锁更新才可能引发，在实际中，这种情况并不多见。
- 其次，即使出现连锁更新，单只要被更新的节点数量不多，就不会对性能造成任何影响。
三、对象系统
Redis中每个对象都由一个 redisObject 结构表示
类型
编码和底层实现
字符串对象
编码有三种：
- int (可以用 long 类型保存的整数)
- raw （可以用long double 类型保存的浮点数）
- embstr （字符串值，或者因为长度太大而没办法用 Long 类型表示的整数，又或者因为长度太大而没有办法用 long double 类型表示的浮点数）
如果字符串对象保存的是一个字符串值，并且这个字符串的长度小于等于32字节，那么字符串对象将使用 emstr 编码的方式来保存这个字符串值。
embstr 与 raw 区别：
- 大小的区别
- 修改时的区别
- 前者是只需分配一次连续空间给 redisObject 和 sdshdr，相应的，释放内存也是一次
- 后者需要分配两次空间，一个给 redisObject，一个给 sdshdr，释放内存两次
编码转换
embstr 是只读，如果修改字符串，那么 embstr 会变成 raw 编码在再进行修改
字符串命令的实现
列表对象
编码有：
- ziplist
- linkedlist
编码转换
当列表对象可以同时满足以下条件时，列表对象使用 ziplist 编码：
- 列表对象保存的所有字符串元素的长度都小于64字节；
- 列表对象保存的元素数量小于521个；
不能满足这两个条件的列表对象需要使用 linkedlist 编码。
哈希对象
编码有：
- ziplist
- hashtable
ziplist底层
hashtable底层
编码转换
当哈希对象可以同时满足以下两个条件时，哈希对象使用ziplist编码：
- 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节
- 哈希对象保存的键值对数量小于512个
集合对象
编码：
- intset
- hashtable
编码的转换
当集合对象可以同时满足以下两个条件时，对象使用intset编码：
- 集合对象保存的所有元素都是整数值
- 集合对象保存的元素数量不超过512个
有序集合对象
编码：
- ziplist
- skiplist
编码的转换
当有序集合对象可以同时满足以下两个条件时，使用ziplist编码：
- 有序集合保存的元素数量小于128个
- 有序集合保存的所有元素的成员的长度都小于64字节
否则，使用 skiplist 编码
参考书籍
《Redis设计与实现》
- 作者:eachenkuang
- 链接:https://kuangyichen.com/article/redis-data-structure
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。