redis 从0到1完整学习 (九):SkipList 数据结构

2023-12-27 11:59:45


1. 引言

前情提要:
《redis 从0到1完整学习 (一):安装&初识 redis》
《redis 从0到1完整学习 (二):redis 常用命令》
《redis 从0到1完整学习 (三):redis 数据结构》
《redis 从0到1完整学习 (四):字符串 SDS 数据结构》
《redis 从0到1完整学习 (五):集合 IntSet 数据结构》
《redis 从0到1完整学习 (六):Hash 表数据结构》
《redis 从0到1完整学习 (七):ZipList 数据结构》
《redis 从0到1完整学习 (八):QuickList 数据结构》

本文主要结合源码来介绍 SkipList 的数据结构

2. redis 源码下载

Redis 源码可以点击这里下载,方便查看其中定义的一些数据结构。
在这里插入图片描述

3. skipList 数据结构

跳跃表(SkipList)是一种有序数结构,它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。

Redis 使用 skipList 作为有序集合键的底层实现之一,如果一个有序集合包含的元素数量比较多,又或者有序集合中元素的成员是比较长的字符串时,Redis 就会使用 skipList 来为有序集合键的底层实现。

如图是 skipList 的示意图,本质上是用空间换时间,跳表详细的可以参考这里

在这里插入图片描述

数据结构如下:
在这里插入图片描述

  • skipList 是一个双向链表,每个节点都包含 score和 ele 值
  • 节点按照 score 值排序,score 值一样则按照 ele 字典排序
  • 层级越高,节点的跨度越大

结合上面数据结构,Redis 的 skipList 组织如下:
在这里插入图片描述

4. 参考

《redis 从0到1完整学习 (一):安装&初识 redis》
《redis 从0到1完整学习 (二):redis 常用命令》
《redis 从0到1完整学习 (三):redis 数据结构》
《redis 从0到1完整学习 (四):字符串 SDS 数据结构》
《redis 从0到1完整学习 (五):集合 IntSet 数据结构》
《redis 从0到1完整学习 (六):Hash 表数据结构》
《redis 从0到1完整学习 (七):ZipList 数据结构》
《redis 从0到1完整学习 (八):QuickList 数据结构》

文章来源:https://blog.csdn.net/qq_36803941/article/details/135225919
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。