Redis数据表现形式与底层数据结构

本文是我最近在复习Redis时所整理总结的知识点，主要参考了《Redis设计与实现》一书，本文主要内容是关于Redis的基础数据表现形式与底层数据结构。

表现形式

1. string字符串

• 普通字符串：最常见的形式，直接存储字符串内容（如用户名称、配置信息）。
• 数字计数器：利用 Redis 的原子性操作（如 INCR、DECR）实现高效计数（如点赞数、访问量统计）。
• 二进制数据：通过 SET 命令存储二进制数据，适用于缓存小型文件（如缩略图）

# 存储字符串
SET username "zhangsan"

# 获取字符串
GET username  # 输出: zhangsan

# 数字自增（计数器场景）
INCR page_views  # 初始值为0，执行后变为1
INCRBY page_views 10  # 增加10，变为11

# 存储二进制数据（如图片Base64编码）
SET image:1 "base64_data_here"

2. hash散列表

类似字典的键值对集合，每个字段（field)对应一个值value，适用于存储对象数据

• 对象存储：将对象的多个属性存储为hash的字段，如用户信息（ID、姓名、年龄等）
• 配置项集合：将相关配置以字段形式存储
• 计数器组合：多个相关计数器存储在一个Hash中（如商品的浏览量、收藏量、销量）

# 存储用户信息
HSET user:1 name "lisi" age 25 city "beijing"

# 获取单个字段
HGET user:1 name  # 输出: lisi

# 获取所有字段
HGETALL user:1  # 输出: name lisi age 25 city beijing

# 字段自增
HINCRBY user:1 age 1  # 年龄加1

3. Set（集合）—— 无序唯一的元素集合

• 数据结构本质：基于哈希表或有序集合实现的无序、唯一元素集合，支持交集、并集、差集等集合运算。

• 数据表现形式及特点

  • 唯一集合：存储不重复的元素（如用户关注的标签、商品的分类）。
  • 集合运算：利用交集、并集等操作处理数据（如共同关注的好友、商品的同类推荐）。
  • 随机抽样：通过 SRANDMEMBER 命令从集合中随机获取元素（如抽奖、随机推荐）。

# 添加元素（自动去重）
SADD user:1:tags "tech" "music" "sports"
SADD user:2:tags "tech" "reading" "sports"

# 获取所有元素
SMEMBERS user:1:tags  # 输出: tech music sports

# 交集运算（共同标签）
SINTER user:1:tags user:2:tags  # 输出: tech sports

# 随机获取元素（抽奖场景）
SRANDMEMBER lucky_draw_users 10  # 从集合中随机获取10个用户

4. sort_set有序集合—带权重的有序集合

• 数据结构本质：每个元素关联一个分数（score），按分数排序的集合，底层通过跳表（SkipList）实现高效查询。

• 数据表现形式及特点

  • 排行榜：以分数作为排名依据（如点赞数、成绩排名）。
  • 时间线排序：以时间戳作为分数，按时间排序（如最新动态、热榜）。
  • 范围查询：按分数范围快速查询元素（如前 10 名、分数在 80-90 之间的用户）。
  • 权重集合：元素权重（分数）可动态调整（如商品热度随时间衰减）。

# 添加元素（分数为点赞数）
ZADD post_rank 100 "post1" 200 "post2" 150 "post3"

# 获取排名前3的帖子（按分数降序）
ZREVRANGE post_rank 0 2 WITHSCORES  # 输出: post2 200 post3 150 post1 100

# 获取分数在100-200之间的帖子
ZRANGEBYSCORE post_rank 100 200 WITHSCORES

# 更新分数（帖子热度衰减）
ZINCRBY post_rank -10 "post1"  # 点赞数减10

5. list列表–有序可重复的元素集合

• 数据结构本质：双向链表实现的有序列表，支持从头部或尾部插入、删除元素，适用于需要顺序存储的数据。

• 数据表现形式及特点

  • 队列（FIFO）：通过 RPUSH（右入）和 LPOP（左出）实现先进先出队列（如消息队列）。
  • 栈（LIFO）：通过 RPUSH 和 RPOP 实现后进先出栈（如操作日志回退）。
  • 有序列表：按插入顺序存储元素，支持范围查询（如最新评论列表、聊天记录）。
  • 排行榜（部分场景）：结合范围查询实现简单的时间线排行榜（如最新发布的文章）。

# 右插入元素（队列场景）
RPUSH message_queue "msg1" "msg2" "msg3"

# 左弹出元素（队列消费）
LPOP message_queue  # 输出: msg1，队列变为["msg2", "msg3"]

# 获取列表范围元素（如最新10条评论）
LRANGE comments:post1 0 9  # 获取索引0到9的元素（最新10条）

# 左插入元素（栈场景）
LPUSH operation_stack "action1" "action2"
RPOP operation_stack  # 弹出最后插入的"action2"

6. bitmap–基于位运算的集合

• 数据结构本质：并非独立的数据结构，而是基于string类型的位操作接口，用每一位表示布尔值。

• 数据表现形式及特点：

  • 状态标记：用位表示状态（如用户是否在线、任务是否完成）。
  • 统计计数：通过位运算统计大量数据的状态（如活跃用户数、签到天数）。
  • 高效存储：相比 Set 存储布尔值更节省空间（100 万用户仅需约 125KB）。

# 设置用户在线状态（用户ID=1001，位索引=1000）
SETBIT online_users 1000 1  # 1表示在线

# 获取用户状态
GETBIT online_users 1000  # 输出: 1

# 统计在线用户数
BITCOUNT online_users  # 计算值为1的位数

# 多个位图交集（如同时在线的用户）
BITOP AND online_today online_yesterday online_users

Redis 的数据结构设计使其具备灵活处理多种场景的能力：

• String 作为基础结构，适用于简单值存储和计数。
• Hash 擅长存储对象，减少内存碎片化。
• List 适合处理有序序列，如队列和历史记录。
• Set 和 Sorted Set 则针对集合运算和排序场景优化。
• Bitmap 以极致的空间效率处理大规模布尔值统计。

底层数据结构

1. 简单动态字符串（二进制安全的字符串）

1. SDS可以直接获取字符串的长度，时间复杂度为O(1)，结构体中有专门记录长度和空闲空间的字段，无需像C语言一样进行遍历
2. SDS具有空间预分配特性。字符串拓展时，会根据当前长度预分配额外空间，减少分配空间次数
3. 当字符串长度减少时，SDS不会立即改变内存结构，而是将减少部分标记为可用，后续拓展的长度如果不超过可用长度，则无需重新分配空间
4. redis的SDS可以存储二进制数据和文本，根据长度界定字符串范围，精确处理文本和二进制数据

+-------------------+-------------------+------------------+----------------+
|       len         |       free        |       buf        |   终止符 '\0'  |
|  (4字节/8字节)    |  (4字节/8字节)    |   (动态数组)     |   (1字节)      |
+-------------------+-------------------+------------------+----------------+
       ↑                   ↑                  ↑                  ↑
       |                   |                  |                  |
       |                   |                  |                  |
+------+-------------------+------------------+------------------+------+
|  记录字符串长度        记录未使用空间      存储字符串数据      兼容C字符串  |
|  （不包含终止符）      （字节数）          （如"redis"）       格式        |
+-------------------------------------------------------------------------+

特点：

1. 常数时间获取长度
2. 有效防止缓冲区溢出
3. 减少修改字符串带来的内存重分配的次数
4. 二进制安全
5. 兼容C字符串函数，这样可以方便我们直接调用C字符串函数

SDS通过未使用空间解除了字符串长度和底层数组长度之间的关联，sds中，数组的长度不一定就是字符数量+1，数组中包含了未使用的字节，这些字节数就是SDS的free属性记录。通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化策略：

• 空间预分配
  空间预分配主要用于SDS的字符串增长操作，当我们使用API对SDS进行修改，并且还可能会进行空间的扩容时，程序不仅会为SDS分配所需要修改的必要空间，还会额外分配部分未使用空间，额外空间的数量主要由以下公式决定：

  1. 如果SDS修改之后，长度没有超过1MB（也就是len小于1MB），那么就会额外分配和len长度一样大小的free空间，例如 len = 16， 那么 free = 16，此时总空间就是 16 + 16 + 1 = 33字节
  2. 如果SDS修改之后，长度超过1MB，那么程序就会分配 1MB的额外未使用空间，即 len = 20MB, free = 1MB，此时总空间大小为 20MB+1MB+1byte
     在扩展SDS空间之前，SDS API会检查未使用空间是否足够，如果足够了就不会内存重分配。这种预分配策略，SDS将连续增长N次字符所需要的内存重分配次数从必定N次降低为最多N次。

• 惰性空间释放
  用于优化空间长度缩短的情况。当SDS中的字符串长度需要缩短时，并不会马上内存重分配来回收缩短的空间，而是利用free来记录这些释放的字节数量，等待将来使用。

2. 整数集合

基础概念

整数集合是Redis中保存整数值的集合抽象数据结构，可以保存类型为int16_t、int32_t、int64_t，并且保证集合中不会出现重复值。

底层的结构源码：

typedef struct intset {
    /// 编码方式
    uint32_t encoding;
    /// 集合包含的元素数量
    uint32_t length;
    /// 保存元素的数组
    int8_t contents[];
} intset;

contents数组就是整数集合的底层实现，contents数组中的每一个元素都是按照值的大小，从小到大排序，不包含重复值。

• endcoding：代表存储数据的类型，分别有INTSET_ENC_INT16, INTSET_ENC_INT32, INTSET_ENC_INT64，最后的数字代表uintxx_t类型
• length：代表整数集合中包含的所有元素数量（contents数组的长度）

升级

当往整数集合中添加一个比现有所有元素类型都长的元素时，整数集合需要首先升级，才能进行添加。因为涉及到升级，那么新元素的类型要么比原始元素都大，要么都小，所有时间复杂度 为O(N)

升级的步骤：

• 根据新元素的类型，拓展底层contents数组大小，并且为新元素分配空间
• 将原始的元素拓展为新元素相同的类型，然后将原始元素放到正确的位置（保持有序性）
• 将新元素插入到底层数组

升级带来的好处：

• 提升了灵活性，通常不会将2种不同类型的元素添加到数组中，整数数组具备升级机制可以自动扩展内存空间，保证里面存储的都是同一个数据类型
• 数据升级可以让整数集合中同时保存三种不同类型的值，升级只会在有需要的时候进行

降级

整数集合不支持降级，一旦升级之后，编码（encoding）就会一直保持当前的类型。

3. 链表

Redis 链表的实现基于双向链表，每个链表节点（listNode）和链表本身（list）都有专门的结构体定义

listnode

链表节点源码定义如下：

typedef struct listNode {
    struct listNode *prev;  // 前驱节点指针，指向当前节点的前一个节点
    struct listNode *next;  // 后继节点指针，指向当前节点的后一个节点
    void *value;            // 节点的值，为 void* 类型，可存储任意类型数据
} listNode;

listnode持有prev和next指针，通过多个listnode组成双端链表，可以支持双向遍历；value 字段为指针类型，可关联字符串、整数等任意数据，使链表能存储多种类型的值。

list

通过多个listnode就可以组成双端链表，但是需要一个“头”来管理双端链表，记录链表元信息

typedef struct list {
    listNode *head;         // 指向链表的头节点
    listNode *tail;         // 指向链表的尾节点
    unsigned long len;      // 链表的长度（节点数量）
    void *(*dup)(void *ptr); // 节点值复制函数（用于深拷贝）
    void (*free)(void *ptr); // 节点值释放函数（用于内存回收）
    int (*match)(void *ptr, void *key); // 节点值比较函数（用于查找匹配）
} list;

成员变量分别是：

• 头/尾指针：head/tail分别可以指向链表的第一个和最后一个节点，保证获取头尾节点或头插尾插时时间复杂度为O(1)
• Len：长度字段记录链表的长度（节点数量），可以直接通过获取该值来获取链表大小
• 函数指针：dup\free\match用于实现链表多态性，支持对不同类型的value进行定制操作

主要特点

• 双向遍历(持有prev和next指针)
• 无环结构，头节点head->prev尾节点tail->next为NULL，首尾不相连接，避免环形链表可能导致遍历死循环
• 头插/尾插，头删/尾删，获取头尾指针/链表长度时间复杂度均是O（1）
• 内存管理可根据value类型定制，避免内存泄漏
• 可以借助match函数指针实现多态

主要操作

1. 插入节点

   • 头部插入（listAddNodeHead）：
     新建节点，将其 next 指向原头节点，原头节点 prev 指向新节点，更新 head 为新节点；若链表为空，则 tail 也指向新节点。
     时间复杂度：O (1)。
   • 尾部插入（listAddNodeTail）：
     类似头部插入，新建节点的 prev 指向原尾节点，原尾节点 next 指向新节点，更新 tail 为新节点；若链表为空，则 head 也指向新节点。
     时间复杂度：O (1)。
   • 指定节点前后插入（listInsertNode）：
     根据插入位置（指定节点的前 / 后），调整新节点与前后节点的指针关系。
     时间复杂度：O (1)（已知指定节点的情况下）。

2. 删除节点（listDelNode）

   • 找到待删除节点后，通过 prev 和 next 指针调整其前后节点的关联（若为头节点则更新 head，若为尾节点则更新 tail），释放节点的 value（调用 free 函数）和节点本身。
   • 时间复杂度：O (1)（已知待删除节点的情况下）。

3. 遍历链表（listIter）

   • 通过迭代器（listIter）遍历链表，迭代器包含当前节点指针和遍历方向（正向 / 反向），每次调用 listNext 可获取下一个节点。
   • 遍历整个链表的时间复杂度：O (N)（N 为节点数量）。

4. 复制链表（listDup）

   • 新建一个链表，遍历原链表的每个节点，通过 dup 函数复制节点的 value，并依次插入新链表。
   • 时间复杂度：O (N)。

5. 查找节点（listSearchKey）

   • 遍历链表，通过 match 函数比较节点的 value 与目标 key，返回匹配的第一个节点。
   • 时间复杂度：O (N)（最坏情况需遍历所有节点）。

应用场景

链表是 Redis 列表键（List）的底层实现之一（另一种是压缩列表 ziplist，用于节省内存），当列表键包含的元素较多或元素为长字符串时，Redis 会自动将底层实现转换为链表。

还可以用于：

1. 发布订阅系统：存储订阅者信息，方便添加 / 删除订阅者。
2. 慢查询日志：记录执行时间超过阈值的命令，支持按时间顺序插入和遍历。
3. 监视器（Monitor）：存储连接到服务器的监视器客户端，便于向其发送命令执行信息。
4. 事务队列：在事务执行过程中，临时存储待执行的命令序列。

与压缩列表的对比

特性	Redis 链表	压缩列表（ziplist）
内存连续性	不连续（节点分散存储）	连续（紧凑存储）
插入 / 删除效率（中间）	O (1)（已知节点时）	O (N)（需移动元素）
遍历效率	O(N)	O(N)
内存开销	较高（节点含指针和额外字段）	较低（节省指针空间）
适用场景	元素多、元素长	元素少、元素短

4. 压缩列表（ziplist）

压缩列表是列表（list）和哈希（hash）的底层实现之一，适合用于存储包含少量元素的列表，且每个元素要么是小整数值，要么是较短的字符串。

结构

压缩列表的内存是连续的，由一组连续存储的内存块组成顺序型结构，可包含任意数量的节点（entry），每个节点可保存一个字节数组或整数值。其组成部分如下：

--------------------------------------------------------------------
<zlbytes><zltail><zllen><entry1><entry2><entry3><...><entryN><zlend>
--------------------------------------------------------------------

字段	类型	含义
zlbytes	uint32_t	记录整个压缩列表的占用内存字节数，用于内存重分配或计算zlend位置
zltail	uint32_t	记录压缩列表起始地址到尾节点的距离，通过偏移量可直接获取尾节点地址
zllen	uint16_t	记录节点数量。若值小于UINT16_MAX（65535），则为实际数量；否则需遍历获取
entryX	–	列表节点，长度由保存的内容决定
zlend	uint8_t	存储0xFF，用于标记压缩列表末端

压缩列表节点（entry）

每个压缩列表节点可以保存一个字节数组或者整数值，字节数组可以是三种不同长度中的一种：

1. 长度小于等于63（2^6-1)字节的字节数组
2. 长度小于等于16483（2^14-1)字节的字节数组
3. 长度小于等于2^32-1字节的字节数组

如果存储的是整数，则可以是以下六种长度的其中一种

1. 4位长，介于0-12之间的无符号整数
2. 1位长的有符号整数
3. 3字节长度有符号整数
4. int16_t类型整数
5. int32_t类型整数
6. int64_t类型整数
   每个节点可保存字节数组或整数值，结构由previous_entry_length、encoding、content三部分组成：

----------------------------------------
<previous_entry_length><encoding><content>
----------------------------------------

1. previous_entry_length
   记录前一个节点的长度，支持通过指针运算获取上一个节点的起始地址，长度可为1字节或5字节：

   • 若前一个节点长度＜254字节：占用1字节，直接存储长度值。
   • 若前一个节点长度≥254字节：占用5字节，第一个字节为0XFE（254），后四个字节存储实际长度。

2. encoding
   记录content的数据类型及长度：

   • 字节数组编码：最高位为00、01、10，长度为1/2/5字节，去除最高2位后的值为字节数组长度。
   • 整数编码：最高位为11，长度为1字节，去除最高2位后的值表示整数类型和长度。

3. content
   保存节点的值（字节数组或整数），长度由encoding字段决定。

连锁更新

连锁更新（cascading update）是压缩列表在插入或删除元素时可能触发的特殊现象。

• 原理：
  当元素长度变化导致后续节点的previous_entry_length从1字节扩展为5字节（或反之）时，这种变化可能持续影响所有后续节点，直至所有前向节点长度更新完成。

• 典型场景：
  压缩列表中存在连续多个长度为250~254字节的元素（prevlen均为1字节），此时插入一个长度＞254字节的新元素，会导致后续元素的prevlen从1字节扩展为5字节，引发连锁反应。

• 示例：
  假设连续3个元素e1、e2、e3的长度均为250字节（prevlen为1字节）：

  1. 插入长度260字节的e0到e1前，e1的prevlen需从1字节扩展为5字节，导致e1总长度变为254字节。
  2. 若e1原长度为253字节，扩展后总长度为257字节（＞254），则e2的prevlen需扩展为5字节，以此类推。

• 性能影响：
  连锁更新本质是多次内存重分配和数据拷贝，最坏情况下时间复杂度为O(N²)。

5. 字典

字典是哈希键的底层实现，每个字典包含两个哈希表（平时使用一个，rehash时使用另一个）。
其底层结构示意图如下：

+-------------------------------+
|           dict（字典）         |
+-------------------------------+
|  type: dictType*              |  // 类型特定函数（如键值对操作函数）
|  privdata: void*              |  // 传给类型函数的参数
|  ht: dictht[2]                |  // 哈希表数组（ht[0]默认使用，ht[1]用于rehash）
|  rehashidx: long              |  // rehash进度（-1表示未进行）
|  iterators: unsigned long     |  // 正在使用的迭代器数量
+-------------------------------+
           |
           ├─────────────────┬─────────────────┐
           ↓                 ↓                 ↓
+---------------------+  +---------------------+
|    dictht[0]        |  |    dictht[1]        |  // 哈希表结构（ht[0]和ht[1]）
+---------------------+  +---------------------+
|  table: dictEntry** |  |  table: dictEntry** |  // 哈希表数组（存储dictEntry指针）
|  size: unsigned long |  |  size: unsigned long |  // 哈希表大小（2^n）
|  sizemask: unsigned long| |  sizemask: unsigned long|  // 掩码（size-1，用于计算索引）
|  used: unsigned long |  |  used: unsigned long |  // 已使用节点数量
+---------------------+  +---------------------+
           |
           ├──────────┬──────────┬──────────┬──────────┐
           ↓          ↓          ↓          ↓          ↓
+----------------+ +----------------+ +----------------+
|  dictEntry*    | |  dictEntry*    | |  dictEntry*    |  // 哈希表节点（链表解决冲突）
+----------------+ +----------------+ +----------------+
|  key: void*    | |  key: void*    | |  key: void*    |  // 键（如字符串对象）
|  val: void*    | |  val: void*    | |  val: void*    |  // 值（如字符串/列表等对象）
|  next: dictEntry*| |  next: dictEntry*| |  next: dictEntry*|  // 下一个节点（解决键冲突）
+----------------+ +----------------+ +----------------+
                          |
                          ↓
                  +----------------+
                  |  dictEntry*    |  // 冲突节点（通过链表链接）
                  +----------------+
                  |  key: void*    |
                  |  val: void*    |
                  |  next: NULL    |
                  +----------------+

结构

字典的源码结构如下：

typedef struct dict {
    dictType *type;               // 类型特定函数
    void *privdata;               // 传给类型函数的参数
    dictht ht[2];                 // 哈希表数组
    long rehashidx;               // rehash进度，-1表示未进行
    unsigned long iterators;      // 正在使用的迭代器数量
} dict;

• type：指向dictType结构的指针，包含操作特定类型键值对的函数（如复制、释放、比较）。
• privdata：传给类型函数的可选参数。
• ht：包含两个dictht哈希表，ht[0]为默认表，ht[1]用于rehash。
• rehashidx：标识rehash进度，-1表示未进行，非负数表示当前处理的索引。

键冲突

Redis使用链地址法解决键冲突：每个哈希表节点通过next指针形成单向链表，新节点采用头插法插入链表（因链表无尾指针）。

Rehash

为维持合理的负载因子，字典会动态扩容或缩容，通过rehash实现：

1. 分配空间：

   • 扩容：ht[1]大小为第一个≥ht[0].used*2的2ⁿ。
   • 缩容：ht[1]大小为第一个≥ht[0].used的2ⁿ。

2. 渐进式rehash：

   1. 为ht[1]分配空间，字典同时持有ht[0]和ht[1]。
   2. 设rehashidx=0，标志rehash开始。
   3. 每次对字典执行增删改查时，顺带将ht[0]中rehashidx索引的键值对迁移到ht[1]，并递增rehashidx。
   4. 当ht[0]所有键值对迁移完成，设rehashidx=-1，释放ht[0]，将ht[1]改为ht[0]，并创建新的ht[1]。

6. 跳表（skiplist）

跳表是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

zskiplist

Redis使用跳表作为有序集合键的底层实现，如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员是比较长的字符串时，Redis就会使用跳表来作为有序集合的底层实现。
Redis中使用跳表只有两个地方：1、有序集合的底层实现 2、集群节点中用作内部数据结构

zskiplist结构，源码如下

typedef struct zskiplist {
    // 头尾节点指针
    struct zskiplistNode *header, *tail;
    // 跳表长度，即节点总数
    unsigned long length;
    // 跳表的最大层数
    int level;
} zskiplist;

包含了以下结构：

1. header:指向跳表的表头结点
2. tail：指向跳表的表尾节点
3. level：记录目前跳表内，层数最大的那个节点的层数（表头节点的层数不算在内）
4. length：记录跳表长度（跳表目前的节点数量）
   仅靠多个跳表节点就可以组成一个跳表，但是必须要使用zskiplist结构来管理跳表，比如快速查找或者快速获取节点数量。
   右侧分别是其中的跳表节点（zskiplistnode)，每个节点包含了层、后退指针、分值以及成员对象。

zskiplistnode

在redis源码中跳表节点是：

/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    // 成员对象，即有序集合中的member
    sds ele;
    // 分值，即有序集合中的score，跳表按此排序
    double score;
    // 后退指针，用于从尾部向前遍历
    struct zskiplistNode *backward;
    // 层数组，每个节点的层数随机生成
    struct zskiplistLevel {
        // 前进指针，指向该层的下一个节点
        struct zskiplistNode *forward;
        // 跨度，表示从当前节点到forward所指节点跨越的节点数
        unsigned long span;
    } level[];
} zskiplistNode;

跳表节点的每个字段的含义：

1、层（level）
level[]中可以包含多个元素，每个元素都是指向其他节点的一个指针，通过访问这些其他节点的指针来实现快速访问，层数越多访问速度会更快；每当生成一个新zskiplistnode时，会依据幂次定律（越大的数出现的概率越小）随机生成一个在1-32之间的level数组的大小，这个大小就是层的高度。

2、前进指针 （struct zskiplistNode *forward）
每个层都有指向表尾方向的前进指针（level[i].forward），使用这个指针从表头向表尾访问数据，每次新到一层时，会找到本层的前进指针，然后依次类推，直到遇到了一个NULL，表示已经到了表尾。

3、跨度 （level[i].span）
在跳表中，每个节点包含多个索引层（底层为原始数据链表，上层为索引），每个索引层都指向另一个节点。跨度是指当前节点的某一层索引，到它所指向的节点之间，间隔的节点数量（包括目标节点本身）。底层（第 0 层）的跨度恒为 1，因为底层是原始链表，每个节点的下一个节点直接相邻，间隔为 1。
跨度的核心作用是辅助计算节点在原始链表中的位置（或距离），从而在查找、插入、删除等操作中快速定位目标节点，避免遍历所有节点。

主要的作用包括：

1. 快速计算排名或者位置
   在跳表中，如果要查找某个节点在原始链表中的排名，或者计算两个节点的距离时，不用遍历底层链表，可以直接通过累加路径上的跨度实现。
2. 可以优化查找路径
   查找过程中，跳表可以比较当前节点的下一个节点的值与目标值，决定是否需要沿着本层遍历，跨度可以判断跳跃的节点数量是否合理，避免无效的层级切换。
3. 维护索引一致性
4. 插入或者删除节点时，跳表需要调整受影响节点的索引层的指针，跨度也需要一起更新，保证索引层指向的节点间隔正确。例如：插入一个新节点后，其前驱节点在某几层的跨度需要加 1；删除一个节点后，其前驱节点在某几层的跨度需要减 1。

实例：
假设跳表的底层链表为：1 -> 3 -> 5 -> 7，且有两层索引：

• 第 1 层索引：1 -> 5（1 的第 1 层跨度为 3，因为从 1 到 5 间隔 3 个节点：1、3、5）。
• 第 2 层索引：1 -> 7（1 的第 2 层跨度为 4，因为从 1 到 7 间隔 4 个节点）。
  当查找节点5时：

1. 从第 2 层开始，1 的第 2 层指向 7，7>5，因此降层到第 1 层。
2. 第 1 层中，1 的跨度为 3，指向 5，5 等于目标值，累加跨度（3）即为 5 的排名（第 3 位）。

4、后退指针
节点的后退指针用于从表尾向表头方向访问节点，每个节点只有一个后退指针，每次只能后退到前一个节点。例如，程序可以通过跳表的tail指针访问链表尾节点，然后透过回退指针访问倒数第二个节点，依次类推。

5、分值和成员
节点分值是double类型，跳表中的所有节点都按照分值从小到大的顺序排序。
节点成员对象是一个指针，指向一个字符串对象，字符串对象保存着一个SDS值。在同一个条表中，每个节点保存的成员对象都是唯一的，多个节点保存的分值可以相同，分值相同的节点将按照成员对象在字典中的大小来进行排序，成员对象较小的节点排在前面，较大的对象排在后面。

最后

本文主要内容参考自《Redis设计与实现》，部分底层结构的原理图参考AIGC绘制，我刚开始写文章，有很多逻辑或者知识点错误的地方还请各位大佬海涵，本人接收一切批评并且善于及时加以改正，希望自己能一直坚持，如有侵权，请联系我删除~