redis的数据结构——跳表（Skiplist）

跳表（Skiplist）是一种用于有序数据存储的高效数据结构，它在Redis中用于实现有序集合（Sorted Set，zset）的底层存储。当有序集合中的数据较多时，Redis会选择使用跳表来存储元素，以便在保持数据有序的同时提供高效的插入、删除、查找操作。

跳表的基本结构

跳表是一种多层链表结构，它通过在基本有序链表的基础上添加多层索引，来加速查找的速度。跳表的每一层都是一个链表，底层（Level 0）包含所有元素，而更高层的链表则是其下一层链表的子集。这种结构类似于平衡树，能够在O(log n)时间复杂度内进行快速的查找、插入和删除操作。

跳表由以下几部分组成：

1. 节点（Node）：跳表的基本组成单位，每个节点包含：

   • 数据域：存储键值对中的成员和分值。
   • 后向指针数组：每个节点可以有多层指针（称为“向前指针”），指向该层中的下一个节点。
   • 后退指针：指向当前节点在底层链表中的前一个节点，便于反向遍历。
   • 跨度（Span）：记录从当前节点到下一个节点的跨度，即中间跨过的节点数量，用于计算排名。

2. 表头（Header）：跳表的起始节点，通常包含多个层次的指针，每层指向该层的第一个节点。