- 简单动态字符串
- Redis 只会使用 C 字符串作为字面量， 在大多数情况下， Redis 使用 SDS （Simple Dynamic String，简单动态字符串）作为字符串表示。
- 比起 C 字符串， SDS 具有以下优点：
- 常数复杂度获取字符串长度。
- 杜绝缓冲区溢出。
- 减少修改字符串长度时所需的内存重分配次数。
- 二进制安全。
- 兼容部分 C 字符串函数。
2链表
- 链表被广泛用于实现 Redis 的各种功能， 比如列表键， 发布与订阅， 慢查询， 监视器， 等等。
- 每个链表节点由一个 listNode 结构来表示， 每个节点都有一个指向前置节点和后置节点的指针， 所以 Redis 的链表实现是双端链表。
- 每个链表使用一个 list 结构来表示， 这个结构带有表头节点指针、表尾节点指针、以及链表长度等信息。
- 因为链表表头节点的前置节点和表尾节点的后置节点都指向 NULL ， 所以 Redis 的链表实现是无环链表。
- 通过为链表设置不同的类型特定函数， Redis 的链表可以用于保存各种不同类型的值。
3.字典
- 字典被广泛用于实现 Redis 的各种功能， 其中包括数据库和哈希键。
- Redis 中的字典使用哈希表作为底层实现， 每个字典带有两个哈希表， 一个用于平时使用， 另一个仅在进行 rehash 时使用。
- 当字典被用作数据库的底层实现， 或者哈希键的底层实现时， Redis 使用 MurmurHash2 算法来计算键的哈希值。
- 哈希表使用链地址法来解决键冲突， 被分配到同一个索引上的多个键值对会连接成一个单向链表。
- 在对哈希表进行扩展或者收缩操作时， 程序需要将现有哈希表包含的所有键值对 rehash 到新哈希表里面， 并且这个 rehash 过程并不是一次性地完成的， 而是渐进式地完成的。
为什么有序集合需要同时使用跳跃表和字典来实现？
在理论上来说， 有序集合可以单独使用字典或者跳跃表的其中一种数据结构来实现， 但无论单独使用字典还是跳跃表， 在性能上对比起同时使用字典和跳跃表都会有所降低。
举个例子， 如果我们只使用字典来实现有序集合， 那么虽然以 O(1) 复杂度查找成员的分值这一特性会被保留， 但是， 因为字典以无序的方式来保存集合元素， 所以每次在执行范围型操作 —— 比如 ZRANK 、 ZRANGE 等命令时， 程序都需要对字典保存的所有元素进行排序， 完成这种排序需要至少 O(N log N) 时间复杂度， 以及额外的 O(N) 内存空间 （因为要创建一个数组来保存排序后的元素）。
另一方面， 如果我们只使用跳跃表来实现有序集合， 那么跳跃表执行范围型操作的所有优点都会被保留， 但因为没有了字典， 所以根据成员查找分值这一操作的复杂度将从 O(1) 上升为 O(log N) 。
因为以上原因， 为了让有序集合的查找和范围型操作都尽可能快地执行， Redis 选择了同时使用字典和跳跃表两种数据结构来实现有序集合。
举个例子， 如果前面 price 键创建的不是 ziplist 编码的有序集合对象， 而是 skiplist 编码的有序集合对象， 那么这个有序集合对象将会是图 8-16 所示的样子， 而对象所使用的 zset 结构将会是图 8-17 所示的样子。
ptr | ... "]; zset [label = "
zset |
dict | zsl "]; node [shape = plaintext]; dict [label = "..."]; zsl [label = "..."]; redisObject:ptr -> zset:head; zset:dict -> dict; zset:zsl -> zsl; }" src="https://img-blog.csdnimg.cn/img_convert/5a8788bb7330b9423fe1889e654faffd.png" />
zset | dict | zsl "]; dict [label = " dict | ... | ht[0] | ... "]; ht0 [label = " dictht | ... | table | ... "]; table [label = " StringObject n "banana" | StringObject n "apple" | StringObject n "cherry" "]; node [shape = plaintext]; apple_price [label = "8.5"]; banana_price [label = "5.0"]; cherry_price [label = "6.0"]; // zset:dict -> dict:head; dict:ht0 -> ht0:head; ht0:table -> table:head; table:apple -> apple_price; table:banana -> banana_price; table:cherry -> cherry_price; // node [shape = record, width = "0.5"]; // l [label = " header | tail | level n 5 | length n 3 "]; subgraph cluster_nodes { style = invisible; header [label = " L32 | ... | L5 | L4 | L3 | L2 | L1 "]; bw_null [label = "NULL", shape = plaintext]; level_null [label = "NULL", shape = plaintext]; A [label = " L4 | L3 | L2 | L1 | BW | 5.0 | StringObject n "banana" "]; B [label = " L2 | L1 | BW | 6.0 | StringObject n "cherry" "]; C [label = " L5 | L4 | L3 | L2 | L1 | BW | 8.5 | StringObject n "apple" "]; } subgraph cluster_nulls { style = invisible; n1 [label = "NULL", shape = plaintext]; n2 [label = "NULL", shape = plaintext]; n3 [label = "NULL", shape = plaintext]; n4 [label = "NULL", shape = plaintext]; n5 [label = "NULL", shape = plaintext]; } // l:header -> header; l:tail -> C; header:l32 -> level_null; header:l5 -> C:l5; header:l4 -> A:l4; header:l3 -> A:l3; header:l2 -> A:l2; header:l1 -> A:l1; A:l4 -> C:l4; A:l3 -> C:l3; A:l2 -> B:l2; A:l1 -> B:l1; B:l2 -> C:l2; B:l1 -> C:l1; C:l5 -> n5; C:l4 -> n4; C:l3 -> n3; C:l2 -> n2; C:l1 -> n1; bw_null -> A:backward -> B:backward -> C:backward [dir = back]; zset:zsl -> l:header; // HACK: 放在开头的话 NULL 指针的长度会有异样 label = "n 图 8-17 有序集合元素同时被保存在字典和跳跃表中"; }" src="https://img-blog.csdnimg.cn/img_convert/6633eeb7d1600ff3b904d3d1fc4075ea.png" />
