Redis内部数据详解

sorted set：当数据较少时，使用ziplist实现，数据较多时，使用zset(dict+skiplist)实现。

zset-max-ziplist-entries 128
zset-max-ziplist-value 64

这两个配置是当sorted set中元素数量超过128个，即ziplist数据项超过256个（数据，score）或任意一个数据值长度超过64时，ziplist会转化为zset(dict+skiplist)

skiplist

节点每增加一层的概率为P(0.25)，每个节点的最大成熟记为MaxLevel(32)

跳表节点的平均层数为：1/(1-P)

平均查找长度约为：C(log1/pn-1)=(log(1/p^(n-1))/p，平均时间复杂度为：O(log N)

ziplist

Ziplist 是为了尽可能地节约内存而设计的特殊编码双端链表。

ziplist结构中，每个entry储存了前一个entry的byte长度，用于反向定位上一个节点的位置。

这个节点长度所占用的字节数可能是1或5，导致增加和删除节点时，需要同步更新后续entry的值。

ziplist的修改操作效率很差，每次数据变动都会引发一次内存realloc，会导致大量的数据拷贝。

quicklist

内部节点采用LZF无损压缩算法。

sds

sds正是在Redis中被广泛使用的字符串结构，它的全称是Simple Dynamic String。

sds是一个二进制安全的字符指针(char *)的形式, 但不完全等同于char *。它由一个header结构构成，可以储存 \0。

dict

字典(dict)是由键值对组成的结构，Redis中的db和hash key都基于dict实现，dict的底层实现为hash表。hash算法有两种，广泛应用的为MurmurHash算法（算法的分布率和速度都非常好），另一种 djb 算法用于命令表和lua脚本缓存。

每个字典有两个哈希表，用于进行 渐进式rehash 过程。rehash过程开启后，每次对hash表进行 增/删/改/查 操作都会让rehash过程执行一帧，每帧将第一个hash表ht[0]上第一个不为空的索引上的所有节点迁往第二个hash表ht[1]。rehash过程中，所有的 删/改/查 操作，都要在两个hash表上进行，增 操作只会添加到新hash表上，保证旧的hash表节点数量只减不增。

参考：

压缩列表——Redis设计与实现

Redis 为什么用跳表而不用平衡树？

跳表──没听过但很犀利的数据结构

Redis内部数据结构详解(4)——sds

Redis内部数据结构详解(4)——ziplist

Redis内部数据结构详解(5)——quicklist