redis中的跳表结构

redis的有序集合zset数据结构底层采用了跳表原理 时间复杂度O(logn)(阿里)

redis使用跳表不用B&＃43;数的原因是&＃xff1a;redis是内存数据库&＃xff0c;而B&＃43;树纯粹是为了mysql这种IO数据库准备的。B&＃43;树的每个节点的数量都是一个mysql分区页的大小(阿里面试)

敲黑板&＃xff1a;

每级遍历 3 个结点即可&＃xff0c;而跳表的高度为 h &＃xff0c;所以每次查找一个结点时&＃xff0c;需要遍历的结点数为 3*跳表高度 &＃xff0c;所以忽略低阶项和系数后的时间复杂度就是 ○(㏒n),空间复杂度是O(n)

问题

如果对以下问题感到困惑或一知半解&＃xff0c;请继续看下去&＃xff0c;相信本文一定会对你有帮助

• mysql 索引如何实现
• mysql 索引结构B&＃43;树与hash有何区别。分别适用于什么场景
• 数据库的索引还能有其他实现吗
• redis跳表是如何实现的
• 跳表和B&＃43;树&＃xff0c;LSM树有何区别呢

解析

首先为什么要把mysql索引和redis跳表放在一起讨论呢&＃xff0c;因为他们解决的都是同一种问题&＃xff0c;用于解决数据集合的查找问题&＃xff0c;即根据指定的key&＃xff0c;快速查到它所在的位置&＃xff08;或者对应的value&＃xff09;

当你站在这个角度去思考问题时&＃xff0c;还会不知道B&＃43;树索引和hash索引的区别吗

数据集合的查找问题

现在我们将问题领域边界划分清楚了&＃xff0c;就是为了解决数据集合的查找问题。这一块需要考虑哪些问题呢

1. 需要支持哪些查找方式&＃xff0c;单key/多key/范围查找&＃xff0c;
2. 插入/删除效率
3. 查找效率&＃xff08;即时间复杂度&＃xff09;
4. 存储大小&＃xff08;空间复杂度&＃xff09;

我们看下几种常用的查找结构

hash

hash是key,value形式&＃xff0c;通过一个散列函数&＃xff0c;能够根据key快速找到value

B&＃43; 树&＃xff1a;

注意 这是关于B&＃43;树的总结&＃xff0c;如果你掌握到这个程度 是远远不够的&＃xff0c;

B&＃43;树 的数据都在叶子节点&＃xff0c;非叶子节点存放 索引

B&＃43;树是在平衡二叉树基础上演变过来&＃xff0c;为什么我们在算法课上没学到B&＃43;树和跳表这种结构呢。因为他们都是从工程实践中得到&＃xff0c;在理论的基础上进行了妥协。

B&＃43;树首先是有序结构&＃xff0c;为了不至于树的高度太高&＃xff0c;影响查找效率&＃xff0c;在叶子节点上存储的不是单个数据&＃xff0c;而是一页数据&＃xff0c;提高了查找效率&＃xff0c;而为了更好的支持范围查询&＃xff0c;B&＃43;树在叶子节点冗余了非叶子节点数据&＃xff0c;为了支持翻页&＃xff0c;叶子节点之间通过指针连接。

跳表

redis跳表视频讲解点击链接&＃xff1a;redis跳表

跳表&＃xff1a;为什么 Redis 一定要用跳表来实现有序集合&＃xff1f;

上几篇主要是学习二分查找算法&＃xff0c;但是二分查找底层依赖的是数组随机访问的特性&＃xff0c;所以只能用数组来实现。如果数据存储在链表中&＃xff0c;就没办法使用二分查找了吗&＃xff1f;

此时跳表出现了&＃xff0c;跳表&＃xff08;Skip list&＃xff09; 实际上就是在链表的基础上改造生成的。

跳表是一种各方面性能都比较优秀的 动态数据结构&＃xff0c;可以支持快速的插入、删除、查找操作&＃xff0c;写起来也不复杂&＃xff0c;甚至可以替代 红黑树&＃xff1f;&＃xff1f;。

Redis 一共有5种数据结构&＃xff0c;包括&＃xff1a;

1、字符串(String)
redis对于KV的操作效率很高&＃xff0c;可以直接用作计数器。例如&＃xff0c;统计在线人数等等&＃xff0c;另外string类型是二进制存储安全的&＃xff0c;所以也可以使用它来存储图片&＃xff0c;甚至是视频等。

2、哈希(hash)
存放键值对&＃xff0c;一般可以用来存某个对象的基本属性信息&＃xff0c;例如&＃xff0c;用户信息&＃xff0c;商品信息等&＃xff0c;另外&＃xff0c;由于hash的大小在小于配置的大小的时候使用的是ziplist结构&＃xff0c;比较节约内存&＃xff0c;所以针对大量的数据存储可以考虑使用hash来分段存储来达到压缩数据量&＃xff0c;节约内存的目的&＃xff0c;例如&＃xff0c;对于大批量的商品对应的图片地址名称。比如&＃xff1a;商品编码固定是10位&＃xff0c;可以选取前7位作为hash的key,后三位作为field&＃xff0c;图片地址作为value。这样每个hash表都不超过999个&＃xff0c;只要把redis.conf中的hash-max-ziplist-entries改为1024&＃xff0c;即可。
3、列表(List)
列表类型&＃xff0c;可以用于实现消息队列&＃xff0c;也可以使用它提供的range命令&＃xff0c;做分页查询功能。

4、集合(Set)
集合&＃xff0c;整数的有序列表可以直接使用set。可以用作某些去重功能&＃xff0c;例如用户名不能重复等&＃xff0c;另外&＃xff0c;还可以对集合进行交集&＃xff0c;并集操作&＃xff0c;来查找某些元素的共同点

5、有序集合(zset)
有序集合&＃xff0c;可以使用范围查找&＃xff0c;排行榜功能或者topN功能。

其中第五个zset 有序集合 就是用跳表来实现的。那 Redis 为什么会选择用跳表来实现有序集合呢&＃xff1f;

一、如何理解跳表&＃xff1f;

对于单链表来说&＃xff0c;我们查找某个数据&＃xff0c;只能从头到尾遍历链表&＃xff0c;此时时间复杂度是 ○(n)。

那么怎么提高单链表的查找效率呢&＃xff1f;看下图&＃xff0c;对链表建立一级 索引&＃xff0c;每两个节点提取一个结点到上一级&＃xff0c;被抽出来的这级叫做 索引 或 索引层。

开发中经常会用到一种处理方式&＃xff0c;hashmap 中存储的值类型是一个 list&＃xff0c;这里就可以把索引当做 hashmap 中的键&＃xff0c;将每 2 个结点看成每个键对应的值 list。

所以要找到13&＃xff0c;就不需要将16前的结点全遍历一遍&＃xff0c;只需要遍历索引&＃xff0c;找到13&＃xff0c;然后发现下一个结点是17&＃xff0c;那么16一定是在 [13,17] 之间的&＃xff0c;此时在13位置下降到原始链表层&＃xff0c;找到16&＃xff0c;加上一层索引后&＃xff0c;查找一个结点需要遍历的结点个数减少了&＃xff0c;也就是说查找效率提高了

那么我们再加一级索引呢&＃xff1f;
跟前面建立一级索引的方式相似&＃xff0c;我们在第一级索引的基础上&＃xff0c;每两个结点就抽出一个结点到第二级索引。此时再查找16&＃xff0c;只需要遍历 6 个结点了&＃xff0c;需要遍历的结点数量又减少了。

当结点数量多的时候&＃xff0c;这种添加索引的方式&＃xff0c;会使查询效率提高的非常明显

二、用跳表查询到底有多快

在一个单链表中&＃xff0c;查询某个数据的时间复杂度是 ○(n)&＃xff0c;那在一个具有多级索引的跳表中&＃xff0c;查询某个数据的时间复杂度是多少呢&＃xff1f;

按照上面的示例&＃xff0c;每两个节点就抽出一个一级索引&＃xff0c;每两个一级索引又抽出一个二级索引&＃xff0c;所以第一级索引的结点个数大约就是 n/2&＃xff0c;第二级索引的结点个数就是 n/4&＃xff0c;第 k 级索引的结点个数就是 n/2^k。

假设一共建立了 h 级索引&＃xff0c;最高级的索引有两个节点&＃xff08;如果最高级索引只有一个结点&＃xff0c;那么这一级索引起不到判断区间的作用&＃xff0c;那么是没什么意义的&＃xff09;&＃xff0c;所以有&＃xff1a;

时间复杂度的分析

根据上图得知&＃xff0c;每级遍历 3 个结点即可&＃xff0c;而跳表的高度为 h &＃xff0c;所以每次查找一个结点时&＃xff0c;需要遍历的结点数为 3*跳表高度 &＃xff0c;所以忽略低阶项和系数后的时间复杂度就是 ○(㏒n)

其实此时就相当于基于单链表实现了二分查找。但是这种查询效率的提升&＃xff0c;由于建立了很多级索引&＃xff0c;会不会很浪费内存呢&＃xff1f;

三、跳表是不是很浪费内存&＃xff1f;

来分析一下跳表的空间复杂度。 为O(n)

空间复杂度

所以如果将包含 n 个结点的单链表构造成跳表&＃xff0c;我们需要额外再用接近 n 个结点的存储空间&＃xff0c;那怎么才能降低索引占用的内存空间呢&＃xff1f;

前面是每两个结点抽一个结点到上级索引&＃xff0c;如果我们每三个&＃xff0c;或每五个结点&＃xff0c;抽一个结点到上级索引&＃xff0c;是不是就不用那么多索引结点了呢&＃xff1f;

计算空间复杂度的过程与前面的一致&＃xff0c;尽管最后空间复杂度依然是 ○(n)&＃xff0c;但我们知道&＃xff0c;使用大○表示法忽略的低阶项或系数&＃xff0c;实际上同样会产生影响&＃xff0c;只不过我们为了关注高阶项而将它们忽略。

空间复杂度

实际上&＃xff0c;在实际开发中&＃xff0c;我们不需要太在意索引占据的额外空间&＃xff0c;在学习数据结构与算法时&＃xff0c;我们习惯的将待处理数据看成整数&＃xff0c;但是实际开发中&＃xff0c;原始链表中存储的很可能是很大的对象&＃xff0c;而索引结点只需要存储关键值&＃xff08;用来比较的值&＃xff09;和几个指针&＃xff08;找到下级索引的指针&＃xff09;&＃xff0c;并不需要存储原始链表中完整的对象&＃xff0c;所以当对象比索引结点大很多时&＃xff0c;那索引占用的额外空间就可以忽略了。

四、高效的动态插入和删除

跳表这个动态数据结构&＃xff0c;不仅支持查找操作&＃xff0c;还支持动态的插入、删除操作&＃xff0c;而且插入、删除操作的时间复杂度也是 ○(㏒n)。

对于单纯的单链表&＃xff0c;需要遍历每个结点来找到插入的位置。但是对于跳表来说&＃xff0c;因为其查找某个结点的时间复杂度是 ○(㏒n)&＃xff0c;所以这里查找某个数据应该插入的位置&＃xff0c;时间复杂度也是 ○(㏒n)。

那么删除操作呢&＃xff1f;

五、跳表索引动态更新

当我们不停的往跳表中插入数据时&＃xff0c;如果我们不更新索引&＃xff0c;就可能出现某 2 个索引结点之间数据非常多的情况。极端情况下&＃xff0c;跳表会退化成单链表。

作为一种动态数据结构&＃xff0c;我们需要某种手段来维护索引与原始链表大小之间的平滑&＃xff0c;也就是说如果链表中结点多了&＃xff0c;索引结点就相应地增加一些&＃xff0c;避免复杂度退化&＃xff0c;以及查找、插入、删除操作性能下降。

跳表是通过随机函数来维护前面提到的 平衡性。

我们往跳表中插入数据的时候&＃xff0c;可以选择同时将这个数据插入到第几级索引中&＃xff0c;比如随机函数生成了值 K&＃xff0c;那我们就将这个结点添加到第一级到第 K 级这 K 级索引中。

随机函数可以保证跳表的索引大小和数据大小的平衡性&＃xff0c;不至于性能过度退化。

跳表的实现有点复杂&＃xff0c;并且跳表的实现并不是这篇的重点。主要是学习思路。

六、解答开篇

Redis 中的有序集合是通过跳表来实现的&＃xff0c;严格点讲&＃xff0c;还用到了散列表&＃xff0c;如果查看 Redis 开发手册&＃xff0c;会发现 Redis 中的有序集合支持的核心操作主要有下面这几个&＃xff1a;

• 插入一个数据
• 删除一个数据
• 查找一个数据
• 按照区间查找数据&＃xff08;比如查找在[100,356]之间的数据&＃xff09;
• 迭代输出有序序列

其中&＃xff0c;插入、查找、删除以及迭代输出有序序列这几个操作&＃xff0c;红黑树也能完成&＃xff0c;时间复杂度和跳表是一样的&＃xff0c;但是&＃xff0c;按照区间来查找数据这个操作&＃xff0c;红黑树的效率没有跳表高。

对于按照区间查找数据这个操作&＃xff0c;跳表可以做到 ○(㏒n) 的时间复杂度定位区间的起点&＃xff0c;然后在原始链表中顺序往后遍历就可以了。这样做非常高效。

当然&＃xff0c;还有其他原因&＃xff0c;比如&＃xff0c;跳表代码更容易实现&＃xff0c;可读性好不易出错。跳表更加灵活&＃xff0c;可以通过改变索引构建策略&＃xff0c;有效平衡执行效率和内存消耗。

不过跳表也不能完全替代红黑树。因为红黑树出现的更早一些。很多编程语言中的 Map 类型都是用红黑树来实现的。写业务的时候直接用就行&＃xff0c;但是跳表没有现成的实现&＃xff0c;开发中想用跳表&＃xff0c;得自己实现。