zset底层数据结构（set 底层）

## Redis Zset 底层数据结构### 简介Zset（Sorted Set）是 Redis 中的一种数据结构，它允许存储带分数的有序集合。这意味着每个元素除了自身值以外，还关联着一个分数，并根据分数进行排序。Zset 通常用于实现排行榜、推荐系统等场景。### 底层数据结构 - 跳跃表 (Skip List)Redis 使用

跳跃表 (Skip List)

作为 Zset 的底层数据结构。跳跃表是一种概率性数据结构，它通过在链表的基础上增加多级索引来实现高效的查找、插入和删除操作。#### 跳跃表的结构跳跃表由多个层级组成，每个层级都是一个有序链表。最底层链表包含所有元素，而更高层级的链表以一定概率包含底层链表中的元素。每个节点都指向更高层级中的相同元素节点，形成多级索引。#### 跳跃表的操作

查找：

从最高层级开始查找，如果当前层级没有找到目标元素，则向下层级查找，直到找到目标元素或到达底层链表。

插入：

首先在底层链表中插入新节点，然后根据概率决定是否将节点插入更高层级链表。

删除：

首先在底层链表中删除节点，然后删除所有指向该节点的索引。#### 跳跃表优点

高效的查找、插入和删除操作：

跳跃表可以在平均 O(log n) 时间内完成这些操作，比平衡树稍微慢一些，但比链表快得多。

易于实现：

与平衡树相比，跳跃表的实现相对简单。

空间效率：

跳跃表的空间效率较高，因为它只存储指向其他节点的指针，而不是整个数据。#### 跳跃表缺点

空间开销：

与简单的链表相比，跳跃表需要额外的空间来存储索引。

随机访问：

跳跃表不支持随机访问元素，需要从头开始遍历。### Zset 的实现Zset 使用跳跃表来存储元素和分数，并使用哈希表来存储元素的索引。

跳跃表：

存储元素和分数，并根据分数进行排序。

哈希表：

存储元素的索引，用于快速查找元素。当执行 Zset 操作时，Redis 会根据需要使用跳跃表和哈希表来完成操作。### 总结Zset 使用跳跃表作为底层数据结构，它可以高效地实现有序集合的操作。跳跃表是一种概率性数据结构，它在空间效率和查找效率之间取得平衡。Redis 使用跳跃表和哈希表来实现 Zset，提供高效的存储和查询功能。

Redis Zset 底层数据结构

简介Zset（Sorted Set）是 Redis 中的一种数据结构，它允许存储带分数的有序集合。这意味着每个元素除了自身值以外，还关联着一个分数，并根据分数进行排序。Zset 通常用于实现排行榜、推荐系统等场景。

底层数据结构 - 跳跃表 (Skip List)Redis 使用 **跳跃表 (Skip List)** 作为 Zset 的底层数据结构。跳跃表是一种概率性数据结构，它通过在链表的基础上增加多级索引来实现高效的查找、插入和删除操作。

跳跃表的结构跳跃表由多个层级组成，每个层级都是一个有序链表。最底层链表包含所有元素，而更高层级的链表以一定概率包含底层链表中的元素。每个节点都指向更高层级中的相同元素节点，形成多级索引。

跳跃表的操作* **查找：** 从最高层级开始查找，如果当前层级没有找到目标元素，则向下层级查找，直到找到目标元素或到达底层链表。 * **插入：** 首先在底层链表中插入新节点，然后根据概率决定是否将节点插入更高层级链表。 * **删除：** 首先在底层链表中删除节点，然后删除所有指向该节点的索引。

跳跃表优点* **高效的查找、插入和删除操作：** 跳跃表可以在平均 O(log n) 时间内完成这些操作，比平衡树稍微慢一些，但比链表快得多。 * **易于实现：** 与平衡树相比，跳跃表的实现相对简单。 * **空间效率：** 跳跃表的空间效率较高，因为它只存储指向其他节点的指针，而不是整个数据。

跳跃表缺点* **空间开销：** 与简单的链表相比，跳跃表需要额外的空间来存储索引。 * **随机访问：** 跳跃表不支持随机访问元素，需要从头开始遍历。

Zset 的实现Zset 使用跳跃表来存储元素和分数，并使用哈希表来存储元素的索引。* **跳跃表：** 存储元素和分数，并根据分数进行排序。 * **哈希表：** 存储元素的索引，用于快速查找元素。当执行 Zset 操作时，Redis 会根据需要使用跳跃表和哈希表来完成操作。

总结Zset 使用跳跃表作为底层数据结构，它可以高效地实现有序集合的操作。跳跃表是一种概率性数据结构，它在空间效率和查找效率之间取得平衡。Redis 使用跳跃表和哈希表来实现 Zset，提供高效的存储和查询功能。