redis是一个key-value存储系统。和memcached类似，它支持存储的value类型相对更多，包括string(字符串)、list(链表)、set(集合)、zset(sorted set有序集合)和hash(哈希类型)。这些数据类型都支持push/pop、add/remove以及取交集并集和差集及更丰富的操作，而且这些操作都是原子性的。
本文将对redis数据的编码方式和底层数据结构进行分析和介绍，帮助读者更好的了解和使用它们。
redis中数据对象的定义如下：
其中type对应了redis中的五种基本数据类型：
encoding则对应了 redis 中的十种编码方式:
type和encoding的对应关系如下图：
raw编码方式使用简单动态字符串来保存字符串对象，其具体定义为：
从len字段可以判断并不不依赖于'0'，故可以用与保存二进制对象。
从free字段可以判断其空间分配是采用预分配的方式，避免字符串修改时频繁分配释放内存。具体分配算法为:
int编码方式以整数保存字符串数据，仅限能用long类型值表达的字符串。
当robj中的lru值没有意义的时候(实例没有设置maxmemory限制或者maxmemory-policy设置的淘汰算法中不计算lru值时)， 0-10000之间的obj_encoding_int编码的字符串对象将进行共享。
具体算法如下：
从redis 3.0版本开始字符串引入了embstr编码方式，长度小于obj_encoding_embstr_size_limit的字符串将以embstr方式存储。
embstr方式的意思是 embedded string ，字符串的空间将会和redisobject对象的空间一起分配，两者在同一个内存块中。
redis中内存分配使用的是jemalloc，jemalloc分配内存的时候是按照8,16,32,64作为chunk的单位进行分配的。为了保证采用这种编码方式的字符串能被jemalloc分配在同一个chunk中，该字符串长度不能超过64，故字符串长度限制obj_encoding_embstr_size_limit = 64 - sizeof('0') - sizeof(robj)为16 - sizeof(struct sdshdr)为8 = 39。
采用这个方式可以减少内存分配的次数，提高内存分配的效率，降低内存碎片率。
链表(list),哈希(hash),有序集合(sorted set)在成员较少，成员值较小的时候都会采用压缩列表(ziplist)编码方式进行存储。
这里成员"较少"，成员值"较小"的标准可以通过配置项进行配置:
压缩列表简单来说就是一系列连续的内存数据块，其内存利用率很高，但增删改查效率较低，所以只会在成员较少，值较小的情况下使用。
其典型结构如下：
在redis 3.2版本之前，一般的链表使用linkdedlist编码。
在redis 3.2版本开始，所有的链表都是用quicklist编码。
两者都是使用基本的双端链表数据结构，区别是quicklist每个节点的值都是使用ziplist进行存储的。
整数集合(intset)是集合键的底层实现之一：
当一个集合只包含整数值元素， 并且这个集合的元素数量不多时， redis 就会使用整数集合作为集合键的底层实现。
字典是redis中存在最广泛的一种数据结构不仅在哈希对象，集合对象和有序结合对象中都有使用，而且redis所有的key,value都是存在db->dict这张字典中的。
redis 的字典使用哈希表作为底层实现。
一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。
哈希表的定义如下：
redis计算hash值和索引的方式为:
一个字典里面保存了两个hash表结构，用于哈希表的扩展收缩操作(rehash)。
随着操作的不断执行，哈希表保存的键值对会逐渐地增多或者减少，为了让哈希表的负载(used/size)维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。
具体算法为:
为字典的 ht[1] 哈希表分配空间,这个哈希表的空间大小为:
第一个大于等于(扩展时)或者小于等于(收缩时) ht[0].used * 2 的 2^n(2 的 n 次方幂);
将保存在 ht[0] 中的所有键值对 rehash 到 ht[1] 上面:rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到 ht[1]哈希表的指定位置上;
当 ht[0] 包含的所有键值对都迁移到了 ht[1] 之后(ht[0] 变为空表)，释放 ht[0] ，将 ht[1] 设置为 ht[0]，并在 ht[1] 新创建一个空白哈希表，为下一次 rehash 做准备。
一次性完成 rehash 过程时间可能很长，redis采用渐进式 rehash 的方式完成整个过程。
每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] ， 并将 rehashidx 的值增一;
直到整个 ht[0] 全部完成 rehash 后，rehashindex设为-1，释放 ht[0] , ht[1]置为 ht[0], 在 ht[1] 创建一个新的空白表。
跳跃表(skiplist)编码方式为有序集合对象专用，有序集合对象采用了字典+跳跃表的方式实现。其定义如下：
其中字典里面保存了有序集合中member与score的键值对，跳跃表则用于实现按score排序的功能。
跳跃表以有序的方式在层次化的链表中保存元素，在一般情况下情况下效率和平衡树媲美， 比起平衡树来说，跳跃表的实现要简单直观得多。
一般的跳跃表结构如下图所示：
跳跃表的基本原理是每一个节点创建的时候层数为随机值，层数越高的几率越小，redis中每升高一层的概率为1/4。也就是说，一个跳跃表里，一般情况下，每一层的节点数为下一次的 1/4，相当于是一个“随机化”的平衡树。
具体的算法在此就不详细赘述了，与一般的跳跃表实现相比，有序集合中的跳跃表有以下特点：
允许重复的 score 值：多个不同的 member 的 score 值可以相同。
进行对比操作时，不仅要检查 score 值，还要检查 member：当 score 值可以重复时，单靠 score 值无法判断一个元素的身份，所以需要连 member 域都一并检查才行。
每个节点都带有一个高度为1层的后退指针，用于从表尾方向向表头方向迭代：当执行 zrevrange 或zrevrangebyscore这类以逆序处理有序集的命令时，就会用到这个属性。
知其然，更要知其所以然。
只有深入了解了redis数据的编码方式和底层数据结构，我们才能更好的了解使用它。在做疑难问题分析和业务优化时，才能更加有的放矢。