Redis 常见对象类型的底层数据结构

1、Redis 介绍

1.1 NoSQL 基本概念

为了解决高并发、高可用、高可扩展，大数据存储等一系列问题而产生的数据库解决方案，就是NoSQL。
NoSQL叫非关系型数据库，它的全名Not only sql。它不能替代关系型数据库，只能作为关系型数据库的一个良好补充。

1.2 NoSQL 分类

  • 键值(Key-Value)存储数据库 相关产品：Tokyo Cabinet/Tyrant、Redis、Voldemort、Berkeley DB 典型应用：内容缓存，主要用于处理大量数据的高访问负载。数据模型：一系列键值对 优势：快速查询 劣势：存储的数据缺少结构化
  • 列存储数据库 相关产品：Cassandra, HBase, Riak 典型应用：分布式的文件系统 数据模型：以列簇式存储，将同一列数据存在一起 优势：查找速度快，可扩展性强，更容易进行分布式扩展 劣势：功能相对局限
  • 文档型数据库 相关产品：CouchDB、MongoDB 典型应用：Web应用（与Key-Value类似，Value是结构化的） 数据模型：一系列键值对 优势：数据结构要求不严格 劣势：查询性能不高，而且缺乏统一的查询语法
  • 图形(Graph)数据库 相关数据库：Neo4J、InfoGrid、Infinite Graph 典型应用：社交网络 数据模型：图结构 优势：利用图结构相关算法。劣势：需要对整个图做计算才能得出结果，不容易做分布式的集群方案。

    1.3 Redis 基本概念

    Redis是使用c语言开发的一个高性能键值数据库。Redis可以通过一些键值类型来存储数据。键值类型：String字符类型、 Map散列类型、 list列表类型、 set集合类型、 sortedset有序集合类型。

    1.4 发展历史

    2008年，意大利的一家创业公司Merzia推出了一款基于MySQL的网站实时统计系统LLOOGG，然而没过多久该公司的创始人 Salvatore Sanfilippo便 对MySQL的性能感到失望，于是他决定亲自为LLOOGG量身定做一个数据库，并于2009年开发完成，这个数据库就是Redis。不过Salvatore Sanfilippo并不满足只将Redis用于LLOOGG这一款产品，而是希望更多的人使用它，于是在同一年Salvatore Sanfilippo将Redis开源发布，并开始和Redis的另一名主要的代码贡献者Pieter Noordhuis一起继续着Redis的开发，直到今天。
    Salvatore Sanfilippo自己也没有想到，短短的几年时间，Redis就拥有了庞大的用户群体。Hacker News在2012年发布了一份数据库的使用情况调查，结果显示有近12%的公司在使用Redis。国内如新浪微博、街旁网、知乎网，国外如GitHub、Stack Overflow、Flickr等都是Redis的用户。
    VMware公司从2010年开始赞助Redis的开发， Salvatore Sanfilippo和Pieter Noordhuis也分别在3月和5月加入VMware，全职开发Redis。

    1.5 应用场景

    缓存（数据查询、短连接、新闻内容、商品内容等等）。（最多使用） 分布式集群架构中的session分离。聊天室的在线好友列表。任务队列。（秒杀、抢购、12306等等） 应用排行榜。网站访问统计。数据过期处理（可以精确到毫秒）
    Redis是一个基于内存中的数据结构存储系统，可以用作数据库、缓存和消息中间件。Redis支持五种常见对象类型：字符串(String)、哈希(Hash）、列表(List)、集合(Set)以及有序集合(Zset)，在日常工作中也会经常使用它们。读懂这五种常见对象类型的底层数据结构也很重要。

    2、对象类型和编码

    Redis使用对象来存储键和值的，在Redis中，每个对象都由redisObject结构表示。redisObject结构主要包含三个属性：type、encoding和ptr。
    1. typedef struct redisObject {
    2.   // 类型
    3.   unsigned type:4;
    4.   // 编码
    5.   unsigned encoding:4;
    6.   // 底层数据结构的指针
    7.   void *ptr;
    8. } robj;
    其中type属性记录了对象的类型，对于Redis来说，键对象总是字符串类型，值对象可以是任意支持的类型。因此，Redis键采用哪种对象类型的时候，指的是对应的值采用哪种对象类型。
类型常量 对象类型名称
REDIS_STRING 字符串对象
REDIS_LIST 列表对象
REDIS_HASH 哈希对象
REDIS_SET 集合对象
REDIS_ZSET 有序集合对象

*ptr属性指向了对象的底层数据结构，而这些数据结构由encoding属性决定。

编码常量 编码对应的底层数据结构
REDIS_ENCODING_INT long类型的整数
REDIS_ENCODING_EMBSTR emstr编码的简单动态字符串
REDIS_ENCODING_RAW 简单动态字符串
REDIS_ENCODING_HT 字典
REDIS_ENCODING_LINKEDLIST 双端链表
REDIS_ENCODING_ZIPLIST 压缩列表
REDIS_ENCODING_INTSET 整数集合
REDIS_ENCODING_SKIPLIST 跳跃表和字典

之所以由encoding属性来决定对象的底层数据结构，是为了实现同一对象类型，支持不同的底层实现。这样就能在不同场景下，使用不同的底层数据结构，进而极大提升Redis的灵活性和效率。

底层数据结构后面会详细讲解，这里简单看一下即可。

3、字符串对象

字符串是日常工作中用得最多的对象类型，它对应的编码可以是int、raw和embstr。
如果一个字符串对象保存的是不超过long类型的整数值，此时编码类型即为int，其底层数据结构直接就是long类型。例如执行set number 10086，就会创建int编码的字符串对象作为number键的值。
Redis常见对象类型的底层数据结构 - 图1
如果字符串对象保存的是一个长度大于39字节的字符串，此时编码类型即为raw，其底层数据结构是简单动态字符串(SDS)；如果长度小于等于39个字节，编码类型则为embstr，底层数据结构就是embstr编码SDS。

3.1 简单动态字符串

SDS定义

在Redis中，使用sdshdr数据结构表示SDS：

  1. struct sdshdr {
  2.     // 字符串长度
  3.     int len;
  4.     // buf数组中未使用的字节数
  5.     int free;
  6.     // 字节数组，用于保存字符串
  7.     char buf[];
  8. };

SDS遵循了C字符串以空字符结尾的惯例，保存空字符的1字节不会计算在len属性里面。例如，Redis这个字符串在SDS里面的数据可能是如下形式：Redis常见对象类型的底层数据结构 - 图2

SDS与C字符串的区别

C语言使用长度为N+1的字符数组来表示长度为N的字符串，并且字符串的最后一个元素是空字符\0。Redis采用SDS相对于C字符串有如下几个优势：

  1. 常数复杂度获取字符串长度
  2. 杜绝缓冲区溢出
  3. 减少修改字符串时带来的内存重分配次数
  4. 二进制安全
    常数复杂度获取字符串长度
    因为C字符串并不记录自身的长度信息，所以为了获取字符串的长度，必须遍历整个字符串，时间复杂度是O(N)；而SDS使用len属性记录了字符串的长度，因此获取SDS字符串长度的时间复杂度是O(1)。
    杜绝缓冲区溢出
    C字符串不记录自身长度带来的另一个问题是很容易造成缓存区溢出。比如使用字符串拼接函数(stract)的时候，很容易覆盖掉字符数组原有的数据。与C字符串不同，SDS的空间分配策略完全杜绝了发生缓存区溢出的可能性。当SDS进行字符串扩充时，首先会检查当前的字节数组的长度是否足够，如果不够的话，会先进行自动扩容，然后再进行字符串操作。
    减少修改字符串时带来的内存重分配次数
    因为C字符串的长度和底层数据是紧密关联的，所以每次增长或者缩短一个字符串，程序都要对这个数组进行一次内存重分配：
  • 如果是增长字符串操作，需要先通过内存重分配来扩展底层数组空间大小，不这么做就导致缓存区溢出。
  • 如果是缩短字符串操作，需要先通过内存重分配来来回收不再使用的空间，不这么做就导致内存泄漏。

因为内存重分配涉及复杂的算法，并且可能需要执行系统调用，所以通常是个比较耗时的操作。对于Redis来说，字符串修改是一个十分频繁的操作，如果每次都像C字符串那样进行内存重分配，对性能影响太大了，显然是无法接受的。
SDS通过空闲空间解除了字符串长度和底层数据之间的关联。在SDS中，数组中可以包含未使用的字节，这些字节数量由free属性记录。通过空闲空间，SDS实现了空间预分配和惰性空间释放两种优化策略。

  1. 空间预分配
    空间预分配是用于优化SDS字符串增长操作的，简单来说就是当字节数组空间不足触发重分配的时候，总是会预留一部分空闲空间
    。这样的话，就能减少连续执行字符串增长操作时的内存重分配次数。有两种预分配的策略：
    1. len小于1MB时：每次重分配时会多分配同样大小的空闲空间；
    2. len大于等于1MB时：每次重分配时会多分配1MB大小的空闲空间。
  2. 惰性空间释放 惰性空间释放是用于优化SDS字符串缩短操作的，简单来说就是当字符串缩短时，并不立即使用内存重分配来回收多出来的字节，而是用free属性记录，等待将来使用。SDS也提供直接释放未使用空间的API，在需要的时候，也能真正的释放掉多余的空间。
    二进制安全
    C字符串中的字符必须符合某种编码，并且除了字符串末尾之外，其它位置不允许出现空字符，这些限制使得C字符串只能保存文本数据。但是对于Redis来说，不仅仅需要保存文本，还要支持保存二进制数据。为了实现这一目标，SDS的API全部做到了二进制安全(binary-safe)。

    3.2 raw和embstr编码的SDS区别

    在前面讲过，长度大于39字节的字符串，编码类型为raw，底层数据结构是简单动态字符串(SDS)。这个很好理解，比如当执行set story "Long, long, long ago there lived a king ..."(长度大于39)之后，Redis就会创建一个raw编码的String对象。
    长度小于等于39个字节的字符串，编码类型为embstr，底层数据结构则是embstr编码SDS。embstr编码是专门用来保存短字符串的，它和raw编码最大的不同在于：raw编码会调用两次内存分配分别创建redisObject结构和sdshdr结构，而embstr编码则是只调用一次内存分配，在一块连续的空间上同时包含redisObject结构和sdshdr结构。
    Redis常见对象类型的底层数据结构 - 图3

    3.3 编码转换

    int编码和embstr编码的字符串对象在条件满足的情况下会自动转换为raw编码的字符串对象。对于int编码来说，当修改这个字符串为不再是整数值的时候，此时字符串对象的编码就会从int变为raw；对于embstr编码来说，只要修改了字符串的值，此时字符串对象的编码就会从embstr变为raw。

    embstr编码的字符串对象可以认为是只读的，因为Redis为其编写任何修改程序。当要修改embstr编码字符串时，都是先将转换为raw编码，然后再进行修改。

4、列表对象

列表对象的编码可以是linkedlist或者ziplist，对应的底层数据结构是链表和压缩列表。列表对象相关命令可参考：Redis命令-List。默认情况下，当列表对象保存的所有字符串元素的长度都小于64字节，且元素个数小于512个时，列表对象采用的是ziplist编码，否则使用linkedlist编码。

可以通过配置文件修改该上限值。

4.1 链表

链表是一种非常常见的数据结构，提供了高效的节点重排能力以及顺序性的节点访问方式。在Redis中，每个链表节点使用listNode结构表示：

  1. typedef struct listNode {
  2.     // 前置节点
  3.     struct listNode *prev;
  4.     // 后置节点
  5.     struct listNode *next;
  6.     // 节点值
  7.     void *value;
  8. } listNode

多个listNode通过prev和next指针组成双端链表，如下图所示：
Redis常见对象类型的底层数据结构 - 图4
为了操作起来比较方便，Redis使用了list结构持有链表。

  1. typedef struct list {
  2.     // 表头节点
  3.     listNode *head;
  4.     // 表尾节点
  5.     listNode *tail;
  6.     // 链表包含的节点数量
  7.     unsigned long len;
  8.     // 节点复制函数
  9.     void *(*dup)(void *ptr);
  10.     // 节点释放函数
  11.     void (*free)(void *ptr);
  12.     // 节点对比函数
  13.     int (*match)(void *ptr, void *key);
  14. } list;

list结构为链表提供了表头指针head、表尾指针tail，以及链表长度计数器len，而dup、free和match成员则是实现多态链表所需类型的特定函数。
Redis常见对象类型的底层数据结构 - 图5
Redis链表实现的特征总结如下：

  1. 双端：链表节点带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度都是O(n)。
  2. 无环：表头节点的prev指针和表尾节点的next指针都指向NULL，对链表的访问以NULL为终点。
  3. 带表头指针和表尾指针：通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点的复杂度为O(1)。
  4. 带链表长度计数器：程序使用list结构的len属性来对list持有的节点进行计数，程序获取链表中节点数量的复杂度为O(1)。
  5. 多态：链表节点使用void*指针来保存节点值，可以保存各种不同类型的值。

    4.2 压缩列表

    压缩列表(ziplist)是列表键和哈希键的底层实现之一。压缩列表主要目的是为了节约内存，是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点，每个节点可以保存一个字节数组或者一个整数值。
    Redis常见对象类型的底层数据结构 - 图6
    如上图所示，压缩列表记录了各组成部分的类型、长度以及用途。
属性 类型 长度 用途
zlbytes uint_32_t 4字节 记录整个压缩列表占用的内存字节数
zltail uint_32_t 4字节 记录压缩列表表尾节点距离起始地址有多少字节，通过这个偏移量，程序无需遍历整个压缩列表就能确定表尾节点地址
zlen uint_16_t 2字节 记录压缩列表包含的节点数量
entryX 列表节点 不定 压缩列表的各个节点，节点长度由保存的内容决定
zlend uint_8_t 1字节 特殊值(0xFFF)，用于标记压缩列表末端

5、哈希对象

哈希对象的编码可以是ziplist或者hashtable。

5.1 hash-ziplist

ziplist底层使用的是压缩列表实现，上文已经详细介绍了压缩列表的实现原理。每当有新的键值对要加入哈希对象时，先把保存了键的节点推入压缩列表表尾，然后再将保存了值的节点推入压缩列表表尾。比如，执行如下三条HSET命令：

  1. HSET profile name "tom"
  2. HSET profile age 25
  3. HSET profile career "Programmer"

如果此时使用ziplist编码，那么该Hash对象在内存中的结构如下：
Redis常见对象类型的底层数据结构 - 图7

5.2 hash-hashtable

hashtable编码的哈希对象使用字典作为底层实现。字典是一种用于保存键值对的数据结构，Redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，每个哈希表节点保存的就是一个键值对。

哈希表

Redis使用的哈希表由dictht结构定义：

  1. typedef struct dictht{
  2.     // 哈希表数组
  3.     dictEntry **table;
  4.     // 哈希表大小
  5.     unsigned long size;
  6.     // 哈希表大小掩码，用于计算索引值
  7.     // 总是等于 size-1
  8.     unsigned long sizemask;
  9.     // 该哈希表已有节点数量
  10.     unsigned long used;
  11. } dictht

table属性是一个数组，数组中的每个元素都是一个指向dictEntry结构的指针，每个dictEntry结构保存着一个键值对。size属性记录了哈希表的大小，即table数组的大小。used属性记录了哈希表目前已有节点数量。sizemask总是等于size-1，这个值主要用于数组索引。比如下图展示了一个大小为4的空哈希表。
Redis常见对象类型的底层数据结构 - 图8

哈希表节点

哈希表节点使用dictEntry结构表示，每个dictEntry结构都保存着一个键值对：

  1. typedef struct dictEntry {
  2.     // 键
  3.     void *key;
  4.     // 值
  5.     union {
  6.         void *val;
  7.         unit64_t u64;
  8.         nit64_t s64;
  9.     } v;
  10.     // 指向下一个哈希表节点，形成链表
  11.     struct dictEntry *next;
  12. } dictEntry;

key属性保存着键值对中的键，而v属性则保存了键值对中的值。值可以是一个指针，一个uint64_t整数或者是int64_t整数。next属性指向了另一个dictEntry节点，在数组桶位相同的情况下，将多个dictEntry节点串联成一个链表，以此来解决键冲突问题。(链地址法)

字典

Redis字典由dict结构表示：

  1. typedef struct dict {
  2.     // 类型特定函数
  3.     dictType *type;
  4.     // 私有数据
  5.     void *privdata;
  6.     // 哈希表
  7.     dictht ht[2];
  8.     //rehash索引
  9.     // 当rehash不在进行时，值为-1
  10.     int rehashidx;
  11. }

ht是大小为2，且每个元素都指向dictht哈希表。一般情况下，字典只会使用ht[0]哈希表，ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用。rehashidx记录了rehash的进度，如果目前没有进行rehash，值为-1。
Redis常见对象类型的底层数据结构 - 图9

rehash

为了使hash表的负载因子(ht[0]).used/ht[0]).size)维持在一个合理范围，当哈希表保存的元素过多或者过少时，程序需要对hash表进行相应的扩展和收缩。rehash（重新散列）操作就是用来完成hash表的扩展和收缩的。rehash的步骤如下：
为

  1. ht[1]

哈希表分配空间

  1. 如果是扩展操作，那么ht[1]的大小为第一个大于ht[0].used*2的2^n。比如ht[0].used=5，那么此时ht[1]的大小就为16。(大于10的第一个2^n的值是16)
  2. 如果是收缩操作，那么ht[1]的大小为第一个大于ht[0].used的2^n。比如ht[0].used=5，那么此时ht[1]的大小就为8。(大于5的第一个2^n的值是8)
    1. 将保存在ht[0]中的所有键值对rehash到ht[1]中。
    2. 迁移完成之后，释放掉ht[0]，并将现在的ht[1]设置为ht[0]，在ht[1]新创建一个空白哈希表，为下一次rehash做准备。

哈希表的扩展和收缩时机：

  1. 当服务器没有执行BGSAVE或者BGREWRITEAOF命令时，负载因子大于等于1触发哈希表的扩展操作。
  2. 当服务器在执行BGSAVE或者BGREWRITEAOF命令，负载因子大于等于5触发哈希表的扩展操作。

  3. 当哈希表负载因子小于0.1，触发哈希表的收缩操作。

    渐进式rehash

    前面讲过，扩展或者收缩需要将ht[0]里面的元素全部rehash到ht[1]中，如果ht[0]元素很多，显然一次性rehash成本会很大，从影响到Redis性能。为了解决上述问题，Redis使用了渐进式rehash技术，具体来说就是分多次，渐进式地将ht[0]里面的元素慢慢地rehash到ht[1]中。下面是渐进式rehash的详细步骤：

  4. 为ht[1]分配空间。

  5. 在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash正式开始。
  6. 在rehash进行期间，每次对字典执行添加、删除、查找或者更新时，除了会执行相应的操作之外，还会顺带将ht[0]在rehashidx索引位上的所有键值对rehash到ht[1]中，rehash完成之后，rehashidx值加1。
  7. 随着字典操作的不断进行，最终会在啊某个时刻迁移完成，此时将rehashidx值置为-1，表示rehash结束。

渐进式rehash一次迁移一个桶上所有的数据，设计上采用分而治之的思想，将原本集中式的操作分散到每个添加、删除、查找和更新操作上，从而避免集中式rehash带来的庞大计算。
因为在渐进式rehash时，字典会同时使用ht[0]和ht[1]两张表，所以此时对字典的删除、查找和更新操作都可能会在两个哈希表进行。比如，如果要查找某个键时，先在ht[0]中查找，如果没找到，则继续到ht[1]中查找。

hash对象中的hashtable

  1. HSET profile name "tom"
  2. HSET profile age 25
  3. HSET profile career "Programmer"

还是上述三条命令，保存数据到Redis的哈希对象中，如果采用hashtable编码保存的话，那么该Hash对象在内存中的结构如下：
Redis常见对象类型的底层数据结构 - 图10
当哈希对象保存的所有键值对的键和值的字符串长度都小于64个字节，并且数量小于512个时，使用ziplist编码，否则使用hashtable编码。

可以通过配置文件修改该上限值。

6、集合对象

集合对象的编码可以是intset或者hashtable。当集合对象保存的元素都是整数，并且个数不超过512个时，使用intset编码，否则使用hashtable编码。

6.1 set-intset

intset编码的集合对象底层使用整数集合实现。
整数集合(intset)是Redis用于保存整数值的集合抽象数据结构，它可以保存类型为int16_t、int32_t或者int64_t的整数值，并且保证集合中的数据不会重复。Redis使用intset结构表示一个整数集合。

  1. typedef struct intset {
  2.     // 编码方式
  3.     uint32_t encoding;
  4.     // 集合包含的元素数量
  5.     uint32_t length;
  6.     // 保存元素的数组
  7.     int8_t contents[];
  8. } intset;

contents数组是整数集合的底层实现：整数集合的每个元素都是contents数组的一个数组项，各个项在数组中按值大小从小到大有序排列，并且数组中不包含重复项。虽然contents属性声明为int8_t类型的数组，但实际上，contents数组不保存任何int8_t类型的值，数组中真正保存的值类型取决于encoding。如果encoding属性值为INTSET_ENC_INT16，那么contents数组就是int16_t类型的数组，以此类推。
当新插入元素的类型比整数集合现有类型元素的类型大时，整数集合必须先升级，然后才能将新元素添加进来。这个过程分以下三步进行。

  1. 根据新元素类型，扩展整数集合底层数组空间大小。
  2. 将底层数组现有所有元素都转换为与新元素相同的类型，并且维持底层数组的有序性。
  3. 将新元素添加到底层数组里面。

还有一点需要注意的是，整数集合不支持降级，一旦对数组进行了升级，编码就会一直保持升级后的状态。
举个栗子，当执行SADD numbers 1 3 5向集合对象插入数据时，该集合对象在内存的结构如下：
Redis常见对象类型的底层数据结构 - 图11

6.2 set-hashtable

hashtable编码的集合对象使用字典作为底层实现，字典的每个键都是一个字符串对象，每个字符串对象对应一个集合元素，字典的值都是NULL。当执行SADD fruits "apple" "banana" "cherry"向集合对象插入数据时，该集合对象在内存的结构如下：
Redis常见对象类型的底层数据结构 - 图12

7、有序集合对象

有序集合的编码可以是ziplist或者skiplist。当有序集合保存的元素个数小于128个，且所有元素成员长度都小于64字节时，使用ziplist编码，否则，使用skiplist编码。

7.1 zset-ziplist

ziplist编码的有序集合使用压缩列表作为底层实现，每个集合元素使用两个紧挨着一起的两个压缩列表节点表示，第一个节点保存元素的成员(member)，第二个节点保存元素的分值(score)。
压缩列表内的集合元素按照分值从小到大排列。如果执行ZADD price 8.5 apple 5.0 banana 6.0 cherry命令，向有序集合插入元素，该有序集合在内存中的结构如下：
Redis常见对象类型的底层数据结构 - 图13

7.2 zset-skiplist

skiplist编码的有序集合对象使用zset结构作为底层实现，一个zset结构同时包含一个字典和一个跳跃表。

  1. typedef struct zset {
  2.     zskiplist *zs1;
  3.     dict *dict;
  4. }

先了解一下什么是跳跃表。

跳跃表

跳跃表(skiplist)是一种有序的数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。Redis的跳跃表由zskiplistNode和zskiplist两个结构定义，zskiplistNode结构表示跳跃表节点，zskiplist保存跳跃表节点相关信息，比如节点的数量，以及指向表头和表尾节点的指针等。

跳跃表节点 zskiplistNode

跳跃表节点zskiplistNode结构定义如下：

  1. typedef struct zskiplistNode {
  2.     // 后退指针
  3.     struct zskiplistNode *backward;
  4.     // 分值
  5.     double score;
  6.     // 成员对象
  7.     robj *obj;
  8.     // 层
  9.     struct zskiplistLevel {
  10.         // 前进指针
  11.         struct zskiplistNode *forward;
  12.         // 跨度
  13.         unsigned int span;
  14.     } level[];
  15. } zskiplistNode;

下图是一个层高为5，包含4个跳跃表节点(1个表头节点和3个数据节点)组成的跳跃表：Redis常见对象类型的底层数据结构 - 图14

  1. 层：每次创建一个新的跳跃表节点的时候，会根据幂次定律(越大的数出现的概率越低)随机生成一个1-32之间的值作为当前节点的”层高”。每层元素都包含2个数据，前进指针和跨度。
    1. 前进指针 每层都有一个指向表尾方向的前进指针，用于从表头向表尾方向访问节点。
    2. 跨度 层的跨度用于记录两个节点之间的距离。
  2. 后退指针(BW) 节点的后退指针用于从表尾向表头方向访问节点，每个节点只有一个后退指针，所以每次只能后退一个节点。
  3. 分值和成员 节点的分值(score)是一个double类型的浮点数，跳跃表中所有节点都按分值从小到大排列。节点的成员(obj)是一个指针，指向一个字符串对象。在跳跃表中，各个节点保存的成员对象必须是唯一的，但是多个节点的分值确实可以相同。

需要注意的是，表头节点不存储真实数据，并且层高固定为32，从表头节点第一个不为NULL最高层开始，就能实现快速查找。

跳跃表 zskiplist

实际上，仅靠多个跳跃表节点就可以组成一个跳跃表，但是Redis使用了zskiplist结构来持有这些节点，这样就能够更方便地对整个跳跃表进行操作。比如快速访问表头和表尾节点，获得跳跃表节点数量等等。zskiplist结构定义如下：

  1. typedef struct zskiplist {
  2.     // 表头节点和表尾节点
  3.     struct skiplistNode *header, *tail;
  4.     // 节点数量
  5.     unsigned long length;
  6.     // 最大层数
  7.     int level;
  8. } zskiplist;

下图是一个完整的跳跃表结构示例：Redis常见对象类型的底层数据结构 - 图15

有序集合对象的skiplist实现

前面讲过，skiplist编码的有序集合对象使用zset结构作为底层实现，一个zset结构同时包含一个字典和一个跳跃表。

  1. typedef struct zset {
  2.     zskiplist *zs1;
  3.     dict *dict;
  4. }

zset结构中的zs1跳跃表按分值从小到大保存了所有集合元素，每个跳跃表节点都保存了一个集合元素。通过跳跃表，可以对有序集合进行基于score的快速范围查找。zset结构中的dict字典为有序集合创建了从成员到分值的映射，字典的键保存了成员，字典的值保存了分值。通过字典，可以用O(1)复杂度查找给定成员的分值。
假如还是执行ZADD price 8.5 apple 5.0 banana 6.0 cherry命令向zset保存数据，如果采用skiplist编码方式的话，该有序集合在内存中的结构如下：Redis常见对象类型的底层数据结构 - 图16

8、总结

总的来说，Redis底层数据结构主要包括简单动态字符串(SDS)、链表、字典、跳跃表、整数集合和压缩列表六种类型，并且基于这些基础数据结构实现了字符串对象、列表对象、哈希对象、集合对象以及有序集合对象五种常见的对象类型。每一种对象类型都至少采用了2种数据编码，不同的编码使用的底层数据结构也不同。