本文主要用来学习下，redis当中使用的压缩表和跳跃表，为什么在诸多的数据结构中，redis要选择他们作为自己的数据存储结构。
什么是压缩表？
压缩表是Redis为了
节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型（sequential）数据结构。一个压缩列表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值。
压缩表的构成
压缩表的构成如下所示：
压缩表各构成部分的含义说明：
| 属性 | 用途 |
|---|---|
| zlbytes | 记录整个压缩表占用的字节数；在对压缩列表进行内存重分配或者计算zlend时使用 |
| zltail | 记录压缩表尾结点距离起始节点的字节距离 |
| zllen | 记录压缩表包含的节点数量 |
| entry | 压缩表的节点，长度由其内容决定 |
| zlend | 标记压缩表末端 |
压缩表节点(entry)的构成
每个节点由以下三个部分组成：
其中三个部分的含义分别是：
| 属性 | 用途 |
|---|---|
| previous_entry_length | 以字节为单位，记录前一个节点的长度。程序可以通过指针运算，根据当前节点的起始地址来计算出前一个节点的起始地址。从表尾向表头遍历操作就是通过这样原理实现的。 |
| encoding | 记录了节点的content属性所保存数据的类型以及长度 |
| content | 保存节点的值，节点值可以是一个字节数组或者整数，值的类型和长度由节点的encoding属性决定 |
连锁更新问题
在前面介绍previous_entry_length的时候，有一点没有详细说明：
如果前一节点的长度小于254字节，那么previous_entry_length属性需要用1字节长的空间来保存这个长度值。
如果前一节点的长度大于等于254字节，那么previous_entry_length属性需要用5字节长的空间来保存这个长度值。
正是由于这样的设计，从而会导致连锁更新问题。
假设有 entry1 到 entryN 个节点，每个节点的字节长度都在 250 到 253 之间，则每个节点的previous_entry_length存储的长度都是1。
如果此时 new 一个大于254的节点被压入压缩表的头部，那么这个 new 将成为 e1 前面的头结点。此时e1的previous_entry_length只有1字节，无法保存前一节点new的5字节长度，所以需要将e1的长度扩大为254 ~ 257。
同样的，对于e2来说，需要如e1一样增加容量才行。直到eN，都需要重新分配空间，这一种连续扩展空间的操作被称之为连锁更新。
其实连锁更新造成的性能损耗的几率是很低的，实际使用过程中几乎不会出现我们上面提到的极端环境，即使少量的连锁更新，也可以忽略不计
什么是跳跃表？
跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。
跳跃表的时间复杂度是平均O（logN）、最坏O（N）。
实现有序集合的方式有很多，为什么redis选择跳跃表？
- 数组：数组元素插入、删除不便
- 链表：查询元素效率低
- 平衡树：实现复杂
大多数情况下，跳跃表的效率可以和和平衡树媲美，而其实现相对平衡树要简单，所以很多情况下用跳跃表去替代平衡树。
跳跃表的构成
跳跃表在redis当中由两部分构成：
-
zskiplistNode：跳跃表节点 -
zskiplist：保存跳跃表节点信息
跳跃表的模型如下所示：
如上图所示：
- 蓝色的是
zskiplist结构 - 其他四个绿色的是
zskiplistNode结构
zskiplist结构介绍
在前面的图上我们看到zskiplist包含四个部分：
-
header：指向跳跃表头结点 -
tail：指向跳跃表的尾结点 -
level：记录跳跃表中层数最大的节点层数。（注意：头结点固定高度为32，初始全部指向NULL，且不被levle记录层高） -
length：记录跳跃表长度，即包含几个节点。（头结点除外）
使用多个节点就可以作为跳跃表，那么为什么还需要zskiplist？
实际通过zskiplist的结构就可以得出：
-
header和tail:快速访问跳跃表的头或尾节点，且时间复杂度是O(1)，否则可能需要遍历至少大于等于1次。 -
length：快速获取长度（即节点数量），时间复杂度都O(1)，否则需要遍历整个跳跃表。 -
level：用来快速获取最高节点层数，时间复杂度是O(1)。
可以帮助我们方便、快速的处理跳跃表。
zskiplistNode结构介绍
在前面的图我们看到zskiplistNode包含四种部分：
-
Level：层，即以L开头的部分。Level包含两个部分前进指针和跨度。表头向表位遍历时，会沿着前进指针前进。-
前进指针：指向表尾方向的其他节点 -
跨度：当前节点距离指向节点的距离，即上图箭头上的数字。
每当有一个新的节点加入跳跃表，程序根据幂次法则生成一个介于1和32之间的值作为level的大小，即层的高度。
-
backward：后退指针，即BW。指向当前节点的前一个节点，当从表尾向表头遍历时被使用。score：分值，即1.0、2.0、3.0。在跳跃表中会按照分值从小到大排列。object：成员对象，即o1、o2、o3。当分值相同时，按照成员对象进行排序
表头节点也有backward、score、object，但是不会使用。
