ZSet的底层实现原理

女爷i 2024-03-25 09:59 83阅读 0赞

#### 文章目录 ####

*   *   *   *  1、zset底层数据结构？简单说说跳表底层数据结构？
             *  2、什么时候采用压缩列表、什么时候采用跳表？
             *  3、跳表的时间复杂度？
             *  4、简单描述一下跳表如何查找某个元素
             *  5、zset为什么用跳表而不用二叉树或者红黑树？
             *  6、zset的底层实现

--------------------

##### 1、zset底层数据结构？简单说说跳表底层数据结构？ #####

**zset**数据结构是压缩列表； **跳表**：在链表的基础上，增加了多级索引，通过多级索引位置的转跳，实现了快速查找元素。

![image-20230302195118071][]

##### 2、什么时候采用压缩列表、什么时候采用跳表？ #####

①有序集合保存的元素数量小于128个

②有序集合保存的所有元素的长度小于64字节

以上两种情况采用压缩列表

##### 3、跳表的时间复杂度？ #####

跳表：O（logN） 普通链表：O（N）

##### 4、简单描述一下跳表如何查找某个元素 #####

跳表是一种支持快速查找、插入和删除的数据结构，其查询时间复杂度为O(log n)。

在跳表中，每个节点都有多个指针，指向同一列中的其他节点。这些指针被称为“跳跃指针”，用于快速遍历跳表。

要查找某个元素，可以从跳表的顶部开始遍历，沿着每个节点的跳跃指针向下移动，直到找到大于或等于目标元素的节点。然后，从该节点开始沿着普通指针向右移动，直到找到目标元素或到达链表的末尾。

如果跳表中不存在目标元素，则遍历将结束并返回空值。

由于跳表中每个节点都有多个跳跃指针，因此每个节点的平均跳跃长度较长，可以在O(log n)的时间内遍历跳表。这种快速查找的能力使得跳表在实际应用中得到广泛使用，如Redis等一些缓存系统中。

![image-20230302202043904][]

##### 5、zset为什么用跳表而不用二叉树或者红黑树？ #####

跳表支持范围查找：跳表的效率比红黑树高，并且实现起来也简单

##### 6、zset的底层实现 #####

在Redis中，Zset（有序集合）是一种有序的、非重复的数据结构。它的底层实现是一种称为“跳跃表”（Skip List）的数据结构，它是一种随机化数据结构，能够快速地支持插入、删除、查找操作，并且具有可预测的性能。

跳跃表由多个层级组成，每个层级都是一个有序链表。在一个有序链表中，每个节点包含一个值和一个指向下一个节点的指针。在跳跃表中，每个节点也包含多个指向下一层节点的指针。这些指针是随机生成的，因此跳跃表的层数是随机的，但通常情况下不会超过log(N)层，其中N是跳跃表中元素的个数。

为了实现有序性，跳跃表中每个节点都包含一个分值，它用来对节点进行排序。在Redis中，Zset中的每个元素都是一个键值对，其中键是元素的值，值是元素的分值。跳跃表中的节点通过分值进行排序，这样就可以实现有序集合。

在Redis中，Zset还有一个叫做“字典”的数据结构，它用来保存元素值和元素分值之间的映射关系。字典使用哈希表实现，可以快速地根据元素值查找元素分值。这样，在对Zset进行查找、插入、删除等操作时，可以同时使用跳跃表和字典来实现高效的操作。

总的来说，Zset底层的实现是一种高效的、随机化的数据结构，能够支持有序集合的各种操作，并且具有可预测的性能。

[image-20230302195118071]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/48ec21991aba40fea53232469e2c6402.png
[image-20230302202043904]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/aa13121674ad4d35a1509b38cd8fbeed.png