05 | 有序集合为何能同时支持点查询和范围查询？-Redis源码剖析与实战

当前位置:　首页>> 技术小册>> Redis源码剖析与实战

### 05 | 有序集合为何能同时支持点查询和范围查询？

在Redis的众多数据结构中，有序集合（Sorted Set）以其独特的性质在众多应用场景中大放异彩。它不仅能够像集合（Set）一样保证元素的唯一性，还能为每个元素关联一个浮点数分数（score），从而实现元素的排序。这种设计使得有序集合能够同时高效地支持点查询（即根据确切的元素值查找）和范围查询（根据分数范围查找一系列元素），为许多需要排序和快速检索的场景提供了强大的支持。本章节将深入探讨有序集合如何实现这一功能，以及背后的数据结构和算法原理。

#### 一、有序集合的基本概念

有序集合（Sorted Set）在Redis中是一个不包含重复元素的字符串集合，每个元素都会关联一个浮点数分数（score）。这个分数用于对集合中的元素进行从小到大的排序。有序集合提供了丰富的操作接口，包括添加元素、删除元素、获取元素排名、通过分数或排名范围查询元素等。

#### 二、有序集合的数据结构

为了实现高效的点查询和范围查询，Redis中的有序集合采用了跳表（Skip List）和哈希表（Hash Table）两种数据结构相结合的方式。这种混合结构兼顾了查询效率和内存使用的优化。

##### 1. 跳表（Skip List）

跳表是一种可以替代平衡树的数据结构，它通过多层索引来提高查询效率。在有序集合中，跳表主要用于实现范围查询，因为它能够快速地跳过大量不需要检查的元素，直接定位到可能包含目标元素的位置区间。

- **层（Level）**：跳表的每一层都是一个有序的链表，但不同层链表的元素数量不同。最高层的链表包含的元素最少，但能够覆盖所有层的元素范围，从而允许快速地从一端跳到另一端。
- **前进指针（Forward Pointers）**：每个节点有多个前进指针，分别指向同一层中下一个节点以及更高层中更远的节点。这些指针使得跳表能够迅速地进行跳跃，减少查找过程中需要检查的节点数。
- **后退指针（Backward Pointers，可选）**：虽然Redis的跳表实现中并未直接包含后退指针，但了解这一点有助于理解跳表作为双向链表的一种变体，在某些应用场景下可能需要的额外功能。
- **分数（Score）和值（Value）**：在有序集合的上下文中，跳表的每个节点存储了元素的分数和值。分数用于排序，而值则是需要存储或检索的实际数据。

##### 2. 哈希表（Hash Table）

哈希表在有序集合中主要用于支持快速的点查询。通过哈希表，Redis可以快速地将元素的值映射到其对应的分数和节点位置，从而实现O(1)时间复杂度的点查询操作。

- **键（Key）与值（Value）**：在有序集合的哈希表中，键是元素的值，而值则是一个指向跳表中相应节点的指针或是一个包含节点信息的复杂结构（取决于具体实现）。
- **冲突解决**：哈希表通过哈希函数将键映射到表的某个位置，当多个键哈希到同一位置时，Redis会采用链表或红黑树等数据结构来解决冲突。

#### 三、点查询的实现

点查询是指根据元素的值直接查找其对应的分数或排名。在Redis的有序集合中，点查询主要依赖于哈希表来实现。

1. **哈希查找**：首先，Redis会计算待查询元素值的哈希值，并在哈希表中查找该哈希值对应的槽位。
2. **冲突解决**：如果槽位中存在多个元素（即哈希冲突），Redis会遍历这些元素，通过比较它们的值来找到精确的匹配项。
3. **返回结果**：一旦找到匹配的元素，Redis就可以直接从哈希表的值部分（或指向跳表节点的指针）中获取该元素的分数或进行进一步的操作。

#### 四、范围查询的实现

范围查询是指根据分数的范围来查找一系列元素。在有序集合中，范围查询主要通过跳表来实现。

1. **确定起始点**：首先，Redis会利用哈希表快速定位到范围查询起始分数的最小可能节点（如果哈希表直接支持这种查找的话，或者通过遍历跳表的前几层来近似定位）。
2. **遍历跳表**：从起始点开始，Redis会沿着跳表的层级逐层向下遍历，直到达到最底层。在遍历过程中，Redis会检查每个节点的分数是否满足查询范围，如果是，则将该节点的元素加入结果集。
3. **优化查找**：由于跳表的层级设计，Redis能够跳过大量不满足条件的节点，从而显著提高查找效率。特别是当查询范围较宽或查询点接近集合的两端时，这种优势尤为明显。

#### 五、性能与空间复杂度分析

- **时间复杂度**：点查询的时间复杂度为O(1)，因为哈希表提供了快速的元素定位能力。范围查询的时间复杂度主要取决于跳表的层数和查找范围内元素的数量，但通常可以认为是O(logN)，其中N是集合中元素的数量。
- **空间复杂度**：有序集合的空间复杂度主要由哈希表和跳表共同决定。哈希表需要额外的空间来存储键值对和冲突解决结构（如链表或红黑树），而跳表则需要额外的空间来存储多层索引和节点之间的指针。然而，这些额外空间相对于存储的元素数量来说是可接受的，并且随着现代计算机硬件的发展，这些开销变得更加微不足道。

#### 六、总结

Redis中的有序集合通过巧妙地结合哈希表和跳表两种数据结构，实现了高效的点查询和范围查询。哈希表保证了点查询的极致速度，而跳表则提供了灵活的范围查询能力。这种设计不仅满足了多种应用场景的需求，还展示了Redis在数据结构选择和算法优化方面的深厚功力。对于需要处理大量有序数据的开发者来说，了解并掌握有序集合的工作原理无疑将是一笔宝贵的财富。

该分类下的相关小册推荐：

Redis的Lua脚本编程

Redis核心技术与实战

Redis零基础到实战

Redis面试指南