redis的zset的底层实现_图解redis五种数据结构底层实现（动
图哦）
redis有五种基本数据结构：字符串、hash、set、zset、list。但是你知道构成这五种结构的底层数据结构是怎样的吗？ 今天我们来花费五分钟的时间了解⼀下。 (⽬前redis版本为3.0.6)
动态字符串SDS
SDS是"simple dynamic string"的缩写。 redis中所有场景中出现的字符串，基本都是由SDS来实现的
所有⾮数字的key。例如 setmsg"hello world" 中的key msg.字符串数据类型的值。例如`` set msg "hello world"中的msg的值"hello wolrd"⾮字符串数据类型中的“字符串值”。例如 RPUSH fruits"apple""banana""cherry"中的"apple" "banana" "cherry"SDS长这样：
free：还剩多少空间 len：字符串长度 buf：存放的字符数组
空间预分配
为减少修改字符串带来的内存重分配次数，sds采⽤了“⼀次管够”的策略：
若修改之后sds长度⼩于1MB，则多分配现有len长度的空间若修改之后sds长度⼤于等于1MB，则扩充除了满⾜修改之后的长度外，额外多1MB空间
惰性空间释放
为避免缩短字符串时候的内存重分配操作，sds在数据减少时，并不⽴刻释放空间。
int
就是redis中存放的各种数字 包括⼀下这种，故意加引号“”的
双向链表
长这样：
分两部分，⼀部分是“统筹部分”：橘黄⾊，⼀部分是“具体实施⽅“：蓝⾊。
主体”统筹部分“：
head指向具体双向链表的头tail指向具体双向链表的尾len双向链表的长度具体"实施⽅"：⼀⽬了然的双向链表结构，有前驱 pre有后继next
由 list和 listNode两个数据结构构成。
ziplist
压缩列表。 redis的列表键和哈希键的底层实现之⼀。此数据结构是为了节约内存⽽开发的。和各种语⾔的数组类似，它是由连续的内存块组成的，这样⼀来，由于内存是连续的，就减少了很多内存碎⽚和指针的内存占⽤，进⽽节约了内存。
然后⽂中的 entry的结构是这样的：
元素的遍历
先到列表尾部元素：
然后再根据ziplist节点元素中的 previous_entry_length属性，来逐个遍历:
连锁更新
再次看看 entry元素的结构，有⼀个 previous_entry_length字段，他的长度要么都是1个字节，要么都是5个字节：
前⼀节点的长度⼩于254字节，则 previous_entry_length长度为1字节前⼀节点的长度⼩于254字节，则 previous_entry_length长度为5字节假设现在存在⼀组压缩列表，长度都在250字节⾄253字节之间，突然新增⼀新节点 new， 长度⼤于等于254字节，会出现：
程序需要不断的对压缩列表进⾏空间重分配⼯作，直到结束。
除了增加操作，删除操作也有可能带来“连锁更新”。 请看下图，ziplist中所有entry节点的长度都在250字节⾄253字节之间，big节点长度⼤于254字节，small节点⼩于254字节。
哈希表
哈希表略微有点复杂。哈希表的制作⽅法⼀般有两种，⼀种是： 开放寻址法，⼀种是 拉链法。redis的哈希表的制作使⽤的是 拉链法。
整体结构如下图：
也是分为两部分：左边橘黄⾊部分和右边蓝⾊部分，同样，也是”统筹“和”实施“的关系。 具体哈希表的实现，都是在蓝⾊部分实现的。 先来看看蓝⾊部分：
这也分为左右两边“统筹”和“实施”的两部分。
右边部分很容易理解：就是通常拉链表实现的哈希表的样式；数组就是bucket，⼀般不同的key⾸先会定位到不同的bucket，若key重复，就⽤链表把冲突的key串起来。
新建key的过程：
假如重复了:
rehash
再来看看哈希表总体图中左边橘黄⾊的“统筹”部分，其中有两个关键的属性： ht和 rehashidx。 ht是⼀个数组，有且只有俩元素ht[0]和ht[1]；其中，ht[0]存放的是redis中使⽤的哈希表，⽽ht[1]和rehashidx和哈希表的 rehash有关。
rehash指的是重新计算键的哈希值和索引值，然后将键值对重排的过程。
加载因⼦(load factor)=ht[0].used/ht[0].size。
扩容和收缩标准
扩容：
没有执⾏BGSAVE和BGREWRITEAOF指令的情况下，哈希表的 加载因⼦⼤于等于1。正在执⾏BGSAVE和BGREWRITEAOF指令的情况下，哈希表的 加载因⼦⼤于等于5。收缩:
加载因⼦⼩于0.1时，程序⾃动开始对哈希表进⾏收缩操作。扩容和收缩的数量
扩容：
第⼀个⼤于等于 ht[0].used*2的 2^n(2的n次⽅幂)。收缩：
第⼀个⼤于等于 ht[0].used的 2^n(2的n次⽅幂)。(以下部分属于细节分析，可以跳过直接看扩容步骤)
对于收缩，我当时陷⼊了疑虑：收缩标准是 加载因⼦⼩于0.1的时候，也就是说假如哈希表中有4个元素的话，哈希表的长度只要⼤于40，就会进⾏收缩，假如有⼀个长度⼤于40，但是存在的元素为4即( ht[0].used为4)的哈希表，进⾏收缩，那收缩后的值为多少？
我想了⼀下：按照前⽂所讲的内容，应该是4。 但是，假如是4，存在和收缩后的长度相等，是不是⼜该扩容？ 翻开源码看看：
收缩具体函数:
int dictResize(dict *d) { int minimal; //如果dict_can_resize被设置成0，表⽰不能进⾏rehash，或正在进⾏rehash，返回出错标志DICT_ERR if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR; minimal = d->ht[0].used; //获得已经有的节点数量作为最⼩限度minimal if (minimal < DICT_HT_INITIAL_SIZE)//但是minimal不能⼩于最低值DICT_HT_INITIAL_SIZE(4) minimal =
DICT_HT_INITIAL_SIZE; return dictExpand(d, minimal); //⽤minimal调整字典d的⼤⼩} int dictExpand(dict *d, unsigned long size) { dictht n; unsigned long realsize = _dictNextPower(size); //获得⼀个最接近2^n的realsize if (dictIsRehashing(d) || d-
>ht[0].used > size) //正在rehash或size不够⼤返回出错标志 return DICT_ERR; if (realsize == d->ht[0].size) return DICT_ERR; //如果新的realsize和原本的size⼀样则返回出错标志 /* Allocate the new hash table and initialize all pointers to NULL */ //初始化新的哈希表的成员 n.size = realsize; n.sizemask = realsize-1; n.table = zcalloc(realsize*sizeof(dictEntry*)); n.used = 0; /* Is this the first initialization? If so it's not really a rehashing * we just set the first hash table so that it can accept keys. */ if (d-
>ht[0].table == NULL) { //如果ht[0]哈希表为空，则将新的哈希表n设置为ht[0] d->ht[0] = n; return DICT_OK; } d->ht[1] = n; //如果ht[0]⾮空，则需要rehash d->rehashidx = 0; //设置rehash标志位为0，开始渐进式rehash(incremental rehashing) return
DICT_OK;} static unsigned long _dictNextPower(unsigned long size){ unsigned long i = DICT_HT_INITIAL_SIZE;
//DICT_HT_INITIAL_SIZE 为 4 if (size >= LONG_MAX) return LONG_MAX + 1LU; while(1) { if (i >= size) return i; i *= 2; }}由代码我们可以看到，假如收缩后长度为4，不仅不会收缩，甚⾄还会报错。()
我们回过头来再看看设定：题⽬可能成⽴吗？ 哈希表的扩容都是2倍增长的，最⼩是4， 4 ===》 8 ====》 16 =====》 32
======》 64 ====》 128
也就是说：不存在长度为 40多的情况，只能是64。但是如果是64的话，64 X 0.1(收缩界限)= 6.4 ，也就是说在减少到6的时候，哈希表就会收缩，会缩⼩到多少呢？是8。此时，再继续减少到4，也不会再收缩了。所以，根本不存在⼀个长度⼤于40，但是存在的元素为4的哈希表的。
扩容步骤
收缩步骤
redis支持的五种数据类型
渐进式refresh
在"扩容步骤"和"收缩步骤" 两幅动图中每幅图的第四步骤“将ht[0]中的数据利⽤哈希函数重新计算，rehash到ht[1]”，并不是⼀步完成的，⽽是分成N多步，循序渐进的完成的。 因为hash中有可能存放⼏千万甚⾄上亿个key，毕竟Redis中每个hash中可以存 2^32-1 键值对(40多亿)，假如⼀次性将这些键值rehash的话，可能会导致服务器在⼀段时间内停⽌服务，毕竟哈希函数就得计算⼀阵⼦呢((#^.^#))。
哈希表的refresh是分多次、渐进式进⾏的。
渐进式refresh和下图中左边橘黄⾊的“统筹”部分中的 rehashidx密切相关：
rehashidx 的数值就是现在rehash的元素位置rehashidx 等于 -1 的时候说明没有在进⾏refresh
甚⾄在进⾏期间，每次对哈希表的增删改查操作，除了正常执⾏之外，还会顺带将ht[0]哈希表相关键值对rehash到ht[1]。
以扩容步骤为例：
intset
整数集合是集合键的底层实现⽅式之⼀。
跳表
跳表这种数据结构长这样：
redis中把跳表抽象成如下所⽰：
看这个图，左边“统筹”，右边实现。 统筹部分有以下⼏点说明：
header: 跳表表头tail：跳表表尾level：层数最⼤的那个节点的层数length：跳表的长度实现部分有以下⼏点说明：
表头：是链表的哨兵节点，不记录主体数据。是个双向链表分值是有顺序的o1、o2、o3是节点所保存的成员，是⼀个指针，可以指向⼀个SDS值。层级⾼度最⾼是32。没每次创建⼀个新的节点的时候，程序都会随机⽣成⼀个介于1和32之间的值作为level数组的⼤⼩，这个⼤⼩就是“⾼度”redis五种数据结构的实现
redis对象
redis中并没有直接使⽤以上所说的各种数据结构来实现键值数据库，⽽是基于⼀种对象，对象底层再间接的引⽤上⽂所说的具体的数据结构。
结构如下图：
字符串
其中：embstr和raw都是由SDS动态字符串构成的。唯⼀区别是：raw是分配内存的时候，redisobject和 sds 各分配⼀块内存，⽽embstr是redisobject和raw在⼀块⼉内存中。
列表
hash
set
zset

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