信阳高端网站建设,郑州模板建站系统,网站开发工具选择,东莞市是哪个省Redis之五大基础数据类型
Redis 共有 5 种基本数据类型#xff1a;String#xff08;字符串#xff09;、List#xff08;列表#xff09;、Set#xff08;集合#xff09;、Hash#xff08;散列#xff09;、Zset#xff08;有序集合#xff09;。
这 5 种数据类…Redis之五大基础数据类型
Redis 共有 5 种基本数据类型String字符串、List列表、Set集合、Hash散列、Zset有序集合。
这 5 种数据类型是直接提供给用户使用的是数据的保存形式其底层实现主要依赖这 8 种数据结构 简单动态字符串SDS、LinkedList双向链表、Dict哈希表/字典、SkipList跳跃表、Intset整数集合、ZipList压缩列表、QuickList快速列表 Redis底层通过C语言实现了这些数据结构这些源码在Redis官网可以下载 我们发现基础数据类型都有对应的C语言文件 Redis是key-value存储系统key一般为string类型的字符串value是redis对象(object) 从上帝视角看看简单的set k1 v1
1.启动Redis server
2.形成redisdb
3.形成字典存储哈希键值对对象
4.指向5大基础数据类型后由对应底层数据结构完成实现 Redis借鉴了Java中对象的思想定义了redisObject结构体来表示stringhashlistsetzset redis中每一个键值对都会有一个dictEntry 在dictEntry中的v指向对应的redisObject 键值对是如何存储并读取达到o1复杂度 1.启动redis server后就会加载redisDb 2.redisDb加载进内存形成数据库 3.数据库读dict字典形成字典后找哈希表 4.其中每一个kv键值对形成结构体dictEntry 5.dictEntry封装后形成redisObject 6.最终操作的是redisObject redisObjectredis数据类型redis编码方式的关系 redis6之前的数据类型和数据结构的关系 redis7的数据类型和数据结构的关系 从简单的set hello world说起 因为Redis是KV键值对的数据库每个键值对都会有一个dictEntry(源码位置dict.h)里面指向了key和value的指针next 指向下一个 dictEntry。 key 是字符串但是 Redis 没有直接使用 C 的字符数组而是存储在redis自定义的 SDS中。 value 既不是直接作为字符串存储也不是直接存储在 SDS 中而是存储在redisObject 中。 实际上五种常用的数据类型的任何一种都是通过 redisObject 来存储的。 redisObject的作用 为了便于操作Redis采用redisObjec结构来统一五种不同的数据类型这样所有的数据类型就都可以以相同的形式在函数间传递而不用使用特定的类型结构。 同时为了识别不同的数据类型redisObjec中定义了type和encoding字段对不同的数据类型加以区别。简单地说redisObjec就是string、hash、list、set、zset的父类可以在函数间传递时隐藏具体的类型信息所以作者抽象了redisObjec结构来到达同样的目的。 redisObject中各个字段的含义 五大基础数据类型结构解析
各个类型的数据结构的编码映射和定义 String
三种编码方式 int保存long的64位8个字节长整形有符号整数-263~263-1 只有整数才会使用int 如果是浮点数redis内部将其转为字符串后再存储 embstr代表embstr格式的SDSsimple dynamic string 简单动态字符保存小于44字节的字符串 embeded string 嵌入的字符串 raw保存长度大于44字节的字符串 SDS简单动态字符串
SDS 是什么 相信大家都学过 C 语言对 C 中的字符串已经比较清楚了在 C 中如果我们要存储一个字符串可以先定义一个字符数组 char[] 或者 char *p 然后将字符串挨个存进去。 这种方式存在什么问题 当我们想要获取字符串的实际长度时需要遍历整个字符串 char[]你可能觉得单次操作性能应该还行然而 redis 服务的是以万 的QPS这种操作就有些问题了。 显然直接用 C 中的字符串不太现实但可以在其之上做一层数据结构封装一款适用于高并发场景下能高效的解决 C 字符串缺陷的特殊结构这就是 SDS。 SDS 既然是字符串那么首先需要一个字符串指针为了方便上层的接口调用该结构还需要记录一些关键信息如当前数据长度和剩余容量等数据结构如下
struct sdshdr {unsigned int len;unsigned int free;char buf[];
};其中len 表示当前字符串长度、free 表示剩余可用空间、buf[] 存储实际数据。
值得注意的是以上结构是 redis3.2 版本之前的结构3.2 已经做出了些许调整至于原因咱们继续往后看 SDS 遵循 C 字符串以空字符结尾的惯例 保存空字符的 1 字节空间不计算在 SDS 的 len 属性里面 并且为空字符分配额外的 1 字节空间 以及添加空字符到字符串末尾等操作都是由 SDS 函数自动完成的 所以这个空字符对于 SDS 的使用者来说是完全透明的。
遵循空字符结尾这一惯例的好处是 SDS 可以直接重用一部分 C 字符串函数库里面的函数。
SDS 与 C 字符串的区别
根据传统 C 语言使用长度为 N1 的字符数组来表示长度为 N 的字符串 并且字符数组的最后一个元素总是空字符 ‘\0’ 比如 C 语言使用的这种简单的字符串表示方式 并不能满足 Redis 对字符串在安全性、效率、以及功能方面的要求 本节接下来的内容将详细对比 C 字符串和 SDS 之间的区别 并说明 SDS 比 C 字符串更适用于 Redis 的原因。
常数复杂度获取字符串长度 因为 C 字符串并不记录自身的长度信息 所以为了获取一个 C 字符串的长度 程序必须遍历整个字符串 对遇到的每个字符进行计数 直到遇到代表字符串结尾的空字符为止 这个操作的复杂度为 O(N) 。 和 C 字符串不同 因为 SDS 在 len 属性中记录了 SDS 本身的长度 所以获取一个 SDS 长度的复杂度仅为 O(1) 。 设置和更新 SDS 长度的工作是由 SDS 的 API 在执行时自动完成的 使用 SDS 无须进行任何手动修改长度的工作。 通过使用 SDS 而不是 C 字符串 Redis 将获取字符串长度所需的复杂度从 O(N) 降低到了 O(1) 这确保了获取字符串长度的工作不会成为 Redis 的性能瓶颈。 比如说 因为字符串键在底层使用 SDS 来实现 所以即使我们对一个非常长的字符串键反复执行 STRLEN 命令 也不会对系统性能造成任何影响 因为 STRLEN 命令的复杂度仅为 O(1) 。 杜绝缓冲区溢出
C 字符串不记录自身长度带来的另一个问题是容易造成缓冲区溢出buffer overflow分配内存空间超过后会导致数组下标越级或者内存分配溢出 与 C 字符串不同 SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性 当 SDS API 需要对 SDS 进行修改时 API 会先检查 SDS 的空间是否满足修改所需的要求 如果不满足的话 API 会自动将 SDS 的空间扩展至执行修改所需的大小 然后才执行实际的修改操作 所以使用 SDS 既不需要手动修改 SDS 的空间大小 也不会出现前面所说的缓冲区溢出问题
减少修改字符串时带来的内存重分配次数
因为 C 字符串并不记录自身的长度 所以对于一个包含了 N 个字符的 C 字符串来说 这个 C 字符串的底层实现总是一个 N1 个字符长的数组额外的一个字符空间用于保存空字符。
因为 C 字符串的长度和底层数组的长度之间存在着这种关联性 所以每次增长或者缩短一个 C 字符串 程序都总要对保存这个 C 字符串的数组进行一次内存重分配操作
如果程序执行的是增长字符串的操作 比如拼接操作append 那么在执行这个操作之前 程序需要先通过内存重分配来扩展底层数组的空间大小 —— 如果忘了这一步就会产生缓冲区溢出。如果程序执行的是缩短字符串的操作 比如截断操作trim 那么在执行这个操作之后 程序需要通过内存重分配来释放字符串不再使用的那部分空间 —— 如果忘了这一步就会产生内存泄漏。
因为内存重分配涉及复杂的算法 并且可能需要执行系统调用 所以它通常是一个比较耗时的操作
在一般程序中 如果修改字符串长度的情况不太常出现 那么每次修改都执行一次内存重分配是可以接受的。但是 Redis 作为数据库 经常被用于速度要求严苛、数据被频繁修改的场合 如果每次修改字符串的长度都需要执行一次内存重分配的话 那么光是执行内存重分配的时间就会占去修改字符串所用时间的一大部分 如果这种修改频繁地发生的话 可能还会对性能造成影响。
为了避免 C 字符串的这种缺陷 SDS 通过未使用空间解除了字符串长度和底层数组长度之间的关联 在 SDS 中 buf 数组的长度不一定就是字符数量加一 数组里面可以包含未使用的字节 而这些字节的数量就由 SDS 的 free 属性记录。
通过未使用空间 SDS 实现了空间预分配和惰性空间释放两种优化策略。 空间预分配 SDS 修改后len 长度小于 1M那么将会额外分配与 len 相同长度的未使用空间。如果修改后长度大于 1M那么将分配1M的使用空间。 惰性空间释放 有空间分配对应的就有空间释放。SDS 缩短时并不会回收多余的内存空间而是使用 free 字段将多出来的空间记录下来。如果后续有变更操作直接使用 free 中记录的空间减少了内存的分配。 二进制安全
C 字符串中的字符必须符合某种编码比如 ASCII 并且除了字符串的末尾之外 字符串里面不能包含空字符 否则最先被程序读入的空字符将被误认为是字符串结尾 —— 这些限制使得 C 字符串只能保存文本数据 而不能保存像图片、音频、视频、压缩文件这样的二进制数据。
虽然数据库一般用于保存文本数据 但使用数据库来保存二进制数据的场景也不少见 因此 为了确保 Redis 可以适用于各种不同的使用场景 SDS 的 API 都是二进制安全的binary-safe 所有 SDS API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组里的数据 程序不会对其中的数据做任何限制、过滤、或者假设 —— 数据在写入时是什么样的 它被读取时就是什么样。
这也是我们将 SDS 的 buf 属性称为字节数组的原因 —— Redis 不是用这个数组来保存字符 而是用它来保存一系列二进制数据。
比如说 使用 SDS 来保存之前提到的特殊数据格式就没有任何问题 因为 SDS 使用 len 属性的值而不是空字符来判断字符串是否结束
C语言SDS字符串长度处理需要从头开始遍历直到遇到 ‘\0’ 为止时间复杂度O(N)记录当前字符串的长度直接读取即可时间复杂度 O(1)内存重新分配分配内存空间超过后会导致数组下标越级或者内存分配溢出空间预分配SDS 修改后len 长度小于 1M那么将会额外分配与 len 相同长度的未使用空间。如果修改后长度大于 1M那么将分配1M的使用空间。惰性空间释放有空间分配对应的就有空间释放。SDS 缩短时并不会回收多余的内存空间而是使用 free 字段将多出来的空间记录下来。如果后续有变更操作直接使用 free 中记录的空间减少了内存的分配。二进制安全二进制数据并不是规则的字符串格式可能会包含一些特殊的字符比如 ‘\0’ 等。前面提到过C中字符串遇到 ‘\0’ 会结束那 ‘\0’ 之后的数据就读取不上了根据 len 长度来判断字符串结束的二进制安全的问题就解决了
SDS API
创建SDS
Redis 通过sdsnewlen方法创建 SDS。在方法中会根据字符串初始化长度选择合适的类型。
sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) {void *sh;sds s;// 根据初始化长度判断 SDS 的类型char type sdsReqType(initlen);// SDS_TYPE_5 强制转换为 SDS_TYPE_8// 这样侧面验证了 sdshdr5 从未被使用创建这一步就GG了 ੯ੁૂ‧̀͡u\if (type SDS_TYPE_5 initlen 0) type SDS_TYPE_8;// 获取头部大学int hdrlen sdsHdrSize(type);// 指向 flags 的指针unsigned char *fp; /* flags pointer. */// 分配的空间size_t usable;// 防止溢出assert(initlen hdrlen 1 initlen); /* Catch size_t overflow */// 分配空间// s_trymalloc_usable: 尝试分配内存失败则返回NULL// s_malloc_usable: 分配内存或者抛异常[不友好]sh trymalloc?s_trymalloc_usable(hdrleninitlen1, usable) :s_malloc_usable(hdrleninitlen1, usable);if (sh NULL) return NULL;if (initSDS_NOINIT)init NULL;else if (!init)memset(sh, 0, hdrleninitlen1);// s 此时指向bufs (char*)shhdrlen;// 指向flagsfp ((unsigned char*)s)-1;usable usable-hdrlen-1;// 对不同类型的 SDS 可分配空间进行截断if (usable sdsTypeMaxSize(type))usable sdsTypeMaxSize(type);switch(type) {case SDS_TYPE_5: {*fp type | (initlen SDS_TYPE_BITS);break;}case SDS_TYPE_8: {SDS_HDR_VAR(8,s);sh-len initlen;sh-alloc usable;*fp type;break;}// ... 省略}if (initlen init)memcpy(s, init, initlen);// 末尾添加\0s[initlen] \0;return s;
}通过sdsnewlen方法我们可以获得以下信息
SDS_TYPE_5 会被强制转换为 SDS_TYPE_8 类型创建时默认会在末尾加\0返回值是指向 SDS 结构中 buf 的指针返回值是char *sds类型可以兼容部分C函数。
释放SDS
为了优化性能SDS 提供了不直接释放内存而是通过重置len达到清空 SDS 目的的方法——sdsclear。改方法仅仅将 SDS 的len归零而buf的空间并为真正被清空新的数据可以复写而不用重新申请内存。
void sdsclear(sds s) {sdssetlen(s, 0);// 设置len为0s[0] \0;//“清空”buf
}若真正想清空 SDS 则可以调用sdsfree方法底层通过调用s_free释放内存。
void sdsfree(sds s) {if (s NULL) return;s_free((char*)s-sdsHdrSize(s[-1]));
}set方法 set k1 123
当字符串键值的内容可以用一个64位有符号整形来表示时Redis会将键值转化为long型来进行存储此时即对应 OBJ_ENCODING_INT 编码类型。内部的内存结构表示如下: Redis 启动时会预先建立 10000 个分别存储 0~9999 的 redisObject 变量作为共享对象这就意味着如果 set字符串的键值在 0~10000 之间的话则可以
直接指向共享对象 而不需要再建立新对象此时键值不占空间
set k1 123
set k2 123 set k1 abc 对于长度小于 44的字符串Redis 对键值采用OBJ_ENCODING_EMBSTR 方式EMBSTR 顾名思义即embedded string表示嵌入式的String。从内存结构上来讲 即字符串 sds结构体与其对应的 redisObject 对象分配在同一块连续的内存空间字符串sds嵌入在redisObject对象之中一样。 set k1 长度大于44的字符串 当字符串的键值为长度大于44的超长字符串时Redis 则会将键值的内部编码方式改为OBJ_ENCODING_RAW格式这与OBJ_ENCODING_EMBSTR编码方式的不同之处在于此时动态字符串sds的内存与其依赖的redisObject的内存不再连续了
如果修改字符串明明没有达到阈值编码却改为了row 判断不出来就取最大Raw
流程图 总结
只有整数才会使用 int如果是浮点数 Redis 内部其实先将浮点数转化为字符串值然后再保存。
embstr 与 raw 类型底层的数据结构其实都是 SDS (简单动态字符串Redis 内部定义 sdshdr 一种结构)。
那这两者的区别见下图
1 intLong类型整数时RedisObject中的ptr指针直接赋值为整数数据不再额外的指针再指向整数了节省了指针的空间开销。2 embstr当保存的是字符串数据且字符串小于等于44字节时embstr类型将会调用内存分配函数只分配一块连续的内存空间空间中依次包含 redisObject 与 sdshdr 两个数据结构让元数据、指针和SDS是一块连续的内存区域这样就可以避免内存碎片3 raw当字符串大于44字节时SDS的数据量变多变大了SDS和RedisObject布局分家各自过会给SDS分配多的空间并用指针指向SDS结构raw 类型将会调用两次内存分配函数分配两块内存空间一块用于包含 redisObject结构而另一块用于包含 sdshdr 结构 redis内部会根据用户给的不同的键值而使用不同的编码格式而这一切都对用户透明
Hash
redis6 hash-max-ziplist-entries使用压缩列表保存时哈希集合中的最大元素个数。 hash-max-ziplist-value使用压缩列表保存时哈希集合中单个元素的最大长度。 Hash类型键的字段个数 小于 hash-max-ziplist-entries 并且每个字段名和字段值的长度 小于 hash-max-ziplist-value 时Redis才会使用 OBJ_ENCODING_ZIPLIST来存储该键前述条件任意一个不满足则会转换为 OBJ_ENCODING_HT的编码方式 1.哈希对象保存的键值对数量小于512个 2.所有的键值对的键和值都小于64byte时用ziplist否则使用hashtable 一旦从压缩列表转为了哈希表Hash类型就会一直用哈希表进行保存而不会再转回压缩列表了。
在节省内存空间方面哈希表就没有压缩列表高效了。
流程 t_hash.c
在redis中hashtable被称为字典dictionary它是一个数组链表
OBJ_ENCODING_HT 这种编码方式内部才是真正的哈希表结构或称为字典结构其可以实现O(1)复杂度的读写操作因此效率很高。
在 Redis内部从 OBJ_ENCODING_HT类型到底层真正的散列表数据结构是一层层嵌套下去的组织关系见面图 字典dictdicthttype
哈希表dicthtdictEntry
哈希条目dictEntrykeyvalue keystring valueredisObject
hset 编码方式的判断和转换 ziplist.c Ziplist 压缩列表是一种紧凑编码格式总体思想是多花时间来换取节约空间即以部分读写性能为代价来换取极高的内存空间利用率 因此只会用于 字段个数少且字段值也较小 的场景。压缩列表内存利用率极高的原因与其连续内存的特性是分不开的。 为了节约内存而开发的它是由连续内存块组成的顺序型数据结构有点类似于数组 ziplist是一个经过特殊编码的双向链表它不存储指向前一个链表节点prev和指向下一个链表节点的指针next而是存储上一个节点长度和当前节点长度通过牺牲部分读写性能来换取高效的内存空间利用率节约内存是一种时间换空间的思想。只用在字段个数少字段值小的场景里面 ziplist的各个单元的含义 在Java中有hashMap结构底层是由数组链表红黑树组成其中数组中存储我们的数据Java为我们封装了一个静态内部类Node来封装我们的KV所以是一个Node类型的数组 对比于redis的哈希结构也在内部为我们封装了一种特有的数据结构来存储我们的KV键值对为zlentry 属性含义
压缩列表zlentry节点结构每个zlentry由前一个节点的长度、encoding和entry-data三部分组成 前节点(前节点占用的内存字节数)表示前1个zlentry的长度privious_entry_length有两种取值情况1字节或5字节。取值1字节时表示上一个entry的长度小于254字节。虽然1字节的值能表示的数值范围是0到255但是压缩列表中zlend的取值默认是255因此就默认用255表示整个压缩列表的结束其他表示长度的地方就不能再用255这个值了。所以当上一个entry长度小于254字节时prev_len取值为1字节否则就取值为5字节。记录长度的好处占用内存小1或者5个字节 enncoding记录节点的content保存数据的类型和长度。 content保存实际数据内容 为什么entry这么设计记录前一个节点的长度
链表在内存中一般是不连续的遍历相对比较慢而ziplist可以很好的解决这个问题。如果知道了当前的起始地址因为entry是连续的entry后一定是另一个entry想知道下一个entry的地址只要将当前的起始地址加上当前entry总长度。如果还想遍历下一个entry只要继续同样的操作。
压缩链表为什么优于链表 1 普通的双向链表会有两个指针在存储数据很小的情况下我们存储的实际数据的大小可能还没有指针占用的内存大得不偿失。ziplist 是一个特殊的双向链表没有维护双向指针:previous next而是存储上一个 entry的长度和当前entry的长度通过长度推算下一个元素在什么地方。牺牲读取的性能获得高效的存储空间因为(简短字符串的情况)存储指针比存储entry长度更费内存。这是典型的“时间换空间”。 2 链表在内存中一般是不连续的遍历相对比较慢而ziplist可以很好的解决这个问题普通数组的遍历是根据数组里存储的数据类型找到下一个元素的(例如int类型的数组访问下一个元素时每次只需要移动一个sizeof(int)就行)但是ziplist的每个节点的长度是可以不一样的而我们面对不同长度的节点又不可能直接sizeof(entry)所以ziplist只好将一些必要的偏移量信息记录在了每一个节点里使之能跳到上一个节点或下一个节点。 备注:sizeof实际上是获取了数据在内存中所占用的存储空间以字节为单位来计数。 3 头节点里有头节点里同时还有一个参数 len和string类型提到的 SDS 类似这里是用来记录链表长度的。因此获取链表长度时不用再遍历整个链表直接拿到len值就可以了这个时间复杂度是 O(1) 小结 ziplist为了节省内存采用了紧凑的连续存储。 ziplist是一个双向链表可以在时间复杂度为 O(1) 下从头部、尾部进行 pop 或 push。 新增或更新元素可能会出现连锁更新现象(致命缺点导致被listpack替换)。 不能保存过多的元素否则查询效率就会降低数量小和内容小的情况下可以使用。 redis7
listpack hash-max-listpack-entries使用压缩列表保存时哈希集合中的最大元素个数。 hash-max-listpack-value使用压缩列表保存时哈希集合中单个元素的最大长度。 Hash类型键的字段个数 小于 hash-max-listpack-entries且每个字段名和字段值的长度 小于 hash-max-listpack-value 时 Redis才会使用OBJ_ENCODING_LISTPACK来存储该键前述条件任意一个不满足则会转换为 OBJ_ENCODING_HT的编码方式 还保留了ziplist保证版本兼容但实际起作用的是listpack 第一步创建hash对象创建listpack并创建obj设置编码方式 第二步创建listpack lpNew 函数创建了一个空的 listpack一开始分配的大小是 LP_HDR_SIZE 再加 1 个字节。LP_HDR_SIZE 宏定义是在 listpack.c 中它默认是 6 个字节其中 4 个字节是记录 listpack 的总字节数2 个字节是记录 listpack 的元素数量。此外listpack 的最后一个字节是用来标识 **listpack 的结束**其默认值是宏定义 LP_EOF。和 ziplist 列表项的结束标记一样LP_EOF 的值也是 2550xFF 第三步 紧凑列表为什么优于压缩列表
ziplist的连锁更新问题 压缩列表新增某个元素或修改某个元素时如果空间不不够压缩列表占用的内存空间就需要重新分配。而当新插入的元素较大时可能会导致后续元素的 prevlen 占用空间都发生变化从而引起「连锁更新」问题导致每个元素的空间都要重新分配造成访问压缩列表性能的下降。 案例说明压缩列表每个节点正因为需要保存前一个节点的长度字段就会有连锁更新的隐患 第一步现在假设一个压缩列表中有多个连续的、长度在 250253 之间的节点如下图 因为这些节点长度值小于 254 字节所以 prevlen 属性需要用 1 字节的空间来保存这个长度值一切OKO(∩_∩)O哈哈~ 第二步这时如果将一个长度大于等于 254 字节的新节点加入到压缩列表的表头节点即新节点将成为entry1的前置节点如下图 因为entry1节点的prevlen属性只有1个字节大小无法保存新节点的长度此时就需要对压缩列表的空间重分配操作并将entry1节点的prevlen 属性从原来的 1 字节大小扩展为 5 字节大小。
第三步连续更新问题出现 entry1节点原本的长度在250253之间因为刚才的扩展空间此时entry1节点的长度就大于等于254因此原本entry2节点保存entry1节点的 prevlen属性也必须从1字节扩展至5字节大小。entry1节点影响entry2节点entry2节点影响entry3节点…一直持续到结尾。这种在特殊情况下产生的连续多次空间扩展操作就叫做「连锁更新」 listpack 是 Redis 设计用来取代掉 ziplist 的数据结构它通过每个节点记录自己的长度且放在节点的尾部来彻底解决掉了 ziplist 存在的连锁更新的问题 listpack结构
Total Bytes为整个listpack的空间大小占用4个字节每个listpack最多占用4294967295Bytes。num-elements为listpack中的元素个数即Entry的个数占用2个字节element-1~element-N为每个具体的元素listpack-end-byte为listpack结束标志占用1个字节内容为0xFF。 相比于ziplist ziplist VS listpack
ziplist 和ziplist 列表项类似listpack 列表项也包含了元数据信息和数据本身。不过为了避免ziplist引起的连锁更新问题listpack 中的每个列表项 不再像ziplist列表项那样保存其前一个列表项的长度。 list Java中有ArrayList底层是由Object[]实现LinkedList底层是由放入Node节点的双端链表实现 redis中的list我们学习redis6和7两个版本 redis6quicklistziplist redis7quicklistlistpack redis6 (1) ziplist压缩配置list-compress-depth 0 表示一个quicklist两端不被压缩的节点个数。这里的节点是指quicklist双向链表的节点而不是指ziplist里面的数据项个数 参数list-compress-depth的取值含义如下 0: 是个特殊值表示都不压缩。这是Redis的默认值。 1: 表示quicklist两端各有1个节点不压缩中间的节点压缩。 2: 表示quicklist两端各有2个节点不压缩中间的节点压缩。 3: 表示quicklist两端各有3个节点不压缩中间的节点压缩。 依此类推… (2) ziplist中entry配置list-max-ziplist-size -2 当取正值的时候表示按照数据项个数来限定每个quicklist节点上的ziplist长度。比如当这个参数配置成5的时候表示每个quicklist节点的ziplist最多包含5个数据项。当取负值的时候表示按照占用字节数来限定每个quicklist节点上的ziplist长度。这时它只能取-1到-5这五个值 每个值含义如下 -5: 每个quicklist节点上的ziplist大小不能超过64 Kb。注1kb 1024 bytes -4: 每个quicklist节点上的ziplist大小不能超过32 Kb。 -3: 每个quicklist节点上的ziplist大小不能超过16 Kb。 -2: 每个quicklist节点上的ziplist大小不能超过8 Kb。-2是Redis给出的默认值 -1: 每个quicklist节点上的ziplist大小不能超过4 Kb。 在Redis3.0之前list采用的底层数据结构是ziplist压缩列表linkedList双向链表 然后在高版本的Redis中底层数据结构是quicklist(替换了ziplistlinkedList)而quicklist也用到了ziplist 结论quicklist就是「双向链表 压缩列表」组合因为一个 quicklist 就是一个链表而链表中的每个元素又是一个压缩列表 quicklist 实际上是 zipList 和 linkedList 的混合体它将 linkedList按段切分每一段使用 zipList 来紧凑存储多个 zipList 之间使用双向指针串接起来。 quicklist quicklist中*zl指向一个ziplist一个ziplist可以存放多个元素 redis7 listpack紧凑列表 是用来替代 ziplist 的新数据结构在 7.0 版本已经没有 ziplist 的配置了6.0版本仅部分数据类型作为过渡阶段在使用 t_list.c 创建object对象 发现6和7底层都是创建quicklist但6的quicklist装ziplist但7装的是listpack
set Redis用intset或hashtable存储set。如果元素都是整数类型就用intset存储。 如果不是整数类型就用hashtable数组链表的存来储结构。key就是元素的值value为null。 zset
redis6
ziplistskiplist 当有序集合中包含的元素数量超过服务器属性 server.zset_max_ziplist_entries 的值默认值为 128 或者有序集合中新添加元素的 member 的长度大于服务器属性 server.zset_max_ziplist_value 的值默认值为 64 时 redis会使用跳跃表作为有序集合的底层实现。 否则会使用ziplist作为有序集合的底层实现 redis7
listpackskiplist 当有序集合中包含的元素数量超过服务器属性 server.zset_max_listpack_entries 的值默认值为 128 或者有序集合中新添加元素的 member 的长度大于服务器属性 server.zset_max_listpack_value 的值默认值为 64 时 redis会使用跳跃表作为有序集合的底层实现。 否则会使用listpack作为有序集合的底层实现 跳表skiplist
相比于单链表 对于一个单链表来讲即便链表中存储的数据是有序的如果我们要想在其中查找某个数据也只能从头到尾遍历链表。 这样查找效率就会很低时间复杂度会很高O(N) 解决方法升维也叫空间换时间。 从这个例子里我们看出加来一层索引之后查找一个结点需要遍历的结点个数减少了也就是说查找效率提高了。 skiplist是一种以空间换取时间的结构。 由于链表无法进行二分查找因此借鉴数据库索引的思想提取出链表中关键节点索引先在关键节点上查找再进入下层链表查找提取多层关键节点就形成了跳跃表 but 由于索引也要占据一定空间的所以索引添加的越多空间占用的越多 优点 跳表是一个最典型的空间换时间解决方案而且只有在数据量较大的情况下才能体现出来优势。而且应该是读多写少的情况下才能使用所以它的适用范围应该还是比较有限的 缺点 维护成本相对要高 在单链表中一旦定位好要插入的位置插入结点的时间复杂度是很低的就是O(1) but 新增或者删除时需要把所有索引都更新一遍为了保证原始链表中数据的有序性我们需要先找 到要动作的位置这个查找操作就会比较耗时最后在新增和删除的过程中的更新时间复杂度也是O(log n) 设计跳表
class Skiplist {static final int MAX_LEVEL 32;//节点最大的层数不允许超过MAX_LEVELstatic final double P_FACTOR 0.25;//如果一个节点有第i层(i1)指针即节点已经在第1层到第i层链表中那么它有第(i1)层指针的概率为P_FACTOR//当P_FACTOR1/4时每个节点所包含的平均指针数目为1.33private SkiplistNode head;private int level;private Random random;public Skiplist() {this.head new SkiplistNode(-1, MAX_LEVEL);this.level 0;this.random new Random();}//search从跳表的当前的最大层数 level层开始查找在当前层水平地逐个比较直至当前节点的下一个节点大于等于目标节点然后移动至下一层进行查找// 重复这个过程直至到达第 1 层。此时若第 1 层的下一个节点的值等于 target则返回 true反之则返回 falsepublic boolean search(int target) {SkiplistNode curr this.head;for (int i level - 1; i 0; i--) {//从最高层开始找//当前层水平地逐个比较直至当前节点的下一个节点大于等于目标节点while (curr.forward[i] ! null curr.forward[i].val target) {curr curr.forward[i];}}curr curr.forward[0];/* 检测当前元素的值是否等于 target */if (curr ! null curr.val target) {return true;}return false;}public void add(int num) {SkiplistNode[] update new SkiplistNode[MAX_LEVEL];Arrays.fill(update, head);SkiplistNode curr this.head;for (int i level - 1; i 0; i--) {/* 找到第 i 层小于且最接近 num 的元素*/while (curr.forward[i] ! null curr.forward[i].val num) {curr curr.forward[i];}update[i] curr;}int lv randomLevel();level Math.max(level, lv);SkiplistNode newNode new SkiplistNode(num, lv);for (int i 0; i lv; i) {/* 对第 i 层的状态进行更新将当前元素的 forward 指向新的节点 */newNode.forward[i] update[i].forward[i];update[i].forward[i] newNode;}}public boolean erase(int num) {SkiplistNode[] update new SkiplistNode[MAX_LEVEL];SkiplistNode curr this.head;for (int i level - 1; i 0; i--) {/* 找到第 i 层小于且最接近 num 的元素*/while (curr.forward[i] ! null curr.forward[i].val num) {curr curr.forward[i];}update[i] curr;}curr curr.forward[0];/* 如果值不存在则返回 false */if (curr null || curr.val ! num) {return false;}for (int i 0; i level; i) {if (update[i].forward[i] ! curr) {break;}/* 对第 i 层的状态进行更新将 forward 指向被删除节点的下一跳 */update[i].forward[i] curr.forward[i];}/* 更新当前的 level */while (level 1 head.forward[level - 1] null) {level--;}return true;}private int randomLevel() {int lv 1;/* 随机生成 lv */while (random.nextDouble() P_FACTOR lv MAX_LEVEL) {lv;}return lv;}
}class SkiplistNode {int val;SkiplistNode[] forward;public SkiplistNode(int val, int maxLevel) {this.val val;this.forward new SkiplistNode[maxLevel];}
}
