一、简介
Redis中所有的的数据结构都是通过一个唯一的字符串key来获取相应的value数据。
Redis有5种基础数据结构，分别是：
string（字符串）
list（列表）
hash（字典）
set（集合）
zset（有序集合）
其中list、set、hash、zset这四种数据结构是容器型数据结构，它们共享下面两条通用规则：
create if not exists：容器不存在则创建
drop if no elements：如果容器中没有元素，则立即删除容器，释放内存
本文将详细讲述的是Redis的5种基础数据结构。
二、string（字符串）
1、string(字符串)相关介绍
1.1 string(字符串)的内部结构
string(字符串)是Redis最简单也是使用最广泛的数据结构，它的内部是一个字符数组。如图所示：
1.2 string(字符串)的扩容
当string(字符串)的大小达到扩容阈值时，将会对string(字符串)进行扩容，string(字符串)的扩容主要有以下几个点：
长度小于1MB，扩容后为原先的两倍; length = length * 2
长度大于1MB，扩容后增加1MB; length = length + 1MB
字符串的长度最大值为 512MB
2、string(字符串)的指令
2.1 单个键值对增删改查操作
set -> key 不存在则新增，存在则修改
set key value
get -> 查询，返回对应key的value，不存在返回(nil)
get key
del -> 删除指定的key(key可以是多个)
del key [key …]
示例：
2.2 批量键值对
批量键值读取和写入最大的优势在于节省网络传输开销
mset -> 批量插入
mset key value [key value …]
mget -> 批量获取
mget key [key …]
示例：
三、list（列表）
1、list(列表)相关介绍
1.1 list(列表)的内部结构
Redis的列表相当于Java语言中的LinkedList，它是一个双向链表数据结构（但是这个结构设计比较巧妙，后面会介绍），支持前后顺序遍历。链表结构插入和删除操作快，时间复杂度O(1)，查询慢，时间复杂度O(n)。
————————————————
版权声明：本文为CSDN博主「李子捌」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_41125219/article/details/118559762
2、list(列表)的指令
2.1 右进左出—队列
队列在结构上是先进先出（FIFO）的数据结构（比如排队购票的顺序），常用于消息队列类似的功能，例如消息排队、异步处理等场景。通过它可以确保元素的访问顺序。
lpush -> 从左边边添加元素
lpush key value [value …]
rpush -> 从右边添加元素
rpush key value [value …]
llen -> 获取列表的长度
llen key
lpop -> 从左边弹出元素
lpop key
2.2 右进右出——栈
栈在结构上是先进后出（FILO）的数据结构（比如弹夹压入子弹，子弹被射击出去的顺序就是栈），这种数据结构一般用来逆序输出。
lpush -> 从左边边添加元素
lpush key value [value …]
rpush -> 从右边添加元素
rpush key value [value …]
rpop -> 从右边弹出元素
rpop code
2.3 慢操作
列表(list)是个链表数据结构，它的遍历是慢操作，所以涉及到遍历的性能将会遍历区间range的增大而增大。注意list的索引运行为负数，-1代表倒数第一个，-2代表倒数第二个，其它同理。
lindex -> 遍历获取列表指定索引处的值
lindex key ind
lrange -> 获取从索引start到stop处的全部值
lrange key start stop
ltrim -> 截取索引start到stop处的全部值，其它将会被删除
ltrim key start stop
3、list(列表)深入理解
Redis底层存储list(列表)不是一个简单的LinkedList，而是quicklist ——“快速列表”。关于quicklist是什么，下面会简单介绍，具体源码我也还在学习中，后面大家一起探讨。
quicklist是多个ziplist(压缩列表)组成的双向列表；而这个ziplist(压缩列表)又是什么呢？ziplist指的是一块连续的内存存储空间，Redis底层对于list(列表)的存储，当元素个数少的时候，它会使用一块连续的内存空间来存储，这样可以减少每个元素增加prev和next指针带来的内存消耗，最重要的是可以减少内存碎片化问题。
3.1 常见的链表结构示意图
每个node节点元素，都会持有一个prev->执行前一个node节点和next->指向后一个node节点的指针（引用），这种结构虽然支持前后顺序遍历，但是也带来了不小的内存开销，如果node节点仅仅是一个int类型的值，那么可想而知，引用的内存比例将会更大。
1.3 hash(字典)的相关使用场景
hash(字典)可以用来存储对象的相关信息，一个hash(字典)代表一个对象，hash的一个key代表对象的一个属性，key的值代表属性的值。hash(字典)结构相比字符串来说，它无需将整个对象进行序列化后进行存储。这样在获取的时候可以进行部分获取。所以相比之下hash(字典)具有如下的优缺点：
读取可以部分读取，节省网络流量
存储消耗的高于单个字符串的存储
2 hash(字典)相关指令
2.1 hash(字典)常用指令
hset -> hash(字典)插入值，字典不存在则创建 key代表字典名称，field 相当于 key，value是key的值
hset key field value
hmset -> 批量设值
hmset key field value [field value …]
示例：
五、set（集合）
1、set(集合)相关介绍
1.1 set(集合)的内部结构
Redis的set(集合)相当于Java语言里的HashSet，它内部的键值对是无序的、唯一的。它的内部实现了一个所有value为null的特殊字典。
集合中的最后一个元素被移除之后，数据结构被自动删除，内存被回收。
六、zset（有序集合）
1、zset(有序集合)相关介绍
1.1 zset(有序集合)的内部结构
zset(有序集合)是Redis中最常问的数据结构。它类似于Java语言中的SortedSet和HashMap的结合体，它一方面通过set来保证内部value值的唯一性，另一方面通过value的score（权重）来进行排序。这个排序的功能是通过Skip List（跳跃列表）来实现的。
zset(有序集合)的最后一个元素value被移除后，数据结构被自动删除，内存被回收。
1.2 zset(有序集合)的相关使用场景
利用zset的去重和有序的效果可以由很多使用场景，举两个例子：
存储粉丝列表，value是粉丝的ID，score是关注时间戳，这样可以对粉丝关注进行排序
存储学生成绩，value使学生的ID，score是学生的成绩，这样可以对学生的成绩排名
2、zset(有序集合)相关指令
1、zadd -> 向集合中添加元素，集合不存在则新建，key代表zset集合名称，score代表元素的权重，member代表元素
zadd key [NX|XX] [CH] [INCR] score member [score member …]
2、zrange -> 按照score权重从小到大排序输出集合中的元素，权重相同则按照value的字典顺序排序([lexicographical order])
超出范围的下标并不会引起错误。 比如说，当 start 的值比有序集的最大下标还要大，或是 start > stop 时， zrange 命令只是简单地返回一个空列表。 另一方面，假如 stop 参数的值比有序集的最大下标还要大，那么 Redis 将 stop 当作最大下标来处理。
可以通过使用 WITHSCORES 选项，来让成员和它的 score 值一并返回，返回列表以 value1,score1, …, valueN,scoreN 的格式表示。 客户端库可能会返回一些更复杂的数据类型，比如数组、元组等。
zrange key start stop [WITHSCORES]
七、Skip List
1、简介
跳表全称叫做跳跃表，简称跳表。跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。
Skip List(跳跃列表)这种随机的数据结构，可以看做是一个二叉树的变种，它在性能上与红黑树、AVL树很相近；但是Skip List(跳跃列表)的实现相比前两者要简单很多，目前Redis的zset实现采用了Skip List(跳跃列表)（其它还有LevelDB等也使用了跳跃列表）。
RBT红黑树与Skip List(跳跃列表)简单对比：
RBT红黑树
插入、查询时间复杂度O(logn)
数据天然有序
实现复杂，设计变色、左旋右旋平衡等操作
需要加锁
Skip List跳跃列表
插入、查询时间复杂度O(logn)
数据天然有序
实现简单，链表结构
无需加锁
2、Skip List算法分析
2.1 Skip List论文
这里贴出Skip List的论文，需要详细研究的请看论文，下文部分公式、代码、图片出自该论文。
Skip Lists: A Probabilistic Alternative to Balanced Trees
https://www.cl.cam.ac.uk/teaching/2005/Algorithms/skiplists.pdf
2.2 Skip List动态图
先通过一张动图来了解Skip List的插入节点元素的流程，此图来自维基百科。
2.3 Skip List算法性能分析
2.3.1 计算随机层数算法
首先分析的是执行插入操作时计算随机数的过程，这个过程会涉及层数的计算，所以十分重要。对于节点他有如下特性：
节点都有第一层的指针
节点有第i层指针，那么第i+1层出现的概率为p
节点有最大层数限制，MaxLevel
计算随机层数的伪代码：
论文中的示例
2.3.2 节点包含的平均指针数目
Skip List属于空间换时间的数据结构，这里的空间指的就是每个节点包含的指针数目，这一部分是额外的内内存开销，可以用来度量空间复杂度。random()是个随机数，因此产生越高的节点层数，概率越低（Redis标准源码中的晋升率数据1/4，相对来说Skip List的结构是比较扁平的，层高相对较低）。其定量分析如下：
level = 1 概率为1-p
level >=2 概率为p
level = 2 概率为p(1-p)
level >= 3 概率为p^2
level = 3 概率为p^2(1-p)
level >=4 概率为p^3
level = 4 概率为p^3(1-p)
……
得出节点的平均层数（节点包含的平均指针数目）：
所以Redis中p=1/4计算的平均指针数目为1.33
2.3.3 时间复杂度计算
以下推算来自论文内容
假设p=1/2，在以p=1/2生成的16个元素的跳过列表中，我们可能碰巧具有9个元素，1级3个元素，3个元素3级元素和1个元素14级（这不太可能，但可能会发生）。我们该怎么处理这种情况？如果我们使用标准算法并在第14级开始我们的搜索，我们将会做很多无用的工作。那么我们应该从哪里开始搜索？此时我们假设SkipList中有n个元素，第L层级元素个数的期望是1/p个；每个元素出现在L层的概率是p^(L-1), 那么第L层级元素个数的期望是 n * (p^L-1)；得到1 / p =n * (p^L-1)
所以我们应该选择MaxLevel = log(1/p)^n
定义：MaxLevel = L(n) = log(1/p)^n
推算Skip List的时间复杂度，可以用逆向思维，从层数为i的节点x出发，返回起点的方式来回溯时间复杂度，节点x点存在两种情况：
节点x存在(i+1)层指针，那么向上爬一级，概率为p，对应下图situation c.
节点x不存在(i+1)层指针，那么向左爬一级，概率为1-p，对应下图situation b.
上面推演的结果可知，爬升k个level的预期长度为k/p，爬升一个level的长度为1/p。
由于MaxLevel = L(n)， C(k) = k / p，因此期望值为：(L(n) – 1) / p；将L(n) = log(1/p)^n 代入可得：(log(1/p)^n - 1) / p；将p = 1 / 2 代入可得：2 * log2^n - 2，即O(logn)的时间复杂度。
3、Skip List特性及其实现
2.1 Skip List特性
Skip List跳跃列表通常具有如下这些特性
Skip List包含多个层，每层称为一个level，level从0开始递增
Skip List 0层，也就是最底层，应该包含所有的元素
每一个level/层都是一个有序的列表
level小的层包含level大的层的元素，也就是说元素A在X层出现，那么 想X>Z>=0的level/层都应该包含元素A
每个节点元素由节点key、节点value和指向当前节点所在level的指针数组组成
2.2 Skip List查询
假设初始Skip List跳跃列表中已经存在这些元素，他们分布的结构如下所示：
从Skip List跳跃列表最顶层level3开始，往后查询到10 < 88 && 后续节点值为null && 存在下层level2
level2 10往后遍历，27 < 88 && 后续节点值为null && 存在下层level1
level1 27往后遍历，88 = 88，查询命中
2.3 Skip List插入
Skip List的初始结构与2.3中的初始结构一致，此时假设插入的新节点元素值为90，插入路线如下所示：
查询插入位置，与Skip List查询方式一致，这里需要查询的是第一个比90大的节点位置，插入在这个节点的前面， 88 < 90 < 100
构造一个新的节点Node(90)，为插入的节点Node(90)计算一个随机level，这里假设计算的是1，这个level时随机计算的，可能时1、2、3、4…均有可能，level越大的可能越小，主要看随机因子x ，层数的概率大致计算为 (1/x)^level ，如果level大于当前的最大level3，需要新增head和tail节点
节点构造完毕后，需要将其插入列表中，插入十分简单步骤 -> Node(88).next = Node(90); Node(90).prev = Node(80); Node(90).next = Node(100); Node(100).prev = Node(90);
2.4 Skip List删除
删除的流程就是查询到节点，然后删除，重新将删除节点左右两边的节点以链表的形式组合起来即可，这里不再画图
4、手写实现一个简单Skip List
实现一个Skip List比较简单，主要分为两个步骤：
定义Skip List的节点Node，节点之间以链表的形式存储，因此节点持有相邻节点的指针，其中prev与next是同一level的前后节点的指针，down与up是同一节点的多个level的上下节点的指针
定义Skip List的实现类，包含节点的插入、删除、查询，其中查询操作分为升序查询和降序查询（往后和往前查询），这里实现的Skip List默认节点之间的元素是升序链表
3.1 定义Node节点
Node节点类主要包括如下重要属性：
score -> 节点的权重，这个与Redis中的score相同，用来节点元素的排序作用
value -> 节点存储的真实数据，只能存储String类型的数据
prev -> 当前节点的前驱节点，同一level
next -> 当前节点的后继节点，同一level
down -> 当前节点的下层节点，同一节点的不同level
up -> 当前节点的上层节点，同一节点的不同level
3.2 SkipList节点元素的操作类
SkipList主要包括如下重要属性：
head -> SkipList中的头节点的最上层头节点（level最大的层的头节点），这个节点不存储元素，是为了构建列表和查询时做查询起始位置的，具体的结构请看2.3中的结构
tail -> SkipList中的尾节点的最上层尾节点（level最大的层的尾节点），这个节点也不存储元素，是查询某一个level的终止标志
level -> 总层数
size -> Skip List中节点元素的个数
random -> 用于随机计算节点level，如果 random.nextDouble() < 1/2则需要增加当前节点的level，如果当前节点增加的level超过了总的level则需要增加head和tail(总level)
1package com.liziba.skiplist; 2 3import java.util.Random; 4 5/** 6 * <p> 7 * 跳表实现 8 * </p> 9 * 10 * @Author: Liziba 11 */ 12public class SkipList { 13 14 /** 最上层头节点 */ 15 public Node head; 16 /** 最上层尾节点 */ 17 public Node tail; 18 /** 总层数 */ 19 public int level; 20 /** 元素个数 */ 21 public int size; 22 public Random random; 23 24 public SkipList() { 25 level = size = 0; 26 head = new Node(null); 27 tail = new Node(null); 28 head.next = tail; 29 tail.prev = head; 30 } 31 32 /** 33 * 查询插入节点的前驱节点位置 34 * 35 * @param score 36 * @return 37 */ 38 public Node fidePervNode(Double score) { 39 Node p = head; 40 for(;;) { 41 // 当前层(level)往后遍历，比较score，如果小于当前值，则往后遍历 42 while (p.next.value == null && p.prev.score <= score) 43 p = p.next; 44 // 遍历最右节点的下一层(level) 45 if (p.down != null) 46 p = p.down; 47 else 48 break; 49 } 50 return p; 51 } 52 53 /** 54 * 插入节点，插入位置为fidePervNode(Double score)前面 55 * 56 * @param score 57 * @param value 58 */ 59 public void insert(Double score, String value) { 60 61 // 当前节点的前置节点 62 Node preNode = fidePervNode(score); 63 // 当前新插入的节点 64 Node curNode = new Node(score, value); 65 // 分数和值均相等则直接返回 66 if (curNode.value != null && preNode.value != null && preNode.value.equals(curNode.value) 67 && curNode.score.equals(preNode.score)) { 68 return; 69 } 70 71 preNode.next = curNode; 72 preNode.next.prev = curNode; 73 curNode.next = preNode.next; 74 curNode.prev = preNode; 75 76 int curLevel = 0; 77 while (random.nextDouble() < 1/2) { 78 // 插入节点层数(level)大于等于层数(level)，则新增一层(level) 79 if (curLevel >= level) { 80 Node newHead = new Node(null); 81 Node newTail = new Node(null); 82 newHead.next = newTail; 83 newHead.down = head; 84 newTail.prev = newHead; 85 newTail.down = tail; 86 head.up = newHead; 87 tail.up = newTail; 88 // 头尾节点指针修改为新的，确保head、tail指针一直是最上层的头尾节点 89 head = newHead; 90 tail = newTail; 91 ++level; 92 } 93 94 while (preNode.up == null) 95 preNode = preNode.prev; 96 97 preNode = preNode.up; 98 99 Node copy = new Node(null); 100 copy.prev = preNode; 101 copy.next = preNode.next; 102 preNode.next.prev = copy; 103 preNode.next = copy; 104 copy.down = curNode; 105 curNode.up = copy; 106 curNode = copy; 107 108 ++curLevel; 109 } 110 ++size; 111 } 112 113 /** 114 * 查询指定score的节点元素 115 * @param score 116 * @return 117 */ 118 public Node search(double score) { 119 Node p = head; 120 for (;;) { 121 while (p.next.score != null && p.next.score <= score) 122 p = p.next; 123 if (p.down != null) 124 p = p.down; 125 else // 遍历到最底层 126 if (p.score.equals(score)) 127 return p; 128 return null; 129 } 130 } 131 132 /** 133 * 升序输出Skip List中的元素 （默认升序存储，因此从列表head往tail遍历） 134 */ 135 public void dumpAllAsc() { 136 Node p = head; 137 while (p.down != null) { 138 p = p.down; 139 } 140 while (p.next.score != null) { 141 System.out.println(p.next.score + "-->" + p.next.value); 142 p = p.next; 143 } 144 } 145 146 /** 147 * 降序输出Skip List中的元素 148 */ 149 public void dumpAllDesc() { 150 Node p = tail; 151 while (p.down != null) { 152 p = p.down; 153 } 154 while (p.prev.score != null) { 155 System.out.println(p.prev.score + "-->" + p.prev.value); 156 p = p.prev; 157 } 158 } 159 160 161 /** 162 * 删除Skip List中的节点元素 163 * @param score 164 */ 165 public void delete(Double score) { 166 Node p = search(score); 167 while (p != null) { 168 p.prev.next = p.next; 169 p.next.prev = p.prev; 170 p = p.up; 171 } 172 } 173}
