合肥建站公司有哪家招聘的,做行程好的网站,php网站页面转wordpress,8x8x域名解析ip地址查询文章目录 一、Redis数据结构概述1.1 Redis有哪些数据类型1.2 Redis本质是哈希表1.3 Redis的哈希冲突与渐进式rehash1.4 数据结构底层1.4.1 简单动态字符串SDS1.4.2 双向链表#xff08;后续已废弃#xff09;1.4.3 压缩列表ZipList1.4.4 哈希表HashTable1.4.5 跳表SkipList1.… 文章目录 一、Redis数据结构概述1.1 Redis有哪些数据类型1.2 Redis本质是哈希表1.3 Redis的哈希冲突与渐进式rehash1.4 数据结构底层1.4.1 简单动态字符串SDS1.4.2 双向链表后续已废弃1.4.3 压缩列表ZipList1.4.4 哈希表HashTable1.4.5 跳表SkipList1.4.6 整数数组IntSet1.4.7 RedisObject1.4.8 Redis的编码方式 二、String类型三、List列表类型3.1 简介3.2 数据结构3.3 压缩列表ZipList3.4 双向链表LinkedList后续已废弃3.5 快速链表QuickList 四、Set集合类型五、Hash哈希类型5.1 简介5.2 数据结构 六、ZSet类型6.1 简介6.2 什么时候采用压缩列表、什么时候采用跳表6.3 跳表6.3.1 跳表是什么what6.3.2 跳表怎么做的how6.3.3 为什么需要跳表WHY6.3.4 为什么用跳表而不用红黑树或者二叉树呢6.3.5 zset为什么用跳表而不用二叉树或者红黑树呢MySQL为什么不用跳表 七、Stream类型 还记得Redis五种数据类型、String、List、Set、Hash、ZSet吗如果忘记可以到这里重新温习
Redis基础超详解一 Redis定义、SQL与NoSQL区别、Redis常用命令、Redis五种数据类型、String、List、Set、Hash、ZSetRedis的Java客户端 Redis 是一款开源的内存中的数据结构存储系统它可以用作数据库、缓存和消息代理。Redis 支持多种类型的数据结构如字符串String、哈希Hash、列表List、集合Set、有序集合Sorted Set、位图Bitmap、HyperLogLog 和地理空间索引Geospatial。这些数据结构提供了丰富的操作使得 Redis 能够应对各种各样的场景。本文将详细介绍 Redis 的各种数据结构包括它们的特性、底层实现、常用命令以及应用场景。 一、Redis数据结构概述
1.1 Redis有哪些数据类型
Redis是一个key-value的数据库key一般是String类型不过value的类型多种多样包含 6 种基本类型——String字符串、List列表、Hash哈希、Set集合、Sorted Set有序集合、Stream流、Redis5.0引入和三种特殊类型——geospatial地理位置、Bitmap位存储、HyperLog基数统计。
数据结构的底层实现底层数据结构一共有 6 种分别是简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组。 从上图可以看出String 的底层是简单动态字符串List 的底层是双向链表和压缩链表Set 的底层是整数数组和哈希表Hash 的底层是压缩链表和哈希表Sorted Set 底层压缩链表和跳表。即 String 类型的底层实现只有一种数据结构也就是简单动态字符串。而 List、Set、Hash 和 Sorted Set这四种数据类型都有两种底层实现结构。通常情况下我们会把这四种类型称为集合类型它们的特点是一个键对应了一个集合的数据。
Redis 之所以采用不同的数据结构其实是在性能和内存使用效率之间的平衡。
1.2 Redis本质是哈希表
Redis 本身是一个键值对数据库这种键值对的存储方式就是哈希映射Hashmap的一种体现即通过键Key来快速查找对应的值Value。
一个哈希表其实就是一个数组数组的每个元素称为一个哈希桶。也就是说一个哈希表是由多个哈希桶组成的每个哈希桶中保存了键值对数据不管是键类型还是值类型哈希桶中的元素保存的都不是值本身而是指向具体值的指针
根据下图可看出哈希桶中的 entry 元素中保存了 ‘*key’ 和 *value ’ 指针分别指向了实际的键和值这样一来即使值是一个集合也可以通过 *value 指针被查找到 因为这个哈希表保存了所有的键值对所以它也叫做全局哈希表。 哈希表的最大好处是可以用 O(1) 的时间复杂度来快速查找到键值对——我们只需要计算键的哈希值就可以知道它对应的哈希桶位置然后就可以访问相应的 Entry元素 这个查找过程主要依赖于哈希计算和数据量的多少并没有直接关系。也就是说不管哈希表里有 10 万个键还是 100 万个键我们只需要一次计算就能找到相应的键。
也就是说整个数据库就是一个全局 Hash 表而 Hash 表的时间复杂度就是 O(1)只需要计算每个键的 Hash 值就知道对应的 Hash 桶位置定位桶里面的 Entry 找到对应数据这个也是 Redis 快的原因之一。
但如果我们只是了解哈希表 O(1) 复杂度和快速查找特性那么当我们向 Redis 中写入大量数据之后就可能发现 操作有时候会突然变慢了。原因是哈希表的冲突问题和 rehash 可能带来的操作阻塞。
1.3 Redis的哈希冲突与渐进式rehash
Redis 使用哈希表作为其底层数据结构哈希冲突是哈希表中常见的问题。当两个或更多的键被哈希函数映射到同一个哈希桶时就会发生哈希冲突。Redis 通过链地址法来解决哈希冲突即在每个哈希桶中维护一个链表所有哈希到同一个桶的键值对都存储在这个链表中。
当哈希表中的元素数量增长到一定程度或者哈希表中的元素数量减少到一定程度Redis 会触发哈希表的扩容或收缩这个过程称为 rehash。为了避免 rehash 过程中一次性复制所有元素导致的长时间阻塞Redis 使用了一种称为“渐进式 rehash”的策略。
在渐进式 rehash 过程中Redis 会同时维护新旧两个哈希表并在每次对哈希表进行操作时将一部分桶从旧哈希表移动到新哈希表。同时为了保证查询操作的正确性Redis 在查询时会同时查找新旧两个哈希表。这样通过分摊在一段时间内完成 rehash避免了一次性操作带来的性能问题。
1.4 数据结构底层
1.4.1 简单动态字符串SDS
我们都知道Redis中保存的Key是字符串value往往是字符串或者字符串的集合。可见字符串是Redis中最常用的一种 数据结构。
不过Redis没有直接使用C语言中的字符串因为C语言字符串存在很多问题。在C语言中定义字符串 char *str message本质是字符数组 {‘m’, ‘e’, ‘s’, ‘s’, ‘a’, ‘g’, ‘e’, ‘\0’}。它会存储如下图的样子 以“\0”代表结束。这样就会产生以下问题
无法存储“\0”这种特殊字符因为“\0”代表结束非二进制安全每次字符串扩容和缩容都需要使用新的char数组没有记录字符串的长度每次都需要进行遍历到结束、或者通过运算 才能知道长度。不可修改
Redis构建了一种新的字符串结构称为简单动态字符串Simple Dynamic String简称SDS。Redis是C语言实现的
例如我们执行命令set name 大哥那么Redis将在底层创建两个SDS其中一个是包含“name”的SDS另一个是包含“大哥”的SDS。 SDS优点
获取字符串长度的时间复杂度为O(1)支持动态扩容减少内存分配次数二进制安全。遍历字符串时不是以介绍标识为标记、而是以长度为基准 len目前已使用的长度allocbuf的总长度就是已经分配空间的长度;flagssds的类型用低三位标识高5位暂时不用。sdshdr5这种类型该字段为空sdshdr8、sdshdr16、sdshdr32、sdshdr64用标识进行表示。buf保存具体的字符串。注意这里也会以\0结尾但它不会计算在len中。
1.4.2 双向链表后续已废弃
1.4.3 压缩列表ZipList
ZipList是一种特殊的“双端链表”并非链表由一系列特殊编码的连续内存块组成像内存连续的数组。可以在任意一端进行压入/弹出操作并且该操作的时间复杂度为O(1)。 压缩列表 底层数据结构本质是一个数组增加了列表长度、尾部偏移量、列表元素个数、以及列表结束标识有利于快速寻找列表的首尾节点但对于其他正常的元素如元素2、元素3只能一个个遍历效率仍没有很高效。 属性类型长度说明zlbytesuint32_t4字节一个 4 字节的整数表示整个压缩列表占用的字节数量包括 zlbytes 自身的大小zltailuint32_t4字节一个 4 字节的整数记录压缩列表表尾节点距离压缩列表的起始地址有多少字节通过这个偏移量可以确定表尾节点的地址zllenuint16_t2字节一个 2 字节的整数表示压缩列表中的节点数量。最大值为UINT16_MAX65534如果超过这个数此处会记录为65535但节点的真实数量需要遍历整个压缩列表才能计算出entry列表节点不定压缩列表中的元素每个元素都由一个或多个字节组成节点的长度由节点保存的内容决定。每个元素的第一个字节又称为entry header用于表示这个元素的长度以及编码方式zlenduint8_t1字节一个字节特殊值0xFF十进制255表示压缩列表的结束 注意 如果查找定位首个元素或最后1个元素可以通过表头 “zlbytes”、“zltail_offset” 元素快速获取复杂度是 O(1)。但是查找其他元素时就没有这么高效了只能逐个查找下去比如 entryN 的复杂度就是 O(N) ZipList虽然节省内存但申请内存必须是连续空间如果内存占用较多申请效率较低。
1.4.4 哈希表HashTable Redis 的散列表hashtable是一种常见的键值对映射结构它通过一个散列函数将键映射到一个桶中然后在桶中进行查找。Redis 的散列表使用链表法解决哈希冲突即当多个键映射到同一个桶时将它们存储在同一个链表中。
在Redis的源代码中散列表的结构定义如下
typedef struct dictEntry {void *key;void *val;struct dictEntry *next;
} dictEntry;typedef struct dictht {dictEntry **table;unsigned long size;unsigned long sizemask;unsigned long used;
} dictht;typedef struct dict {dictht ht[2];long rehashidx; /* rehashing not in progress if rehashidx -1 */int iterators; /* number of iterators currently running */
} dict;其中 dictEntry 结构体表示散列表中的一个节点包含键key、值val和指向下一个节点的指针next。 dictht 结构体表示一个散列表包含指向哈希表数组的指针table、哈希表数组的大小size、哈希表数组大小掩码sizemask和已使用的节点数量used。 dict 结构体表示一个字典包含两个散列表ht、当前进行 rehash 的索引rehashidx和当前运行的迭代器数量iterators。
1.4.5 跳表SkipList
**SkipList跳表**首先是链表在链表的基础上增加了多级索引通过多级索引位置的转跳实现了快速查找元素。但与传统链表相比有几点差异
元素按照升序排列存储节点可能包含多个指针指针跨度不同 普通链表想查找元素27只能从链表头部一个个往后遍历需要遍历6次 才能找到元素27 跳表怎么做的how建立多级索引
如建立一级索引 如果觉得慢可以建立二级索引 当数据量特别大的时候跳表的时间复杂度为 O(logN)。其本身利用的思想有点类似于二分法。
SkipList的特点
跳跃表是一个双向链表每个节点都包含score和ele值节点按照score值排序score值一样则按照ele字典排序每个节点都可以包含多层指针层数是1到32之间的随机数不同层指针到下一个节点的跨度不同层级越高跨度越大增删改查效率与红黑树基本一致实现却更简单
1.4.6 整数数组IntSet
IntSet是Redis中set集合的一种实现方式基于整数数组来实现并且具备长度可变、有序等特征。 int8_t int表示整数、8表示8bit位即1个字节
为了方便查找Redis会将intset中所有的整数按照升序依次保存在contents数组中结构如图 IntSet升级
现在假设有一个intSet元素为{5,1020}采用的编码是INTSET_ENC_INT16则每个整数占2字节 我们向该其中添加一个数字50000这个数字超出了int16_t的范围intset会自动升级编码方式到合适的大小。以当前案例来说流程如下
升级编码为INTSET_ENC_INT32每个整数占4字节并按照新的编码方式及元素个数扩容数组倒序依次将数组中的元素拷贝到扩容后的正确位置将待添加的元素放入数组末尾最后将inset的encoding属性改为INTSET_ENC_INT32将length属性改为4 1.4.7 RedisObject
Redis中的任意数据类型的键和值都会被封装为一个RedisObject也叫做Redis对象源码如下 1.4.8 Redis的编码方式
Redis中会根据存储的数据类型不同选择不同的编码方式共包含11种不同类型
编号编码方式说明0OBJ_ENCODING_RAWraw编码动态字符串1OBJ_ENCODING_INTlong类型的整数的字符串2OBJ_ENCODING_HThash表字典dict3OBJ_ENCODING_ZIPMAP已废弃4OBJ_ENCODING_LINKEDLIST双端链表后续已废弃5OBJ_ENCODING_ZIPLIST压缩列表6OBJ_ENCODING_INTSET整数集合7OBJ_ENCODING_SKIPLIST跳表8OBJ_ENCODING_EMBSTRembstr的动态字符串9OBJ_ENCODING_QUICKLIST快速列表10OBJ_ENCODING_STREAMStream流
五种数据结构
Redis中会根据存储的数据类型不同选择不同的编码方式。每种数据类型的使用的编码方式如下
数据类型编码方式OBJ_STRINGint、embstr、rawOBJ_LISTLinkedList和ZipList(3.2以前、QuickList3.2以后OBJ_SETintset、HTOBJ_ZSETZipList、HT、SkipListOBJ_HASHZipList、HT
二、String类型
详细介绍Redis五种数据类型、String、List、Set、Hash、ZSet
String 是 Redis 最简单的数据类型也是最常用的数据类型。它可以包含任何数据包括字符串、整数或者浮点数。在 Redis 中字符串的最大长度可以达到 512MB。
应用场景
缓存将查询结果、页面内容等缓存在 Redis 的 String 结构中提高系统访问速度。计数器Redis String 结构可以将字符串解析为整数进行自增或自减操作适合做各种计数器。分布式锁利用 Redis String 结构的原子性操作可以实现分布式锁。
底层结构Redis 的 String 类型是二进制安全的基于简单动态字符串SDS实现它的底层实际上是一个字节数组因此 String 类型可以包含任何数据例如 jpg 图片或者序列化的对象。 在Redis实现中并没有直接采用C语言的字符串而是自定义了一个SDS简单动态字符串的结构体来标识字符串。
在C语言中定义字符串 char *str message它会存储如下图的样子 以“\0”代表结束。这样就会产生以下问题
无法存储“\0”这种特殊字符因为“\0”代表结束每次字符串扩容和缩容都需要使用新的char数组没有记录字符串的长度每次都需要进行遍历到结束才能知道长度。
redis要解决上述问题就自定义了一个SDS结构如下图 len目前已使用的长度allocbuf的总长度就是已经分配空间的长度;flagssds的类型用低三位标识高5位暂时不用。sdshdr5这种类型该字段为空sdshdr8、sdshdr16、sdshdr32、sdshdr64用标识进行表示。buf保存具体的字符串。注意这里也会以\0结尾但它不会计算在len中。
redis可以根据字符串的大小使用不同类型的sds这样可以进一步的节省内存。这里不需要担心buf的长度不够用2的64次幂是一个非常巨大的数字同时redis默认也会限制最大的字符为512M在6.3版本开始可以对最大限制字符大小进行配置。注意使用不同类型的sds并不是一次性分配这么多空间而是逐步分配的例如使用sdshdr16这种类型存入一个长度为14的字符串那么会根据存入的字符串长度预留空闲长度这里是14如果字符串大小超过1M那么预留空间就是1M。
redis除了自定义了SDS类型来存储字符串还定义了三种编码
int8字节的长整形值时数字类型并且数字长度小于20embstr长度小于等于44字节的字符串3.2版本之前是39字节raw长度大于44字节的字符串。
三、List列表类型
3.1 简介
详细介绍Redis五种数据类型、String、List、Set、Hash、ZSet
Redis中的List类型与Java中的LinkedList类似可以看做是一个双向链表结构按插入顺序排序你可以添加一个元素到头部左边或尾部右边。既可以支持正向检索和也可以支持反向检索。特征也与LinkedList类似有序、元素可重复、插入和删除快、查询速度一般。在 Redis 中列表最多可以包含 2^32 - 1 个元素。
应用场景
消息队列可以利用 List 的 push 和 pop 操作实现生产者消费者模型。时间线、动态消息比如微博的时间线可以将最新的内容放在 List 的最前面。常用来存储一个有序数据例如朋友圈点赞列表评论列表等
底层结构
在3.2版本之前Redis List底层采用压缩链表ZipList和双向链表LinkedList来实现List。当元素数量小于512并且元素大小小于64字节时采用ZipList编码超过则将自动采用LinkedList编码在3.2版本之后Redis统一采用快速链表QuickList来实现List
3.2 数据结构
Redis的List结构类似一个双端链表可以从首、尾操作列表中的元素
在Redis 3.2版本之前Redis List底层采用压缩链表ZipList和双向链表LinkedList来实现List。当元素数量小于512个并且元素大小小于64字节时采用ZipList编码超过则将自动采用LinkedList编码。在3.2版本之后Redis统一采用快速链表QuickList结构来实现List
QuickList结构如下 在 Redis3.2 版本前Redis 列表 List 使用两种数据结构作为底层实现
压缩列表 ZipList插入元素过多或字符串太大就需要调用 Realloc 扩展内存双向链表 LinkedList需附加指针 Prev 和 Next较浪费空间加重内存的碎片化
3.3 压缩列表ZipList
在 Redis3.2 版本前 压缩列表不仅是 List 的底层实现之一同时也是 Hash、 ZSet 两种数据类型底层实现之一。
ZipList是一种特殊的“双端链表”并非链表由一系列特殊编码的连续内存块组成像内存连续的数组。可以在任意一端进行压入/弹出操作并且该操作的时间复杂度为O(1)。 压缩列表 底层数据结构本质是一个数组增加了列表长度、尾部偏移量、列表元素个数、以及列表结束标识有利于快速寻找列表的首尾节点但对于其他正常的元素如元素2、元素3只能一个个遍历效率仍没有很高效。
当我们的 List 列表数据量比较少的时候且存储的数据轻量的如小整数值、短字符串时候 Redis 就会通过压缩列表来进行底层实现。 属性类型长度说明zlbytesuint32_t4字节一个 4 字节的整数表示整个压缩列表占用的字节数量包括 zlbytes 自身的大小zltailuint32_t4字节一个 4 字节的整数记录压缩列表表尾节点距离压缩列表的起始地址有多少字节通过这个偏移量可以确定表尾节点的地址zllenuint16_t2字节一个 2 字节的整数表示压缩列表中的节点数量。最大值为UINT16_MAX65534如果超过这个数此处会记录为65535但节点的真实数量需要遍历整个压缩列表才能计算出entry列表节点不定压缩列表中的元素每个元素都由一个或多个字节组成节点的长度由节点保存的内容决定。每个元素的第一个字节又称为entry header用于表示这个元素的长度以及编码方式zlenduint8_t1字节一个字节特殊值0xFF十进制255表示压缩列表的结束 注意 如果查找定位首个元素或最后1个元素可以通过表头 “zlbytes”、“zltail_offset” 元素快速获取复杂度是 O(1)。但是查找其他元素时就没有这么高效了只能逐个查找下去比如 entryN 的复杂度就是 O(N) ZipList虽然节省内存但申请内存必须是连续空间如果内存占用较多申请效率较低。
3.4 双向链表LinkedList后续已废弃
3.5 快速链表QuickList
QuickList底层 LinkedList ZipList可以从双端访问内存占用较低保含多个ZipList存储上限高。其特点
是一个节点为ZipList的双端链表节点采用ZipList解决了传统链表的内存占用问题控制了ZipList大小解决连续内存空间申请效率问题中间节点可以压缩进一步节省了内存 ZipList虽然节省内存但申请内存必须是连续空间如果内存占用较多申请效率较低。 四、Set集合类型
详细介绍Redis五种数据类型、String、List、Set、Hash、ZSet
Set 是 Redis 的一种数据类型它是字符串类型的无序集合不一定确保元素有序可以满足元素唯一、查询效率要求极高。和列表一样你可以添加、删除、查找元素。但它保证每个元素只出现一次。在 Redis 中集合最多可以包含 2^32 - 1 个元素。满足下列特点
不保证有序性保证元素唯一可以判断元素是否存在求交集、并集、差集
应用场景
社交网络中的好友关系、共同好友、二度好友等功能。利用集合支持的交集、并集、差集等操作可以计算共同喜好、全部的喜好、自己独有的喜好等。
底层结构
Redis Set 的底层实现为整数集合和哈希表两种当集合中的元素都是整数且元素数量较少时Redis 会选择整数集合作为底层实现这样可以更加节省内存当数据量变大或者集合中的元素不全是整数时Redis 会自动将底层实现从整数集合切换为哈希表类似于Java 中hashset是基于hashmap实现的
为了查询效率和唯一性Set采用HT编码Dict。Dict中的key用来存储元素Value统一为null。当存储的所有数据都是整数并且元素数量不超过set-max-intset-entries时Set会采用lntSet编码以节省内存。 注意事项
集合中的元素是无序的如果需要获取有序的数据可以使用 Sorted Set 数据类型。集合中的元素不允许重复如果需要存储重复元素可以使用 List 数据类型。
五、Hash哈希类型
5.1 简介
详细介绍Redis五种数据类型、String、List、Set、Hash、ZSet
Hash 是 Redis 的一种数据类型也叫散列其value是一个无序字典类似于Python 的字典、Java中的HashMap结构。它是键值对集合是一个字符串字段和字符串值之间的映射表其字段和值的最大长度都是 512MB。在 Redis 中哈希可以存储超过 4 亿个键值对。
String结构是将对象序列化为JSON字符串后存储当需要修改对象某个字段时很不方便
KEYVALUEjw:user:1{name:“Jack”, age:21}jw:product:1{name:“Rose”, age:18}
Hash结构可以将对象中的每个字段独立存储可以针对单个字段做CRUD只需要通过key field找到 Hash结构与Redis中的Zset非常类似
都是键值存储都需求根据键获取值键必须唯一
区别如下
zset的键是member值是scorehash的键和值都是任意值zset要根据score排序hash则无需排序
因此Hash底层采用的编码与ZSet也基本一致只需要把排序有关的SkipList去掉即可 应用场景
存储对象Hash 结构可以看作是 String 类型的 field 和 value 的映射表非常适合用于存储对象。例如你可以使用 Hash 类型存储用户的信息如用户名、密码、邮箱等数据缓存可以将数据库中的一条记录映射成一个 Hash 结构Hash 的每个字段对应记录的每个列数据分析你可以使用 Hash 类型存储各种统计数据例如用户的行为数据然后进行数据分析社交网络在社交网络应用中你可以使用 Hash 类型存储用户的朋友列表、粉丝列表等
底层结构
Hash底层采用的编码与ZSet也基本一致只需要把排序有关的SkipList去掉即可。Redis Hash 的底层实现为压缩列表和哈希表两种当 Hash 中的元素个数较少且每个元素的大小较小的时候Redis 会选择压缩列表作为底层实现这样可以更加节省内存当数据量变大时Redis 会自动将底层实现从压缩列表切换为哈希表。
Hash结构默认采用ZipList编码用以节省内存。ZipList中相邻的两个entry分别保存field和value当数据量较大时Hash结构会转为HT编码也就是Dict触发条件有两个 ZipList中的元素数量超过了hash-max-ziplist-entries默认512ZipList中的任意entry大小超过了hash-max-ziplist-value默认64字节 5.2 数据结构
Redis 的 Hash 类型的底层实现是一个非常优化的数据结构它会根据实际情况选择使用紧凑的**压缩列表ziplist或者散列表hashtable**作为底层实现。
Hash结构默认采用ZipList编码用以节省内存。ZipList中相邻的两个entry分别保存field和value当数据量较大时Hash结构会转为HT编码也就是Dict触发条件有两个 ZipList中的元素数量超过了hash-max-ziplist-entries默认512ZipList中的任意entry大小超过了hash-max-ziplist-value默认64字节
Redis 的 Hash 类型会根据实际情况在压缩列表ziplist和散列表hashtable之间进行切换这主要取决于两个配置参数hash-max-ziplist-entries 和 hash-max-ziplist-value。 hash-max-ziplist-entries这个参数用于设置压缩列表可以存储的最大节点数量。如果一个 Hash 类型的元素数量超过这个值那么就会从压缩列表切换到散列表。默认值为 512 hash-max-ziplist-value这个参数用于设置压缩列表中每个节点的最大值大小以字节为单位。如果一个 Hash 类型的任何元素的大小超过这个值那么就会从压缩列表切换到散列表。默认值为 64。
这两个参数都可以在 Redis 的配置文件中进行设置。通过调整这两个参数你可以根据自己的应用特性选择更倾向于节省内存还是更倾向于提高性能。 从压缩列表转换到散列表当 Hash 类型存储的字段和值的数量超过 hash-max-ziplist-entries 的值或者任何字段或值的大小超过 hash-max-ziplist-value 的值时Redis 会将底层结构从压缩列表转换为散列表。这个过程是自动进行的对用户来说是透明的。 从散列表转换到压缩列表一旦 Hash 类型的底层结构被转换为散列表就无法再转换回压缩列表。这是因为散列表的性能更高而且在大多数情况下一旦一个 Hash 类型的大小超过了一定的阈值那么它的大小就很可能会继续增长。
压缩列表ziplist与散列表hashtable的详细介绍 可见本文1.4章节。
六、ZSet类型
6.1 简介
详细介绍Redis五种数据类型、String、List、Set、Hash、ZSet
ZSet有序集合也就是SortedSet其中每一个元素都需要指定一个score值和member值。它是一个可排序的set集合在 Set 的基础上增加了一个权重参数 score使得集合中的元素能够按 score 进行有序排列。在 Redis 中有序集合的最大成员数是 2^32 - 1。ZSet具备下列特性
可排序。根据score值排序元素不重复member必须唯一查询速度快也可以根据member查询分数
因为ZSet的可排序特性经常被用来实现排行榜这样的功能。 应用场景
排行榜应用有序集合使得我们能够方便地实现排行榜比如网站的文章排行、学生成绩排行等。带权重的消息队列可以通过 score 来控制消息的优先级。
底层结构
ZSet与Java中的TreeSet有些类似但底层数据结构却差别很大。ZSet中的每一个元素都带有一个score属性可以基于score属性对元素排序底层的实现是一个跳表SkipList加 hash表。注意集合成员是唯一的但是评分可以重复。 Redis ZSet 的底层实现为跳跃列表和哈希表两种跳跃列表保证了元素的排序和快速的插入性能哈希表则提供了快速查找的能力。 当元素数量不多时HT和SkipList的优势不明显而且更耗内存。因此zset还会采用ZipList结构来节省内存不过需要同时满足两个条件 元素数量小于zset_max_ziplist_entries默认值128每个元素都小于zset_max_ziplist_value字节默认值64 补充ziplist本身没有排序功能而且没有键值对的概念因此需要有zset通过编码实现
ZipList是连续内存因此score和element是紧挨在一起的两个entryelement在前score在后score越小越接近队首score越大越接近队尾按照score值升序排列 注意事项
有序集合中的元素是唯一的但分数score可以重复。插入、删除、查找的时间复杂度都是 O(log(N))。对于获取排名排行榜的操作Redis 有序集合是非常高效的。
6.2 什么时候采用压缩列表、什么时候采用跳表
什么时候采用压缩列表、什么时候采用跳表呢
有序集合保存的元素数量小于128个有序集合保存的所有元素的长度小于64字节
上述 1且2的时候采用压缩列表否则采用跳表
6.3 跳表
学习一个新知识从三方面分析WHAT、WHY、HOW
6.3.1 跳表是什么what
**SkipList跳表**首先是链表在链表的基础上增加了多级索引通过多级索引位置的转跳实现了快速查找元素。但与传统链表相比有几点差异
元素按照升序排列存储节点可能包含多个指针指针跨度不同 SkipList的特点
跳跃表是一个双向链表每个节点都包含score和ele值节点按照score值排序score值一样则按照ele字典排序每个节点都可以包含多层指针层数是1到32之间的随机数不同层指针到下一个节点的跨度不同层级越高跨度越大增删改查效率与红黑树基本一致实现却更简单
普通链表想查找元素27只能从链表头部一个个往后遍历需要遍历6次 才能找到元素27 6.3.2 跳表怎么做的how
跳表怎么做的how建立多级索引
如建立一级索引 如果觉得慢可以建立二级索引 当数据量特别大的时候跳表的时间复杂度为 O(logN)。其本身利用的思想有点类似于二分法。
6.3.3 为什么需要跳表WHY
因为普通链表查找一个元素 时间复杂度O(n)而跳表查找的时间复杂度为O(logn)查找速度更快。不仅如此删除、插入等操作的时间复杂度也是O(logn)
6.3.4 为什么用跳表而不用红黑树或者二叉树呢
红黑树、二叉树查找一个元素的时间复杂度也是O(logn) ZSet有个核心操作范围查找跳表效率比红黑树高跳表可以做到 logn 时间复杂度内快速查找找到区间起点、依次往后遍历即可但红黑树范围查找的效率没有跳表高每一层加了指针跳表实现比红黑树及平衡二叉树简单、易懂可以有效控制跳表的索引层级来控制内存的消耗
6.3.5 zset为什么用跳表而不用二叉树或者红黑树呢MySQL为什么不用跳表
Redis是直接操作内存的、并不需要磁盘io而MySQL需要去读取磁盘io所以MySQL使用b树的方式去减少磁盘io。B树原理是 叶子节点存储数据、非叶子节点存储索引每次读取磁盘页时就会读取一整个节点每个叶子节点还要指向前后节点的指针其目的是最大限度地降低磁盘io
数据在内存种读取 耗费的时间是磁盘IO读取的百万分之一而Redis是内存中读取数据、不涉及IO因此使用了跳表跳表模型是更快更简单的方式
七、Stream类型
Stream 是 Redis 5.0 版本引入的新特性它是一种类似于日志系统的数据结构用于存储多个键值对的列表每个键值对都会被分配一个自动递增的ID。Stream 主要用于实现消息队列的功能如 Apache Kafka。
应用场景
消息队列Stream 可以作为生产者消费者模型的一种实现生产者添加消息到 Stream消费者从 Stream 中读取消息并处理。日志记录由于 Stream 中的每个元素都有唯一的 ID并且这个 ID 是自动递增的因此非常适合用来记录日志。
底层结构
Redis Stream 的底层实现为一种叫做快速列表quicklist的数据结构这是一种同时包含了压缩列表ziplist和双向链表特性的数据结构既可以利用压缩列表节省内存又可以利用双向链表在两端进行快速的添加、删除操作。
常用命令
XADD key ID field value [field value …]向 Stream 中添加元素。
XRANGE key start end [COUNT count]获取 Stream 中指定范围的元素。
XREAD [COUNT count] [BLOCK milliseconds] STREAMS key [key …] ID [ID …]从 Stream 中读取数据。
XDEL key ID [ID …]从 Stream 中删除指定 ID 的元素。
XLEN key获取 Stream 中的元素数量。注意事项
Stream 是 Redis 中唯一一个可以安全地进行多个写入操作的数据结构因为每个元素都有一个唯一的、自动递增的 ID。Stream 中的元素一旦被添加就不能被修改只能被删除。
参考 Redis数据结构Hash类型全面解析、Redis数据结构List类型全面解析
