Redis的⼏种数据结构五种数据类型对象
先看⼏种数据结构
通过分析底层的数据结构，学习如何根据场景选型和设计
1，简单动态字符串
redis使⽤的字符串SDS有别于C语⾔中的字符串
a, 结构
free字段为已分配但未使⽤的空间
len为已使⽤的空间（不计⼊'\0'）
buf为char数组
b, 与C字符串区别
redis的字符环结构可以理解为将C字符串封装了⼀层，通过加⼊的属性字段降低字符串操作的复杂度，提⾼安全性。
通过len属性可以在常数复杂度获取字符串的长度，仅通过len属性可直接获取长度，⽽C语⾔字符串复杂度需要遍历，长度为
O（N）。
⼆进制安全的。C字符串是ASCII编码的，以'\0'来判断字符串是否结束，如果数据中包含'\0'字符便会将数据截断，当做两个字符串，因此仅限于保存⽂本数据。redis字符串通过len属性来获取数据⽽不是通过遍历寻结束标志，因此可以存储任意内容的⼆进制数据。
兼容C字符串的操作。默认在字符串最后加'\0‘，使⽤C库字符串的部分操作。
避免缓冲区溢出。其实原理就是根据redis字符串的特点重写了C可能造成内存溢出的函数，如strcat拼接字符串函数，C语⾔中需⼈为保证⽬标字符串的空间⾜够⼤，否会造成溢出，⽽redis字符串通过free属性来⾃动判断是否可容纳源字符串，否则会扩展⾃⾝内存再拼接。
减少内存分配次数。空间和效率的问题，redis采⽤的是牺牲空间来换取效率的提升，避免多次的申请或释放内存。redis是kv型数据库，要求速度快，数据也多为频繁修改，因此牺牲⼀部分空间是可取的。它提供了两种策略，空间预分配和惰性释放。预分配指的是⼀个字符串修改后会同时分配⼀定⼤⼩的空间给free预留，避免再次修改分配内存。惰性释放是字符串缩短后不是放空间⽽是给free记录，避免释放空间。
预分配和惰性释放在memcache中也使⽤了，不过它是从内存管理的⾓度出发的。通过在初始化时对整个内存进⾏预分配，减少动态申请内存的操作带来的消耗，使⽤的内存都是连续的，避免了内存碎⽚，内存也不会回收⽽是通过内个slab的slot指针数组来保存。关于memcache的内存管理的机制具体见这⾥
c, 场景
该类型是字符串对象的⼀种实现⽅式，并⽤于AOF缓冲区和客户端输⼊缓冲区。
2，链表
redis使⽤的联表⽰标准的双端⽆环链表
a, 结构
其中，head和tail表⽰链表的表头和表尾节点，len表⽰链表中节点的数⽬，dup、free、match分别为复制、释放和对⽐函数。
b, 场景
链表结构的特点是可以快速的在表头和表尾插⼊和删除元素，但查复杂度⾼，是列表的底层实现之⼀，也因此列表没有提供判断某⼀元素是否在列表中的借⼝，因为在链表中查复杂度⾼。
3，字典
redis的字典使⽤哈希表作为底层实现。
a, 结构
上图为字典结构图
dict结构中，type表⽰是dicttype类型的指针，表⽰操作特定类型的键值对的函数，privdata是传给特定函数的可选参数。ht是包含两个哈希表的数组，ht[0]表⽰正常存放数据的hash表，⽽ht[1]⽤于rehash，rehashidx是记录了rehash的进度，正常情况下为-1。
dictht是哈希表，table表⽰哈希表数组，指针数组，size表⽰哈希表的⼤⼩，used表⽰已有节点的数⽬，used/size为负载因⼦，决定何时进⾏rehash。sizemask⽤于计算索引值。
每个哈希表元素是dictentry结构，key为键，value可以是⼀个指针或是⼀个整数。，next为指向下⼀个的指针。是传统的hash表。    b, rehash
redis使⽤murmurhash算法计算hash值，能有很好的随机分布性，速度也很快。
当负载因⼦⼤于3/2时进⾏扩容操作，扩容⼤⼩为第⼀个⼤于ht[0].used*2的2^n，当负载因⼦⼩于0.1进⾏缩容，为第⼀个⼤于
ht[0].used的2^n。
redis采⽤渐进式rehash，将rehash操作分摊到每次增删改查，具体过程见这⾥
c, 场景
字典是数据库和哈希对象的底层实现，数据库中dict存放所有kv，v可能是各种对象，⽽expire存放有过期时间的k和过期时间。⽤作hash底层时，k和v都是字符串对象。
4，跳跃表
跳跃表是⼀种可以快速访问节点的数据结构，性能接近于平衡术，且实现简单。
a, 结构
跳跃链表是⼀种随机化数据结构，基于并联的链表。跳跃列表是对有序的链表增加上附加的前进链接，增加是以随机化的⽅式进⾏的，所以在列表中的查可以快速的跳过部分列表。所有操作都以对数随机化的时间进⾏。
header和tail指向表头和表尾，level表⽰最⼤层级，length表⽰节点数⽬（不包括⾸节点）
每个节点都包含⼀个后退指针，⽤于从尾部遍历，路径唯⼀。obj为⼀个对象，score为对应的分值。level是⼤⼩随机出来的层级数组，每个层级包含⼀个前进指针和距离指向节点的跨度。跨度⽤于计算rank，跨度之和为rank。具体算法这⾥不介绍，具体见
b, 场景
跳跃表是有序集合的底层实现之⼀，跳跃表将指向有序集的 score 值和 member 域的指针作为元素， 并以 score 值为索引， 对有序集元素进⾏排序。
redis根据⾃⼰的需求对跳跃表做了更改：
1. score 值可重复。
2. 对⽐⼀个元素需要同时检查它的 score 和 memeber 。
3. 每个节点带有⾼度为 1 层的后退指针，⽤于从表尾⽅向向表头⽅向迭代，当执⾏ZREVRANGE或 ZREVRANGEBYSCORE 这类以
逆序处理有序集的命令时，就会⽤到这个属性。
5，整数集合
redis的整数集合实质上是动态的数组。reids的整数集合是可以根据整数的值，⾃动选择⽤什么长度来存储。
a, 结构
encoing标会编码⽅式，8/16/32/64位，length表⽰集合元素的数量，contents表⽰数据，元素由⼩到⼤排列。
b, 升级
当加⼊的数⼤于encoding对应的最⼤长度时，⾃动进⾏升级操作。流程是：⾸先扩展数组空间的⼤⼩。将原数组中的原书进⾏类型扩展并存储，最后将新插⼊的数放⼊对应位置。整数集合不做降级操作。
c, 场景
整数集合是redis集合对象的底层实现之⼀。当键数量⼩于512并且键值为整数时集合使⽤整数集合作为底层存储，节约内存。如何保证不重复？（待解决）。
6，压缩列表
redis使⽤压缩列表来存储⼩整数值或长度⽐较短的字符串redis支持的数据结构
压缩列表是为了节省内存开发的，是⼀系列特殊编码的连续内存块组成的顺序型数据结构。
a, 结构
zlbytes记录整个列表所占的内存数
zltail记录距离尾节点的距离
zllen记录节点数⽬
entry是每个节点
zlend列表结束标志
每个节点的组成，previous_entry_length是前⼀节点的长度，可⽤于从尾节点向前遍历，encoding记录content的数据类型和长度，content为节点的值。
b, 连锁更新
当插⼊或者删除元素时，会导致previous_entry_length的长度发⽣变化，如有1⼦节点为5字节，如果原先本节点的总⼤⼩处于250⾄253之间，会导致笑⼀个节点的previous..的长度发⽣变化，可能引起连锁更新的情况。需要不停的重复分配空间来存放增⼤的⼤⼩。
但redis中假定的是处于临界⼤⼩的数据很多并且连续这种情况⼏率很低，同事假定被更新的节点数⽬少。
c, 场景
redis使⽤压缩列表来作为列表键和哈希键的底层实现之⼀，存储⼩整数值或长度⽐较短的字符串时使⽤，previous_entry_length的存在使其可以像链表⼀样遍历。实现hash时顺序添加相邻接的节点为k和v。
1，redis对象的结构
type记录了对象的类型，可以使字符串，列表，哈希，集合和有序集合对象。
encoding记录的是type对象对应的底层实现，在redis中每种类型只有少两种底层实现的数据结构。通过不同的编码⽅式是redis可以根据不同的使⽤场景来选择不同的实现⽅式。同时不同编码在满⾜条件时会触发转换。
ptr是指向底层实现数据结构的指针。
2，字符串
字符串对象是使⽤最⼴泛的类型，如memcache中的kv的v相似。也是redis其他数据类型嵌套使⽤的对象类型。有三种编码⽅式：int、raw、embstr三种。
a, raw编码⽅式
字符串对象是⼤于39字节的字符串时则私⽤raw编码⽅式存储，即SDS。
b, smbstr编码⽅式
smbstr编码⽅式是专门保存短字符产的⼀种编码⽅式，与raw相似，但会调⽤⼀次内存分配函数申请redisobject和sdshdr，连续存储。但它是只读的，当对它修改时类型转换为raw编码⽅式。
c, int编码⽅式
ptr指向⼀个整数，当对已int编码⽅式编码的字符串对象进⾏append等操作时，会类型转换为sds类型。
d, 可进⾏的操作
在使⽤命令INCR系列（ INCR, DECR, INCRBY）命令时将字符串作为的原⼦计数器。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。