redis使用链地址法(separate chaining)来解决键冲突,当两个键的index值相同时,会把第二个键放到第一个键的前面,查询时对这个index的哈希节点链表进行遍历
rehash:当哈希表的负载因子(load factor)大于设定值时(平时为1,在BGREWRITEAOF时为5),哈希表会进行rehash操作
rehash采用渐进式的方式进行执行,具体流程就是把ht[0]里面的数据重新进行哈希计算放到ht[1],此时的哈希查询操作两个表同时提供服务,写入操作则只有ht[1]提供,这样ht[0]处于只减不增的状态,最终当ht[0]里面的所有数据都被转移到ht[1]时,rehashidx被设为-1,表明rehash结束,删除ht[0],并将ht[1]设为ht[0],同时重新分配新的ht[1]
ps:负载因子 = used /size;
跳跃表 数据结构//跳跃表节点 typedef struct zskiplistNode { sds ele; double score; struct zskiplistNode *backward; struct zskiplistLevel { struct zskiplistNode *forward; unsigned int span; } level[]; } zskiplistNode; //跳跃表 typedef struct zskiplist { struct zskiplistNode *header, *tail; unsigned long length; int level; } zskiplist;
跳跃表是有序集合的底层实现之一
跳跃表中的头结点不计算在length长度之内,跳跃表的节点排序按照分值从小到大排序
每次创建新节点的时候,redis会根据幂次定律随机生成一个1-32的层数作为level数组的大小,每个节点都有指向表尾方向的前进指针和之前表头方向的后退指针,这两个指针可以让程序方便的遍历所有节点,层的跨度用于记录两点之间的距离,跨度可以用来计算rank值.节点的分值是一个double值,节点的对象是一个指针,指向一个保存着sds字符串的字符串对象(下一节讲redis对象)
整数集合 数据结构typedef struct intset{ uint32_t encoding;//编码方式 uint32_t length;//集合包含的元素数量 int8_t contents[];//保存元素的数组 } intset;
顾名思义整数集合是用来保存整数值的抽象数据结构
集合中不会出现重复元素
contents数组中保存的整数值有小到大排列
length等于contents的长度
虽然contents的定义是int8_t 但实际上contents的值类型由encoding决定
当一个新元素超过原来整数集合encoding定义的值的类型时,会进行升级,升级结果会使集合的encoding变成所有数组中元素的值最大的数据类型,并且不支持降级
例如:有一个整数集合[1,2,3],本身的编码为int8,现在增加一个300的数字进该集合,会导致集合的编码升级为int16,这个时候列表的大小由8x3=24 变为 16x4=64,即便int8可以存储前三个值,但是为了简单起见,仍然会为集合中每一个元素分配同样的空间
压缩列表压缩列表被用作列表键和哈希键的底层实现
压缩列表属于特殊的结构,是一种数据存储的方式,目的是为了节约内存,是一种采用特殊编码的连续内存块组成的顺序型(sequential)数据结构.
大致结构如下:
zlbyteszltailzllenentry1entry2...zlend每个压缩列表由如下三部分组成
previous_entry_lengthencodingcontent前一节点的长度 记录content的类型和长度 节点的值
如果前一个节点长度小于254字节,previous_entry_length会使用1字节空间保存这个长度,如果大于254字节,将使用5字节长度保存这个值,这个机制会引起"连锁更新"
连锁更新: 假设现有连续的三个压缩列表节点l1,l2,l3,长度分别为 253,253,253,现在往第一个节点前添加一个长度超过254的节点,这个时候l1要给previous_entry_length分配5个字节来存储长度,所以列表本身长度会变为257,这将导致l2也需要5字节存储l1的长度,l3也会产生同样的变化,这样由一个列表操作引起的一系列更新操作成为连锁更新。
下面关于Redis的文章您也可能喜欢，不妨参考下：