Redis中的类型和数据结构

redis对外有5中基本类型，分别是string t_string.c, list t_list.c, hash t_hash.c, set t_set.c 和 zset (ordered set) t_zset.c.这5种类型是“接口”而不是“实现”，因此redis得以根据不同的情形自由选择不同数据结构的实现，这也是redis在设计上的高明之处。

5种基本类型对应了int object.c, embstr object.c, raw sds.c, linkedlist adlist.c, ziplist ziplist.c, skiplist t_zset.c, ht dict.c, intset intset.c 这8种数据结构的实现。

类型与数据结构实现的对应关系如图。

实用type KEYNAME可以查看某个key对应的类型，而object encoding KEYNAME可以查看该key内部的实现。

string

string 有三种实现方式，分别是int, embstr和raw.长度比较短的整数会使用int实现。长度比较短的字符串会使用embstr, 更长的会使用raw。embstr和raw的区别在于，embstr吧redisObject和sds放在一块连续空间里面，这样申请内存和释放内存都只需要一次调用。带来的坏处是，embstr是只读的，如果调用append等操作则自动升级为raw。

对于int实现的string，如果调用strlen和gettrange等会产生额外开销。如果需要强制使用raw来实现, 可以用setrange。

zset

zset在元素较少时，使用intset实现。在元素较多时，使用skiplist和dict一起实现。其中skiplist用于提供顺序相关的操作，而dict用于快速查询score.

关于skiplist: 这是一种用多级链表加快查询速度的数据结构。Insert, delete, search的复杂度均为o(logn), 还可以进行高效的range query, 功能与性能与红黑树，B树相当，但实现更简单。CLRS里有详细的解释。