Redis的数据以K-V形式存储，K和V都是一个对象，每个对象都由结构体redisObject表示。
struct redisObject {
unsigned type:4; // 类型
unsigned encoding:4; // 编码
void * ptr; // 指向底层实现数据结构的指针
...
}
为了节约内存，结构体内使用了位字段。
对象的type有五种，可根据命令type key获得
- string
- list
- hash
- set
- zset
coding决定了对象的底层实现，可根据命令object encoding key获得
- int：long类型整数
- embstr：存储短字符串。
- raw：简单动态字符串（SDS），用来存储长字符串。
- linkedlist：双向链表
- hashtable：由链表数组实现
- ziplist：压缩列表
- intset：（小型）整数集合。由整型数组实现，数组中的元素有序排列，且不重复。
- skiplist：跳表
需要注意的是redis的数据结构是动态类型，其底层实现可能会发生变化。
- string（string是五种类型中唯一一种会被其他四种对象嵌套的类型）
int：存储long类型的整数
embstr：字符串长度小于等于39字节，或者double浮点数
raw： 字符串长度大于39字节，或者long和double无法存储的数字 - list
ziplist：元素数量小于512，且每个字符串长度小于64
linkedlist：不满足上述条件
在新版的redis中，实现方式是quicklist - hash
ziplist：K-V数量小于512，且K和V的字符串长度小于64
hashtable：不满足上述条件 - set
intset：集合中元素数量小于512，且所有元素都是整数
hashtable：不满足上述条件 - zset
ziplist：有序集合元素数量小于128，且所有元素的长度小于64
skiplist & hashtable：不满足上述条件
本地做一个简单的测试：
可以看到264-1和264的底层实现是不一样的，两者都不能进行incr操作，一个会溢出，一个不是不能进行整数操作。
记得在去年看过一篇讲redis 数据结构的文章，非常深刻，有些东西对我非常有益，不过没怎么吸收。
skiplist与平衡树、哈希表的比较
- skiplist和各种平衡树（如AVL、红黑树等）的元素是有序排列的，而哈希表不是有序的。因此，在哈希表上只能做单个key的查找，不适宜做范围查找。所谓范围查找，指的是查找那些大小在指定的两个值之间的所有节点。
- 在做范围查找的时候，平衡树比skiplist操作要复杂。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在skiplist上进行范围查找就非常简单，只需要在找到小值之后，对第1层链表进行若干步的遍历就可以实现。
- 平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速。
- 查找单个key，skiplist和平衡树的时间复杂度都为O(log n)，大体相当；而哈希表在保持较低的哈希值冲突概率的前提下，查找时间复杂度接近O(1)，性能更高一些。所以我们平常使用的各种Map或dictionary结构，大都是基于哈希表实现的。
- 从算法实现难度上来比较，skiplist比平衡树要简单得多。
2019-07-24
redis的数据结构是动态实现的，一个是轻量级的杀鸡刀，一个是重量级的杀牛刀。
