redis使用了跳跃表，但是我发现。。。。我竟然不知道跳跃表是什么东东。亏我还觉得数据结构基础还凑合呢= =。于是赶紧去看了《数据结构与算法分析》，算是知道是啥玩意的。说白了，就是链表+二分查找的结合体。这里主要是研究redis的，所以就不细谈这个数据结构了。
和双端链表、字典不同的是，跳跃表在reids中不是广泛使用的，它在redis中的唯��作用就是实现有序集数据类型。所以等到集合的时候再深入了解。
二上一章我们介绍了redis的内部结构：
但是，创建这些完整的数据结构是比较耗费内存的，如果对于一个特别简单的元素，使用这些数据结构无异于大材小用。为了解决这个问题，redis在条件允许的情况下，会使用内存映射数据结构来代替内部数据结构，主要有：
整数集合 intset
压缩列表 ziplist
当然了，因为这些结构是和内存直接打交道的，就有节省内存的优点，而又因为对内存的操作比较复杂，所以也有操作复杂，占用的CPU时间更多的缺点。
这个要掌握一个平衡，才能使redis的总体效率更好。目前，redis使用两种内存映射数据结构。
1. 整数集合
整数集合用于有序、无重复的保存多个整数值，它会根据元素的值，自动选择该用什么长度的整数类型来保存元素。比如，在一个int set中，最大的元素可以用int16_t保存，那么这个int set的所有元素都是int16_t，当插入一个元素是int32_t的时候，int set会先将所有元素升级为int32_t，再插入这个元素。总的来说，整数集合会自动升级。
看名字我们就知道它的用途：
只保存整数元素
元素的数量不多[因为它不费内存，费CPU。量多的话，肯定是CPU为第一考虑]
那么我们看一下 intset 的定义：
1 typedef struct intset { 2 3 // 保存元素所使用的类型的长度 4 uint32_t encoding; 5 6 // 元素个数 7 uint32_t length; 8 9 // 保存元素的数组 10 int8_t contents[]; 11 12 } intset;其中 encoding 保存的是 intset 中元素的编码类型，比如是 int16_t还是 int32_t等等。具体的定义在 intset.c 中：
1 #define INTSET_ENC_INT16 (sizeof(int16_t)) 2 #define INTSET_ENC_INT32 (sizeof(int32_t)) 3 #define INTSET_ENC_INT64 (sizeof(int64_t))length 肯定就是元素的个数喽，然后是具体的元素，我们发现是 int8_t 类型的，实现上它只是一个象征意义上的类型，到实际分配时候，会根据具体元素的类型选择合适的类型。而且 contents 有两个特点：
没有重复元素
元素在数组中从小到大排序
所以，添加元素到intset有下面几个步骤：
判断插入元素是否存在于集合，如果存在，没有任何操作(无重复元素)
看元素的长度是否需要把intset升级，如果需要，先升级
插入元素，而且要保证在contents数组中，从小到大排序
维护length
简单总结一下整数集合的特点：
保存有序、无重复的整数元素
根据元素的值自动选择对应的类型，但是int set只升级、不降级
升级会引起整个int set中的contents数组重新内存分配，并移动所有的元素（因为内存不一样了），所以复杂度为O(N)
因为int set是有序的，所以查找使用的是binary search
2. 压缩列表
本质来说，压缩列表就是由一系列特殊编码的内存块构成的列表，一个压缩列表可以包含多个节点，每个节点可以保存一个长度受限的字符数组（不以为\0结尾的char数组）或者整数。说白了，它是以内存为中心的数据结构，一般列表是以元素类型的字节总数为大小，而压缩列表是以它最小内存块进行扩展组成的列表。下面我来说一下。
压缩列表分为3个部分：
header：10字节，保存整个压缩列表的信息，有尾节点到head的偏移量、节点个数、整个压缩列表的内存（字节）
节点：一个结构体、由前一个节点的大小（用于向前遍历）、元素类型and长度、具体值组成
哨兵：就是一个1字节的全为1的内存，表示一个压缩列表的结束
其中压缩列表的节点值得说一下，它可以存储两类数据：