Redis入门到通关之数据结构解析-SkipList

☃️概述

SkipList（跳表）是一种数据结构，用于实现有序元素的动态集合，它的设计目的是在有序链表的基础上通过增加多级索引来提高查找效率。

跳表的核心思想是在原始链表的基础上建立多层索引，每一层索引都是原始链表的子集，其中每个节点都具有指向下一层的指针。这样，从头节点到尾节点的路径形成了一种类似跳跃的结构，使得在搜索时可以跳过一些节点，从而减少了搜索的时间复杂度。

SkipList（跳表）首先是链表，但与传统链表相比有几点差异：
元素按照升序排列存储
节点可能包含多个指针，指针跨度不同。

SkipList（跳表）首先是链表，但与传统链表相比有几点差异：
元素按照升序排列存储
节点可能包含多个指针，指针跨度不同。

SkipList（跳表）首先是链表，但与传统链表相比有几点差异：
元素按照升序排列存储
节点可能包含多个指针，指针跨度不同。

☃️总结

跳表的特点和优势包括：

快速查找: 跳表通过多级索引实现了快速的查找操作，平均情况下的时间复杂度为O(log n)，与二分查找类似。

动态更新: 跳表支持动态插入和删除操作，而且相比于平衡树等数据结构，其实现相对简单。

简单高效: 跳表的实现相对简单，不需要复杂的平衡操作，而且在实际应用中通常可以获得较好的性能。

空间效率: 跳表通过增加索引层的方式来提高查找效率，相比于红黑树等平衡树，其空间复杂度更低。

SkipList的特点：

• 跳跃表是一个双向链表，每个节点都包含score和ele值
• 节点按照score值排序，score值一样则按照ele字典排序
• 每个节点都可以包含多层指针，层数是1到32之间的随机数
• 不同层指针到下一个节点的跨度不同，层级越高，跨度越大
• 增删改查效率与红黑树基本一致，实现却更简单

跳表在实际应用中被广泛使用，特别是在需要高效查找和动态更新有序元素集合的场景下，例如Redis中的有序集合（Sorted Set）就是通过跳表实现的。跳表的设计理念简单而有效，使得它成为了数据结构领域中的一个重要成员。