[由零开始]Redis数据类型与底层数据结构


数据类型与底层数据结构
1.数据类型

Redis是一个Key-Value的存储系统,使用ANSI C语言编写。
key的类型是字符串。

常用的:string字符串类型、list列表类型、set集合类型、sortedset(zset)有序集合类型、hash类
型。
不常见的:bitmap位图类型、geo地理位置类型。
Redis5.0新增一种:stream类型
注意:Redis中命令是忽略大小写,(set SET),key是不忽略大小写的 (NAME name)

2. Redis数据类型分析
2.1 Redis的Key的设计

    用:分割
    把表名转换为key前缀, 比如: user:
    第二段放置主键值
    第三段放置列名
    比如:用户表user, 转换为redis的key-value存储
userid username password email

1
zhangf
111111
zhangf@163.com

username 的 key: user:9:username
{userid:9,username:zhangf}
email的key user:9:email

2.2 String字符串类型

String能表达3种值的类型:字符串、整数、浮点数

2.2 .1 常见操作命令:

命令名称 命令描述

set
set key value
赋值

get
get key
取值

getset
getset key value
取值并赋值

setnx
setnx key value
当value不存在时采用赋值
set key value NX PX 3000 原子操作,px 设置毫秒数

append
append key value
向尾部追加值

strlen
strlen key
获取字符串长度

incr
incr key
递增数字

incrby
incrby key increment
增加指定的整数

decr
decr key
递减数字

decrby
decrby key decrement
减少指定的整数

2.2 .2 应用场景:

key和命令是字符串
普通的赋值
incr用于乐观锁
incr:递增数字,可用于实现乐观锁 watch(事务)
setnx用于分布式锁
当value不存在时采用赋值,可用于实现分布式锁

127.0.0.1:6379> setnx name zhangf #如果name不存在赋值
(integer) 1
127.0.0.1:6379> setnx name zhaoyun #再次赋值失败
(integer) 0
127.0.0.1:6379> get name
"zhangf"

2.3 list列表类型

list列表类型可以存储有序、可重复的元素
获取头部或尾部附近的记录是极快的
list的元素个数最多为2^32-1个(40亿)

2.3 .1 常见操作命令:

命令 说明

lpush
从左侧插入列表

lpop
从列表左侧取出

rpush
从右侧插入列表

rpop
从列表右侧取出

lpushx
将值插入到列表头部

rpushx
将值插入到列表尾部

blpop
从列表左侧取出,当列表为空时阻塞,可以设置最大阻塞时
间,单位为秒

brpop
从列表右侧取出,当列表为空时阻塞,可以设置最大阻塞时
间,单位为秒

llen
获得列表中元素个数

lindex
获得列表中下标为index的元素 index从0开始

lrange
返回列表中指定区间的元素,区间通过start和end指定

lrem
可删除列表中与value相等的元素
当count>0时, lrem会从列表左边开始删除;当count<0时,
lrem会从列表后边开始删除;当count=0时, lrem删除所有值
为value的元素

lset
将列表index位置的元素设置成value的值

ltrim
对列表进行修剪,只保留start到end区间

rpoplpush
从key1列表右侧弹出并插入到key2列表左侧

brpoplpush
从key1列表右侧弹出并插入到key2列表左侧,会阻塞

linsert
将value插入到列表,且位于值pivot之前或之后

2.3 .2 应用场景:

作为栈或队列使用
列表有序可以作为栈和队列使用
可用于各种列表,比如用户列表、商品列表、评论列表等

2.4 set集合类型

​ Set:无序、唯一元素
​ 集合中最大的成员数为 2^32 -

2.4 .1 常见操作命令:

命令 说明

sadd
为集合添加元素

smembers
显示集合中所有元素 无序

scard
返回集合中元素的个数

spop
随即删除n个元素,并返回对应删除的n个元素 n—>数字

smove
从一个集合中向另一个集合移动元素 smove source(原始集合) destination(目标集合) member(元素)

srem
从集合中删除指定的member(1-n个)

sismember
判断一个集合中是否含有这个元素

srandmember
随机返回元素 默认返回一个,可以手动指定返回元素的个数

sdiff
去掉第一个集合中其它集合含有的相同元素

sinter
求交集

sunion
求和集

2.4 .2 应用场景:

适用于不能重复的且不需要顺序的数据结构
比如:关注的用户,还可以通过spop进行随机抽奖

2.5 sortedset有序集合类型

SortedSet(ZSet) 有序集合: 元素本身是无序不重复的
每个元素关联一个分数(score)
可按分数排序,分数可重复

2.5 .1 常见操作命令:

命令 说明

zadd
添加一个有序集合元素

zcard
返回集合的元素个数

zrange
返回一个范围内的元素(zrange zset 0 -1 withscores 遍历所有并展示分数)

zrangebyscore
按照分数查找一个范围内的元素

zrank
返回排名(返回index)

zrevrank
倒序排名(返回index)

zscore
显示某一个元素的分数

zrem
移除某一个元素

zincrby
给某个特定元素加分

2.5 .2 应用场景:

由于可以按照分值排序,所以适用于各种排行榜。比如:点击排行榜、销量排行榜、关注排行榜等。

2.6 hash类型(散列表)

Redis hash 是一个 string 类型的 field 和 value 的映射表,它提供了字段和字段值的映射。
每个 hash 可以存储 2^32 - 1 键值对(40多亿)。

[由零开始]Redis数据类型与底层数据结构

2.6 .1 常见操作命令:

命令 说明

hset
设置一个key/value对

hget
获得一个key对应的value

hgetall
获得所有的key/value对

hdel
删除某一个key/value对

hexists
判断一个key是否存在

hkeys
获得所有的key

hvals
获得所有的value

hmset
设置多个key/value

hmget
获得多个key的value

hsetnx
设置一个不存在的key的值

hincrby
为value进行加法运算

hincrbyfloat
为value加入浮点值

2.6 .2 应用场景:

对象的存储 ,表数据的映射

2.7 bitmap位图类型

bitmap是进行位操作的
通过一个bit位来表示某个元素对应的值或者状态,其中的key就是对应元素本身。
bitmap本身会极大的节省储存空间。

2.7 .1 常见操作命令:

命令 说明

setbit
设置key在offset处的bit值(只能是0或者
1)。

getbit
获得key在offset处的bit值

bitcount
获得key的bit位为1的个数

bitpos
返回第一个被设置为bit值的索引值

bitop
对多个key 进行逻辑运算后存入destkey

2.7 .1 应用场景:

用户每月签到,用户id为key , 日期作为偏移量 1表示签到
统计活跃用户, 日期为key,用户id为偏移量 1表示活跃
查询用户在线状态, 日期为key,用户id为偏移量 1表示在线

2.8 geo地理位置类型

geo是Redis用来处理位置信息的。在Redis3.2中正式使用。主要是利用了Z阶曲线、Base32编码和
geohash算法

Z阶曲线
在x轴和y轴上将十进制数转化为二进制数,采用x轴和y轴对应的二进制数依次交叉后得到一个六位数编
码。把数字从小到大依次连起来的曲线称为Z阶曲线,Z阶曲线是把多维转换成一维的一种方法。

[由零开始]Redis数据类型与底层数据结构

Base32编码

Base32这种数据编码机制,主要用来把二进制数据编码成可见的字符串,其编码规则是:任意给定一
个二进制数据,以5个位(bit)为一组进行切分(base64以6个位(bit)为一组),对切分而成的每个组进行编
码得到1个可见字符。Base32编码表字符集中的字符总数为32个(0-9、b-z去掉a、i、l、o),这也是
Base32名字的由来。

[由零开始]Redis数据类型与底层数据结构

geohash算法

Gustavo在2008年2月上线了geohash.org网站。Geohash是一种地理位置信息编码方法。 经过
geohash映射后,地球上任意位置的经纬度坐标可以表示成一个较短的字符串。可以方便的存储在数据
库中,附在邮件上,以及方便的使用在其他服务中。以北京的坐标举例,[39.928167,116.389550]可以
转换成wx4g0s8q3jf9 。
Redis中经纬度使用52位的整数进行编码,放进zset中,zset的value元素是key,score是GeoHash的
52位整数值。在使用Redis进行Geo查询时,其内部对应的操作其实只是zset(skiplist)的操作。通过zset
的score进行排序就可以得到坐标附近的其它元素,通过将score还原成坐标值就可以得到元素的原始坐
标。

2.8 .1 常见操作命令:

命令 说明

geoadd
添加地理坐标

geohash
返回标准的geohash串

geopos
返回成员经纬度

geodist
计算成员间距离

georadiusbymember
根据成员查找附近的成员

2.8 .2 应用场景:

记录地理位置
计算距离
查找"附近的人"

2.9 geo地理位置类型

stream是Redis5.0后新增的数据结构,用于可持久化的消息队列。
几乎满足了消息队列具备的全部内容,包括:

消息ID的序列化生成
消息遍历
消息的阻塞和非阻塞读取
消息的分组消费
未完成消息的处理
消息队列监控

每个Stream都有唯一的名称,它就是Redis的key,首次使用xadd 指令追加消息时自动创建。

2.9 .1 常见操作命令:

命令 说明

xadd
将指定消息数据追加到指定队列(key)中,*
表示最新生成的id(当前时间+序列号)

xread
从消息队列中读取,COUNT:读取条数,
BLOCK:阻塞读(默认不阻塞)key:队列
名称 id:消息id

xrange
读取队列中给定ID范围的消息 COUNT:返
回消息条数(消息id从小到大)

xrevrange
读取队列中给定ID范围的消息 COUNT:返
回消息条数(消息id从大到小)

xdel
删除队列的消息

xgroup
创建一个新的消费组
xgroup create key groupnameid

xgroup
删除指定消费组
xgroup delconsumer key groupname cname

xgroup
修改指定消息的最大id
xgroup setid key id

xreadgroup
从队列中的消费组中创建消费者并消费数据
(consumer不存在则创建)

2.9 .1 应用场景:

消息队列的使用

3.Redis底层数据结构

Redis作为Key-Value存储系统,数据结构如下:

[由零开始]Redis数据类型与底层数据结构

Redis没有表的概念,Redis实例所对应的db以编号区分,db本身就是key的命名空间。
比如:user:1000作为key值,表示在user这个命名空间下id为1000的元素,类似于user表的id=1000的
行。

3.1 RedisDB结构

Redis中存在“数据库”的概念,该结构由redis.h中的redisDb定义。
当redis 服务器初始化时,会预先分配 16 个数据库
所有数据库保存到结构 redisServer 的一个成员 redisServer.db 数组中
redisClient中存在一个名叫db的指针指向当前使用的数据库
RedisDB结构体源码:

typedef struct redisDb {
int id; //id是数据库序号,为0-15(默认Redis有16个数据库)
long avg_ttl; //存储的数据库对象的平均ttl(time to live),用于统计
dict *dict; //存储数据库所有的key-value
dict *expires; //存储key的过期时间
dict *blocking_keys;//blpop 存储阻塞key和客户端对象
dict *ready_keys;//阻塞后push 响应阻塞客户端 存储阻塞后push的key和客户端对象
dict *watched_keys;//存储watch监控的的key和客户端对象
} redisDb;

3.1.1 id

id是数据库序号,为0-15(默认Redis有16个数据库)

3.1.2 dict

存储数据库所有的key-value

3.1.3 expires

存储key的过期时间

3.2 RedisObject结构

typedef struct redisObject {
unsigned type:4;//类型 五种对象类型
unsigned encoding:4;//编码
void *ptr;//指向底层实现数据结构的指针
//...
int refcount;//引用计数
//...
unsigned lru:LRU_BITS; //LRU_BITS为24bit 记录最后一次被命令程序访问的时间
//...
}robj;

3.2.1 结构信息概览

4位type

type 字段表示对象的类型,占 4 位;
REDIS_STRING(字符串)、REDIS_LIST (列表)、REDIS_HASH(哈希)、REDIS_SET(集合)、REDIS_ZSET(有
序集合)。
当我们执行 type 命令时,便是通过读取 RedisObject 的 type 字段获得对象的类型

127.0.0.1:6379> type a1
string

4位encoding

encoding 表示对象的内部编码,占 4 位
每个对象有不同的实现编码
Redis 可以根据不同的使用场景来为对象设置不同的编码,大大提高了 Redis 的灵活性和效率。
通过 object encoding 命令,可以查看对象采用的编码方式

127.0.0.1:6379> object encoding a1
"int"

24位LRU

lru 记录的是对象最后一次被命令程序访问的时间,( 4.0 版本占 24 位,2.6 版本占 22 位)。
高16位存储一个分钟数级别的时间戳,低8位存储访问计数(lfu : 最近访问次数)

refcount

当对象的refcount>1时,称为共享对象
Redis 为了节省内存,当有一些对象重复出现时,新的程序不会创建新的对象,而是仍然使用原来的对
象。

ptr

ptr 指针指向具体的数据,比如:set hello world,ptr 指向包含字符串 world 的 SDS。

3.2.2 7种type

字符串对象

C语言: 字符数组 “\0”
Redis 使用了 SDS(Simple Dynamic String)。用于存储字符串和整型数据。

[由零开始]Redis数据类型与底层数据结构

struct sdshdr{
//记录buf数组中已使用字节的数量
int len;
//记录 buf 数组中未使用字节的数量
int free;
//字节数组,用于保存字符串
char buf[];
}

SDS的优势:
1、SDS 在 C 字符串的基础上加入了 free 和 len 字段,获取字符串长度:SDS 是 O(1),C 字符串是
O(n)。
buf数组的长度=free+len+1
2、 SDS 由于记录了长度,在可能造成缓冲区溢出时会自动重新分配内存,杜绝了缓冲区溢出。
3、可以存取二进制数据,以字符串长度len来作为结束标识
使用场景:
SDS的主要应用在:存储字符串和整型数据、存储key、AOF缓冲区和用户输入缓冲。

跳跃表(重点)

跳跃表是有序集合(sorted-set)的底层实现,效率高,实现简单。

跳跃表的基本思想:
将有序链表中的部分节点分层,每一层都是一个有序链表。
查找
在查找时优先从最高层开始向后查找,当到达某个节点时,如果next节点值大于要查找的值或next指针
指向null,则从当前节点下降一层继续向后查找。
举例:

[由零开始]Redis数据类型与底层数据结构

查找元素9,按道理我们需要从头结点开始遍历,一共遍历8个结点才能找到元素9。
第一次分层:
遍历5次找到元素9(红色的线为查找路径)

[由零开始]Redis数据类型与底层数据结构

第二次分层:
遍历4次找到元素9

[由零开始]Redis数据类型与底层数据结构

第三层分层:
遍历4次找到元素9

[由零开始]Redis数据类型与底层数据结构

这种数据结构,就是跳跃表,它具有二分查找的功能。
插入与删除
上面例子中,9个结点,一共4层,是理想的跳跃表。
通过抛硬币(概率1/2)的方式来决定新插入结点跨越的层数:

正面:插入上层
背面:不插入
达到1/2概率(计算次数)
删除
找到指定元素并删除每层的该元素即可
跳跃表特点:
每层都是一个有序链表
查找次数近似于层数(1/2)
底层包含所有元素
空间复杂度 O(n) 扩充了一倍
Redis跳跃表的实现

//跳跃表节点
typedef struct zskiplistNode {
sds ele; /* 存储字符串类型数据 redis3.0版本中使用robj类型表示,
但是在redis4.0.1中直接使用sds类型表示 */
double score;//存储排序的分值
struct zskiplistNode *backward;//后退指针,指向当前节点最底层的前一个节点
/*
层,柔性数组,随机生成1-64的值
*/
struct zskiplistLevel {
struct zskiplistNode *forward; //指向本层下一个节点
unsigned int span;//本层下个节点到本节点的元素个数
} level[];
} zskiplistNode;
//链表
typedef struct zskiplist{
//表头节点和表尾节点
structz skiplistNode *header, *tail;
//表中节点的数量
unsigned long length;
//表中层数最大的节点的层数
int level;
}zskiplist;

完整的跳跃表结构体:

[由零开始]Redis数据类型与底层数据结构

跳跃表的优势:
1、可以快速查找到需要的节点
2、可以在O(1)的时间复杂度下,快速获得跳跃表的头节点、尾结点、长度和高度。
应用场景:有序集合的实现

字典(重点+难点)

字典dict又称散列表(hash),是用来存储键值对的一种数据结构。
Redis整个数据库是用字典来存储的。(K-V结构)
对Redis进行CURD操作其实就是对字典中的数据进行CURD操作。
数组
数组:用来存储数据的容器,采用头指针+偏移量的方式能够以O(1)的时间复杂度定位到数据所在的内
存地址。
Redis 海量存储 快
Hash函数
Hash(散列),作用是把任意长度的输入通过散列算法转换成固定类型、固定长度的散列值。
hash函数可以把Redis里的key:包括字符串、整数、浮点数统一转换成整数。
key=100.1 String “100.1” 5位长度的字符串
Redis-cli :times 33
Redis-Server : siphash
数组下标=hash(key)%数组容量(hash值%数组容量得到的余数)

Hash冲突

不同的key经过计算后出现数组下标一致,称为Hash冲突。
采用单链表在相同的下标位置处存储原始key和value
当根据key找Value时,找到数组下标,遍历单链表可以找出key相同的value

[由零开始]Redis数据类型与底层数据结构

Redis字典的实现
Redis字典实现包括:字典(dict)、Hash表(dictht)、Hash表节点(dictEntry)。

[由零开始]Redis数据类型与底层数据结构

Hash表

typedef struct dictht {
dictEntry **table; // 哈希表数组
unsigned long size; // 哈希表数组的大小
unsigned long sizemask; // 用于映射位置的掩码,值永远等于(size-1)
unsigned long used; // 哈希表已有节点的数量,包含next单链表数据
} dictht;

1、hash表的数组初始容量为4,随着k-v存储量的增加需要对hash表数组进行扩容,新扩容量为当前量
的一倍,即4,8,16,32
2、索引值=Hash值&掩码值(Hash值与Hash表容量取余)
Hash表节点

typedef struct dictEntry {
void *key; // 键
union { // 值v的类型可以是以下4种类型
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next; // 指向下一个哈希表节点,形成单向链表 解决hash冲突
} dictEntry

key字段存储的是键值对中的键
v字段是个联合体,存储的是键值对中的值。
next指向下一个哈希表节点,用于解决hash冲突

[由零开始]Redis数据类型与底层数据结构

dict字典

typedef struct dict {
dictType *type; // 该字典对应的特定操作函数
void *privdata; // 上述类型函数对应的可选参数
dictht ht[2]; /* 两张哈希表,存储键值对数据,ht[0]为原生
哈希表,
ht[1]为 rehash 哈希表 */
long rehashidx; /*rehash标识 当等于-1时表示没有在
rehash,
否则表示正在进行rehash操作,存储的值表示
hash表 ht[0]的rehash进行到哪个索引值
(数组下标)*/
int iterators; // 当前运行的迭代器数量
} dict;

type字段,指向dictType结构体,里边包括了对该字典操作的函数指针

typedef struct dictType {
// 计算哈希值的函数
unsigned int (*hashFunction)(const void *key);
// 复制键的函数
void *(*keyDup)(void *privdata, const void *key);
// 复制值的函数
void *(*valDup)(void *privdata, const void *obj);
// 比较键的函数
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
// 销毁键的函数
void (*keyDestructor)(void *privdata, void *key);
// 销毁值的函数
void (*valDestructor)(void *privdata, void *obj);
} dictType;

Redis字典除了主数据库的K-V数据存储以外,还可以用于:散列表对象、哨兵模式中的主从节点管理等
在不同的应用中,字典的形态都可能不同,dictType是为了实现各种形态的字典而抽象出来的操作函数
(多态)。
完整的Redis字典数据结构:

[由零开始]Redis数据类型与底层数据结构

字典扩容

字典达到存储上限,需要rehash(扩容)

扩容流程:

[由零开始]Redis数据类型与底层数据结构

说明:

    初次申请默认容量为4个dictEntry,非初次申请为当前hash表容量的一倍。
    rehashidx=0表示要进行rehash操作。
    新增加的数据在新的hash表h[1]
    修改、删除、查询在老hash表h[0]、新hash表h[1]中(rehash中)
    将老的hash表h[0]的数据重新计算索引值后全部迁移到新的hash表h[1]中,这个过程称为
    rehash。

渐进式rehash

当数据量巨大时rehash的过程是非常缓慢的,所以需要进行优化。
服务器忙,则只对一个节点进行rehash
服务器闲,可批量rehash(100节点)

应用场景:

1、主数据库的K-V数据存储
2、散列表对象(hash)
3、哨兵模式中的主从节点管理

压缩列表

压缩列表(ziplist)是由一系列特殊编码的连续内存块组成的顺序型数据结构
节省内存

是一个字节数组,可以包含多个节点(entry)。每个节点可以保存一个字节数组或一个整数。
压缩列表的数据结构如下:

[由零开始]Redis数据类型与底层数据结构

zlbytes:压缩列表的字节长度
zltail:压缩列表尾元素相对于压缩列表起始地址的偏移量
zllen:压缩列表的元素个数
entry1…entryX : 压缩列表的各个节点
zlend:压缩列表的结尾,占一个字节,恒为0xFF(255)
entryX元素的编码结构:

[由零开始]Redis数据类型与底层数据结构

previous_entry_length:前一个元素的字节长度
encoding:表示当前元素的编码
content:数据内容
ziplist结构体如下:

typedef struct zlentry {
unsigned int prevrawlensize; //previous_entry_length字段的长度
unsigned int prevrawlen; //previous_entry_length字段存储的内容
unsigned int lensize; //encoding字段的长度
unsigned int len; //数据内容长度
unsigned int headersize; //当前元素的首部长度,即previous_entry_length字段长
度与 encoding字段长度之和。
unsigned char encoding; //数据类型
unsigned char *p; //当前元素首地址
} zlentry;

应用场景:
sorted-set和hash元素个数少且是小整数或短字符串(直接使用)
list用快速链表(quicklist)数据结构存储,而快速链表是双向列表与压缩列表的组合。(间接使用)

整数集合

整数集合(intset)是一个有序的(整数升序)、存储整数的连续存储结构。

当Redis集合类型的元素都是整数并且都处在64位有符号整数范围内(2^64),使用该结构体存储。

127.0.0.1:6379> sadd set:001 1 3 5 6 2
(integer) 5
127.0.0.1:6379> object encoding set:001
"intset"
127.0.0.1:6379> sadd set:004 1 100000000000000000000000000 9999999999
(integer) 3
127.0.0.1:6379> object encoding set:004
"hashtable

intset的结构图如下:

[由零开始]Redis数据类型与底层数据结构

typedef struct intset{
//编码方式
uint32_t encoding;
//集合包含的元素数量
uint32_t length;
//保存元素的数组
int8_t contents[];
}intset;

应用场景:
可以保存类型为int16_t、int32_t 或者int64_t 的整数值,并且保证集合中不会出现重复元素。

快速列表(重要)

快速列表(quicklist)是Redis底层重要的数据结构。是列表的底层实现。(在Redis3.2之前,Redis采
用双向链表(adlist)和压缩列表(ziplist)实现。)在Redis3.2以后结合adlist和ziplist的优势Redis设
计出了quicklist。

127.0.0.1:6379> lpush list:001 1 2 5 4 3
(integer) 5
127.0.0.1:6379> object encoding list:001
"quicklist"

双向列表(adlist)

[由零开始]Redis数据类型与底层数据结构

双向链表优势:

    双向:链表具有前置节点和后置节点的引用,获取这两个节点时间复杂度都为O(1)。
    普通链表(单链表):节点类保留下一节点的引用。链表类只保留头节点的引用,只能从头节点插
    入删除
    无环:表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL,对链表的访问都是以 NULL 结
    束。
    带链表长度计数器:通过 len 属性获取链表长度的时间复杂度为 O(1)。
    多态:链表节点使用 void* 指针来保存节点值,可以保存各种不同类型的值。
    快速

快速列表

quicklist是一个双向链表,链表中的每个节点时一个ziplist结构。quicklist中的每个节点ziplist都能够存
储多个数据元素。

[由零开始]Redis数据类型与底层数据结构

quicklist的结构定义如下:

typedef struct quicklist {
quicklistNode *head; // 指向quicklist的头部
quicklistNode *tail; // 指向quicklist的尾部
unsigned long count; // 列表中所有数据项的个数总和
unsigned int len; // quicklist节点的个数,即ziplist的个数
int fill : 16; // ziplist大小限定,由list-max-ziplist-size给定
(Redis设定)
unsigned int compress : 16; // 节点压缩深度设置,由list-compress-depth给定(Redis
设定)
} quicklist;

quicklistNode的结构定义如下:

typedef struct quicklistNode {
struct quicklistNode *prev; // 指向上一个ziplist节点
struct quicklistNode *next; // 指向下一个ziplist节点
unsigned char *zl; // 数据指针,如果没有被压缩,就指向ziplist结构,反之指
向 quicklistLZF结构
unsigned int sz; // 表示指向ziplist结构的总长度(内存占用长度)
unsigned int count : 16; // 表示ziplist中的数据项个数
unsigned int encoding : 2; // 编码方式,1--ziplist,2--quicklistLZF
unsigned int container : 2; // 预留字段,存放数据的方式,1--NONE,2--ziplist
unsigned int recompress : 1; // 解压标记,当查看一个被压缩的数据时,需要暂时解压,标
记此参数为 1,之后再重新进行压缩
unsigned int attempted_compress : 1; // 测试相关
unsigned int extra : 10; // 扩展字段,暂时没用
} quicklistNode;

数据压缩

quicklist每个节点的实际数据存储结构为ziplist,这种结构的优势在于节省存储空间。为了进一步降低
ziplist的存储空间,还可以对ziplist进行压缩。Redis采用的压缩算法是LZF。其基本思想是:数据与前
面重复的记录重复位置及长度,不重复的记录原始数据。
压缩过后的数据可以分成多个片段,每个片段有两个部分:解释字段和数据字段。quicklistLZF的结构
体如下:

typedef struct quicklistLZF {
unsigned int sz; // LZF压缩后占用的字节数
char compressed[]; // 柔性数组,指向数据部分
} quicklistLZF;

应用场景
列表(List)的底层实现、发布与订阅、慢查询、监视器等功能。

流对象

stream主要由:消息、生产者、消费者和消费组构成。

[由零开始]Redis数据类型与底层数据结构

Redis Stream的底层主要使用了listpack(紧凑列表)和Rax树(基数树)。
listpack
listpack表示一个字符串列表的序列化,listpack可用于存储字符串或整数。用于存储stream的消息内
容。
结构如下图:

[由零开始]Redis数据类型与底层数据结构

Rax树

Rax 是一个有序字典树 (基数树 Radix Tree),按照 key 的字典序排列,支持快速地定位、插入和删除操
作。

[由零开始]Redis数据类型与底层数据结构

Rax 被用在 Redis Stream 结构里面用于存储消息队列,在 Stream 里面消息 ID 的前缀是时间戳 + 序
号,这样的消息可以理解为时间序列消息。使用 Rax 结构 进行存储就可以快速地根据消息 ID 定位到具
体的消息,然后继续遍历指定消息 之后的所有消息。

[由零开始]Redis数据类型与底层数据结构

应用场景:
stream的底层实现

3.2.2 10种encoding

String
int、raw、embstr
int
REDIS_ENCODING_INT(int类型的整数)

127.0.0.1:6379> set n1 123
OK
127.0.0.1:6379> object encoding n1
"int"

embstr

REDIS_ENCODING_EMBSTR(编码的简单动态字符串)
小字符串 长度小于44个字节

127.0.0.1:6379> set name:001 zhangfei
OK
127.0.0.1:6379> object encoding name:001
"embstr"

raw

REDIS_ENCODING_RAW (简单动态字符串)
大字符串 长度大于44个字节

127.0.0.1:6379> set address:001
asdasdasdasdasdasdsadasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdas
dasdasdas
OK
127.0.0.1:6379> object encoding address:001
"raw"

list

列表的编码是quicklist。
REDIS_ENCODING_QUICKLIST(快速列表)

127.0.0.1:6379> lpush list:001 1 2 5 4 3
(integer) 5
127.0.0.1:6379> object encoding list:001
"quicklist"

hash

散列的编码是字典和压缩列表

dict
REDIS_ENCODING_HT(字典)
当散列表元素的个数比较多或元素不是小整数或短字符串时。

127.0.0.1:6379> hmset user:003
username111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111 zhangfei password 111 num
2300000000000000000000000000000000000000000000000000
OK
127.0.0.1:6379> object encoding user:003
"hashtable"

ziplist
REDIS_ENCODING_ZIPLIST(压缩列表)
当散列表元素的个数比较少,且元素都是小整数或短字符串时。

127.0.0.1:6379> hmset user:001 username zhangfei password 111 age 23 sex M
OK
127.0.0.1:6379> object encoding user:001
"ziplist"

set
集合的编码是整形集合和字典
intset
REDIS_ENCODING_INTSET(整数集合)
当Redis集合类型的元素都是整数并且都处在64位有符号整数范围内(<18446744073709551616)

127.0.0.1:6379> sadd set:001 1 3 5 6 2
(integer) 5
127.0.0.1:6379> object encoding set:001
"intset"

dict

REDIS_ENCODING_HT(字典)
当Redis集合类型的元素都是整数并且都处在64位有符号整数范围外(>18446744073709551616)

127.0.0.1:6379> sadd set:004 1 100000000000000000000000000 9999999999
(integer) 3
127.0.0.1:6379> object encoding set:004
"hashtable"

zset
有序集合的编码是压缩列表和跳跃表+字典
ziplist
REDIS_ENCODING_ZIPLIST(压缩列表)
当元素的个数比较少,且元素都是小整数或短字符串时。

127.0.0.1:6379> zadd hit:1 100 item1 20 item2 45 item3
(integer) 3
127.0.0.1:6379> object encoding hit:1
"ziplist"

skiplist + dict
REDIS_ENCODING_SKIPLIST(跳跃表+字典)
当元素的个数比较多或元素不是小整数或短字符串时。

127.0.0.1:6379> zadd hit:2 100
item1111111111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111 20 item2 45 item3
(integer) 3
127.0.0.1:6379> object encoding hit:2
"skiplist"

TSET(整数集合)
当Redis集合类型的元素都是整数并且都处在64位有符号整数范围内(<18446744073709551616)

127.0.0.1:6379> sadd set:001 1 3 5 6 2
(integer) 5
127.0.0.1:6379> object encoding set:001
"intset"

dict

REDIS_ENCODING_HT(字典)
当Redis集合类型的元素都是整数并且都处在64位有符号整数范围外(>18446744073709551616)

127.0.0.1:6379> sadd set:004 1 100000000000000000000000000 9999999999
(integer) 3
127.0.0.1:6379> object encoding set:004
"hashtable"

zset
有序集合的编码是压缩列表和跳跃表+字典
ziplist
REDIS_ENCODING_ZIPLIST(压缩列表)
当元素的个数比较少,且元素都是小整数或短字符串时。

127.0.0.1:6379> zadd hit:1 100 item1 20 item2 45 item3
(integer) 3
127.0.0.1:6379> object encoding hit:1
"ziplist"

skiplist + dict
REDIS_ENCODING_SKIPLIST(跳跃表+字典)
当元素的个数比较多或元素不是小整数或短字符串时。

127.0.0.1:6379> zadd hit:2 100
item1111111111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111 20 item2 45 item3
(integer) 3
127.0.0.1:6379> object encoding hit:2
"skiplist"

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

[由零开始]Redis数据类型与底层数据结构

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » [由零开始]Redis数据类型与底层数据结构
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏