数据结构

简单动态字符串SDS

①字符串长度②申请的总的内存大小

内存预分配扩容机制：追加新的字符串时，如果新字符串小于1M，则新的空间扩展为字符串长度2倍+1

IntSet

①编码方式②数组长度

编码方式动态升级：当添加的数字超过出int16的范围，那么IntSet会自动升级编码方式存储数组，然后倒序依次将数组元素拷贝到扩容后的位置，如果插入的数小于0，则他比所有元素都小，插入数组头部；如果他大于0则添加的元素添加到数组的尾部。整个数组保证有序，底层是二分查找。

Dict

添加键值对时，首先根据key计算出hash值，然后通过hash&(size-1)计算元素存储到的索引位置。

有两个哈希表ht[2]，一个平常用，另一个rehash用

添加元素时，根据负载因子(used/size)触发哈希扩容(扩容大小比当前size大1的最近的2的倍数)；删除元素时会检查是否收缩。无论是扩容还是收缩，当哈希表的大小变化时，需要计算所有key的索引，并插入到新的哈希表中。数据迁移时采用渐进式rehash，仅在每次增删改查时迁移一个角标的元素到ht[1]上。

ZipList-quicklist-listpack

• ZipList

双端链表每个节点结构：①前一个节点长度prevlen②编码方式③节点数据

问题：新增或者修改某个元素时，会导致内存占用空间重新分配，并且后续元素的prevlen占用空间发生变化，引起连锁更新问题。

• QuickList

解决ZipList存储大量数据，同时内存申请效率比较低。

使用QuickList双端链表来将所有ZipList串起来，每个节点包含一个前向指针，后向指针，ZipList指针。每个节点还可以设置是否对ZipList压缩。

SkipList跳表

• 元素按照得分score升序排列存储
• 每个节点包含多个指针，指针跨度不同。查找时根据不同指针跨度的score和要查询的score进行比较，如果比所要查询的score小，那就找跨度更大的指针。

• 跳表中，每个节点出了包含下个节点的指针外，还可能包含多个后面节点的指针，越高层的指针跨越的节点数越多。跳表一个重要性质是一个节点如果在第i层链表出现，那么在第1到i-1层链表中也会出现。比如要在一个有序链表中查找元素，可以通过跳表跳过查找一些中间元素，从而减少查找时间。其实是一种空间换时间的做法。

  

RedisObject

• set：HT，Intset(如果是数值类型)

使用HT的key存储元素，value统一设置为null，底层跟java的hashmap和hashset一致。

• Zset：HT+SkipList,ZipList(数据量少时节省内存使用ziplist，让element和score紧挨保存在相邻的entry中)。通过一个哈希表(维护姓名->分数的一个映射关系)和一个跳表(存储分数)来实现，查找某个节点排名时，只需从高层到底层把跨度相加起来，得到排名结果。它的查询次数是远比普通链表要小的。

• Hash：HT，ZipList