什么是数据结构？

数据结构是计算机存储、组织数据的方式。
数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

1、数据的逻辑结构

指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后间关系，而与他们在计算机中的存储位置无关。逻辑结构包括：

• 集合：数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系；
• 线性结构：数据结构中的元素存在一对一的相互关系；
• 树形结构：数据结构中的元素存在一对多的相互关系；
• 图形结构：数据结构中的元素存在多对多的相互关系。

2、数据的物理结构

指数据的逻辑结构在计算机存储空间的存放形式。

数据的物理结构是数据结构在计算机中的表示（又称映像），它包括数据元素的机内表示 和 关系的机内表示。
由于具体实现的方法有顺序、链接、索引、散列等多种，所以，一种数据结构可表示成一种或多种存储结构。

数据元素的机内表示（映像方法）： 用二进制位（bit）的位串表示数据元素。通常称这种位串为节点（node）。
当数据元素有若干个数据项组成时，位串中与各个数据项对应的子位串称为数据域（data field）。
因此，节点是数据元素的机内表示（或机内映像）。

关系的机内表示（映像方法）：数据元素之间的关系的机内表示可以分为顺序映像和非顺序映像。
常用两种存储结构：顺序存储结构和链式存储结构。
顺序映像借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
非顺序映像借助指示元素存储位置的指针（pointer）来表示数据元素之间的逻辑关系。

3、数据存储结构

数据的逻辑结构在计算机存储空间中的存放形式称为数据的物理结构(也称为存储结构)。
一般来说，一种数据结构的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序存储、链式存储、索引存储和哈希存储等。

数据的顺序存储结构的特点是：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系；
非顺序存储的特点是：借助指示元素存储地址的指针表示数据元素之间的逻辑关系。

线性结构与非线性结构

一般来说，按照数据的逻辑结构对其进行简单的分类，包括线性结构和非线性结构两类。

1、线性结构

• 是一个有序数据元素的集合
• 有且仅有一个开始结点和一个终端结点，且所有结点都最多只有一个直接前驱和一个直接后继。

常用的线性结构有：数组(顺序表)，线性表，栈，队列，双队列，串。

其中静态链表是数组模拟的链式结构，数组存储下表跳转信息，建立链接逻辑。

2、非线性结构

• 非线性结构的一个结点可能有多个直接前趋结点和多个直接后继结点。

常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。

广义表（Lists，又称列表）是线性表的推广，其本质上非线性结构！

常用数据结构

一、数组( Array)

有序排列的同类数据元素的集合称为数组。

若将有限个类型相同的变量的集合命名，那么这个名称为数组名。

组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。

用于区分数组的各个元素的数字编号称为下标。

二、链表( Linked List)

链表是物理存储单元上非连续的、非顺序的存储结构。

数据元素的逻辑顺序是通过链表的指针地址实现。

每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。

根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。

1、单链表

2、双链表

3、循环链表

4、静态链表

应用场景：

1. 结合哈希表：LRU 缓存、链地址法解决哈希冲突。
2. 循环链表：约瑟夫问题

数组与链表的区别

数组	链表
数组是一个相似数据类型的数据集合	链表是一个有相同数据类型的有续集，其中每个元素使用指针链接
数组元素可以使用数组索引随机访问	链表不允许随机访问，元素只能被有序或顺序访问
数组的数据元素在内存中连续储存	元素可能存储在内存的任意地方，链表创建一个指针指向相应的数据
插入和删除操作非常耗时，时间为O(n)，因为元素的内存地址是连续和固定的	链表的插入和删除操作非常快，时间为O(1)
数组的内存是静态分配的，在编译期间完成	链表的内存分配是动态的，在运行时动态分配
数组的大小必须在数组的声明或初始化的时候指定	链表的大小随着元素的插入或删除变化

三、栈( Stack)

• 栈（stack）又称为堆栈或堆叠，栈作为一种数据结构，它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶
• java中Stack是Vector的一个子类，只定义了默认构造函数，用来创建一个空栈。
• 栈是元素的集合，其包含了两个基本操作：push 操作可以用于将元素压入栈，pop 操作可以将栈顶元素移除。
• 遵循后进先出（LIFO）原则。

应用场景：

1. 函数调用栈（栈帧），操作数栈等。
2. 单调栈：用于求比当前元素大/小的上/下一个元素（LeetCode 42、496、503、739）。
3. 递归栈：递归调用本身基于栈，也可以转换为迭代化解法（模拟函数调用栈）。
4. 树相关：前中后序遍历、直径、路径等问题。
5. 图相关：深度优先(depth-first)搜索法。
6. 计算表达式（逆波兰式）、符号匹配、浏览器前进后退等问题。

四、队列( Queue)

• 队列是元素的集合，其包含了两个基本操作：enqueue 操作可以用于将元素插入到队列中，而 dequeue 操作则是将元素从队列中移除。
• 遵循先入先出原则 (FIFO)。

1. 队列本身是有序列表，数组或链表实现，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量。
2. 因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变，如图所示:
   队列增加数据时候 rear增加；队列消费数据时候 front改变。
   

应用场景：

1. 操作系统管道通信
2. 并发容器：阻塞队列、并发队列。
3. “生产者 - 消费者”、“发布 - 订阅”模型。
4. 优先级队列：最大/小堆方法解决 topK 问题。
5. 树相关：层序遍历、高度。
6. 图相关：广度优先遍历。

五、树( Tree)

树是一种数据结构，它是由 n(n≥1) 个有限节点组成一个具有层次关系的集合。

树的特点：

• 每个节点有零个或多个子节点；
• 没有父节点的节点称为根节点；
• 每一个非根节点有且只有一个父节点；
• 除了根节点外，每个子节点可以分为多个不相交的子树

思维导图未完待补充…

六、图( Graph)

数据结构中的一个图是用G = (V, E)集合来表示的， V（vertex）是顶点集合， E(edge)是边集合。
图的相关概念如下图所示。

图的相关概念（附图）：https://blog.csdn.net/shuiyixin/article/details/83692474

1、邻接矩阵

2、邻接表

3、十字链表

4、邻接多重表

七、散列表( Hash)

1、什么是散列表？

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。

也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

给定表M，存在函数 f(key)，对任意给定的关键字值 key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数 f(key) 为哈希(Hash) 函数。

2、散列表的存储

记录的存储位置=f(key)

散列表就是把 key 通过一个固定的算法函数（哈希函数），转换成一个整型数字。

然后就将该数字对数组长度进行取余，取余结果就当作数组的下标。

将 value 存储在以该数字为下标的数组空间里。

这种存储空间可以充分利用数组的查找优势来查找元素，所以查找的速度很快。

3、哈希表在集合里的应用

哈希表在应用中也是比较常见的，就如 Java 中有些集合类就是借鉴了哈希原理构造的，例如 HashMap，HashTable 等，利用 hash表的优势，对于集合的查找元素时非常方便的。

然而，因为哈希表是基于数组衍生的数据结构，在添加删除元素方面是比较慢的，所以很多时候需要用到一种数组链表来做，也就是拉链法。

拉链法是数组结合链表的一种结构，较早前的 HashMap 底层的存储就是采用这种结构，直到 jdk1.8 之后才换成了数组加红黑树的结构，其示例图如下：

从图中可以看出，左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头。当然这个链表可能为空，也可能元素很多。

我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。

哈希表的应用场景很多，当然也有很多问题要考虑，比如哈希冲突的问题，如果处理的不好会浪费大量的时间，导致应用崩溃。

应用场景：

哈希表适用于那种查找性能要求高，数据元素之间无逻辑关系要求的情况。

1. 哈希表和位图的结合——布隆过滤器
   　　可作用于网页URL的去重，垃圾邮件的判别，集合重复元素的判别，查询加速（比如基于key-value的存储系统）等

2. 校验安装文件的完整性
   　　在软件部署的时候，计算软件包当前的哈希值是否与预设值相等，防止软件包被篡改或被替换。Linux提供了基于 sha 算法的命令，用于计算文件的哈希值 sha256sum fileName

3. 存储和校验用户口令
   　　用户口令不能用明文存储，更进一步，如果系统不知道用户口令明文，那就更好了，而哈希算法就可以做到既不知道用户明文，又可以校验用户口令。详见《基于哈希算法的web账户口令存储方法》，http://www.cnblogs.com/todsong/archive/2012/04/22/2465178.html

4. 校验重复提交的消息
   　　用户可能因为误操作重复提交数据，而这些数据会对系统产生影响，若要拒绝这些消息，最好的方法就是在每次提交时，计算消息的哈希值，当发现疑似重复提交的时候，做消息哈希值的对比。这是一个 CPU 密集型的操作，如果系统的 CPU 负载比较低，可以考虑使用。至于如何在代码中使用哈希算法，这里就不描述了，Java、C++都有现成的算法库可用。

5. 作为数据库乐观锁的条件
   　　数据库中，最常用的乐观锁方法是在表中增加额外的一列，用于记录一行数据的版本值，通常是一个计数或是时间戳。但是，一张已经存在大量数据的表需要增加额外的版本列，似乎不太可行，也不太方便，此时可以通过哈希计算出虚拟的版本列，用于乐观锁定控制。Oracle数据库提供了哈希算法的存储过程，输入某几个列数据的字符连接，输出该条记录的哈希值，通过比较该值判断数据是否被修改。下面是摘自《Oracle 9i&10g 编程艺术》的例子

6. 作为数据库表分区的分区条件
   　　如果难以按照某一个列对数据库表做分区，表中的数据又没有太多的业务逻辑，那么通过哈希函数强行分区是个不错的选择。详见《Oracle分区表，哈希分区的新建与增加》，http://www.cnblogs.com/todsong/archive/2012/08/26/2657158.htm

八、堆( Heap)

参考资料

[1] 数据结构：八大数据结构分类：
https://blog.csdn.net/yeyazhishang/article/details/82353846
[2] 数据结构：https://juejin.cn/post/6916804072485945358
[3] 408数据结构：
https://www.processon.com/view/6103b75a0e3e7423a334a3c5?fromnew=1
[4] 数据结构与算法：
https://www.processon.com/view/5cc266d7e4b08b66b9bb9579?fromnew=1
[5] 数据结构：八大数据结构分类：
https://blog.csdn.net/yeyazhishang/article/details/82353846
[6] 散列表原理与应用场景：https://blog.csdn.net/qq_39038793/article/details/103210889

1. 线性结构

内存中数据的存储形式分为连续存储和离散存储两种，分别对应了数组和链表。

数组：元素在内存中连续存储，即内存地址连续，所以查找数据效率高，但需要预先申请一块连续的内存空间，且运行期间数组大小无法动态增加减少。在插入、删除元素时效率比较低，伴随着后面元素位置的移动。

数组的应用场景：当数据量比较小，数据规模已知且需要经常访问元素时用数组更合适。

链表：动态申请 / 删除内存空间，对于元素的增删比较灵活，不需要预先知道数据规模，但无法随机查找。另外有序数组可以通过二分法来查找目标，但链表只能用顺序查找。

链表应用场景：对线性表规模难以估计，需要频繁进行插入删除操作。

2. 树结构

二叉树本质上是对数组和链表的折中。

2.1 二叉查找树

二叉查找树结合了有序数组的高效率查找和链表的高效率插入，时间复杂度为 $O(lo{g}_{2}n)$。适用于需要频繁进行查询、插入、删除操作的场景。但有可能退化成链表（此时只有左子树/右子树）此时查找和插入的最坏时间复杂度都是$O(n)$。

2.2 平衡树

为了解决二叉查找树可能会退化为链表的问题，平衡树要求任意节点的左右两个子树的高度差不超过 1。平衡树的种类包括：AVL树，红黑树，SBT，Treap，伸展树。

2.2.1 平衡二叉搜索树（AVL 树）

AVL 树 = 平衡二叉搜索树（Self-balancing binary search tree），它要么是一颗空树，要么它的左右子树的高度差的绝对值不超过 1，且左右子树也满足以上性质。和红黑树相比，它是严格的平衡二叉树。在对 AVL 树进行插入或删除节点时，只要不满足平衡的性质就要通过旋转来保持平衡，比较耗时。

【应用场景】 适合插入删除操作都比较少、查找多的情况，AVL 保证了树深度为 $O(lo{g}_{2}n)$。Windows 内核使用 AVL 树保存一些离散的地址空间，原因大概是这些地址的访问次数多于插入删除的次数，且 AVL 树的高度低于红黑树。

2.2.2 红黑树

一种平衡的二叉搜索树，其在插入删除节点时旋转次数较少，故在插入删除多的情况下性能高于其他平衡二叉搜索树。

红黑树原理：通过对任何一条从根到叶子的简单路径上各个节点的颜色进行约束（红和黑），确保没有一条路径会比其他路径长2倍，因而是近似平衡的（一个节点的两棵子树高度不会相差二倍），是一棵弱平衡二叉树。所以相对于严格要求平衡的 AVL 树来说，它的旋转保持平衡次数较少。

【应用场景】

• C++ STL 包括set，multiset，map，multimap。C++关联容器，java容器中的TreeMap。
• IO多路复用的epoll，内部用红黑树来维持我们想要监控的socket。以支持快速的插入和删除。
• nginx中定时器是用红黑树来维持的，因为红黑树是有序的，每次从红黑树内部取出最小的定时器即可。
• linux内核中用红黑树来管理进程的内存使用，进程的虚拟地址空间块都以虚拟地址为key值挂在这棵红黑树上。

2.2.3 B 树和 B+ 树

B 树是一种平衡的多路查找树（查找路径不止两条）。在查找节点时，从根节点开始比较，若小于根节点则向左子树查找，否则向右子树查找。在多路分支中，找到合适的区间继续向下查找，直到查找到叶子节点，如果树结构中没有包含查找目标，则返回 null。

m 阶 B 树特点：

• 根结点至少有两个子女
• 每个中间节点都包含 k-1 个元素和 k 个孩子，其中 m/2 <= k <= m
• 每一个叶子节点都包含 k-1 个元素，其中 m/2 <= k <= m
• 每个节点中的元素从小到大排列，节点当中 k-1 个元素正好是 k 个孩子包含的元素的值域分划
• 所有的叶子结点都位于同一层

B+ 树是基于 B 树的一种变体，有着比 B 树更高的查询性能。B+ 树通常用于数据库和操作系统的文件系统中。B+ 树的特点是 能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入。

m 阶 B+ 树特点：

• 有 k 个子树的中间节点包含有 k 个元素（B 树中是 k-1 个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点
• 所有的叶子结点中包含了全部元素的信息及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接
• 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素
  

1. 每一个父节点的元素都出现在子节点中，且是子节点的最大（或最小）元素。
2. 根节点的最大元素就是整个 B+ 树的最大元素，以后无论怎样插入删除，始终要保持最大元素在根节点中。
3. 由于父节点元素都出现在子节点，因此所有叶子节点包含了全部元素信息。
4. 每一个叶子节点都带有指向下一个节点的指针，形成了一个有序链表。

B+ 树与 B 树的区别：

• B 树中无论中间节点还是叶子节点都带有卫星数据，而 B+ 树中只有叶子节点带有卫星数据，其余中间节点仅有索引，没有任何数据关联，所以同样大小的磁盘页可以容纳更多的节点元素，在数据量相同的情况下，B+ 树比 B 树更加 “矮胖”，查询时的 IO 次数也更少
• B+ 树查询必须查找到叶子节点，而 B 树只要找到匹配元素即可，不管匹配元素处于中间节点还是叶子节点，因此 B 树查找性能不稳定（最好情况是只查到了根节点，最坏情况是查到了叶子节点），而 B+ 树的每一次查找都是稳定的
• 范围查询时，B 树需要依靠繁琐的中序遍历，而 B+ 树的所有叶子节点形成有序链表，只需要在链表上做遍历即可

B+ 树的优点：

• 查询时的 IO 次数更少
• 查找性能稳定
• 便于范围查询

【应用场景】

B/B+树主要用在数据库或者大型索引数据中，是一种多路查找树。

B树，B+树：它们特点是一样的，是多路查找树，一般用于数据库系统中，为什么，因为它们分支多层数少呗(一般一个节点有成千上万个子节点，所以B树层数是非常少的，节点个数为N个高度为logN，但是这个log的底数不是我们常用的2了，而是一个节点的子节点个个数，底数非常大从而树高度很低)，都知道磁盘IO是非常耗时的（和内存访问速度差千倍），而像大量数据存储在磁盘中所以我们要有效的减少磁盘IO次数避免磁盘频繁的查找。减少磁盘IO就意味着提升性能。

B+树是B树的变种树，有n棵子树的节点中含有n个关键字，每个关键字不保存数据（也就是节点只保存key），只用来索引，数据都保存在叶子节点。是为文件系统而生的。

B树一般用在数据库等大型索引，主要原因就是层数少，重点—>减少避免磁盘IO
B+树适应文件系统，想下文件系统的样子，目录并不保存文件只有底层叶子节点保存数据。

2.3 Trie树

单词查找树，主要处理字符串，字符串的相同前缀保存在相同的节点中。它的变种树非常多，比如前缀树（prefix tree），后缀树（suffix tree）。

它是不同字符串的相同前缀只保存一份，相对直接保存字符串肯定是节省空间的，但是它保存大量字符串时会很耗费内存（是内存）。

【应用场景】

前缀树(prefix tree)：
1.字符串快速检索
2.字符串排序
3.最长公共前缀
4.自动匹配前缀显示后缀。

后缀树(suffix tree)：
1.查找字符串s1在s2中
2.字符串s1在s2中出现的次数
3.字符串s1,s2最长公共部分
4.最长回文串
详情还是见

2.4 并查集（Union Find）

并查集是一种树型数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。凡是涉及到 元素的分组管理问题，都可以考虑使用并查集进行维护。

学习参考：算法学习笔记(1) : 并查集 - 知乎

2.5 哈夫曼树

哈夫曼树如何构成？

树的带权路径长度（WPL）
哈夫曼树是在叶子节点和权重确定的情况下，带权路径长度最小的二叉树，也称作最优二叉树。

如何构建二叉树，才能保证其带权路径长度最小？
应该让权重小叶子节点的远离树根，让权重大的叶子节点靠近树根。

计算方法：每个叶子节点的权重 x 根节点到该叶子节点的路径长度 之和

相同叶子节点构成的哈夫曼树可能不止一棵

构建哈夫曼树：

• 构建森林，把每个叶子节点都当作一棵独立的树（只有根节点的树）；同时有一个辅助队列，队列中按照权值大小存储所有叶子节点。
• 选择当前权值最小的两个节点，生成新的父节点，父节点的权值是这两个节点的权值之和
• 从辅助队列删除上一步所选择的两个最小节点，将上一步生成的新的父节点加入队列，仍然保持队列的升序
• 重复执行第二步操作
• 最后队列中仅剩一个节点，说明整个森林已经合并为了哈夫曼树

2.6 堆（Heap）

最大（小）堆是指在树中，若某结点有孩子结点，则该结点的值都不小于（大于）其孩子结点的值。在实现时，一般用 数组 来表示堆，$i$ 节点的父节点下标为 $(i-1)/2$，左、右子节点的下标分别为 $2\ast i+1$ 和 $2\ast i+2$。

特点：堆是完全二叉树，但不一定是满二叉树。

堆节点的插入：新插入的元素放在数组最后，然后更新这棵树，更新过程类似于直接插入排序。

堆节点的删除：按定义堆中每次都删除第 0 个数据，即删除最小/最大的节点。实际操作是将堆中最后一个数据的值赋给根节点，然后再从根节点向下进行逐层调整，相当于将根节点下沉。

堆化数组：对于任意一棵二叉树的叶子节点，不需要调整次序，从最后一个非叶子节点开始调整。

3. 哈希表

可以实现 $O(1)$ 级别的增、删、改、查效率。但哈希表基于数组实现，创建后难以扩展，

4. 栈和队列

栈是一种先进先出的结构，这个不用多说。在具体实现时，分为顺序栈和链栈，顺序栈用数组实现，链栈用链表实现。

顺序栈：元素存储位置连续，需要知道栈的最大长度才可以使用，无法避免溢出问题。当系统分配了数组存储空间，即使未使用到其他任务也不能使用该块空间，存储密度等于 1。顺序栈的 top 指针指向栈顶的空元素，top-1 指向栈顶元素。

# 顺序栈实现
class Stack:
    def __init__(self):
        self.value = []

    def push(self, item):  # 压栈
        self.value.append(item)

    def pop(self):  # 出栈
        if self.is_empty():
            print('为空栈!')
            return
        return self.value.pop()
    def is_empty(self):  # 判断空栈
        return self.len() == 0

    def len(self):   # 当前栈大小
        return len(self.value)

    def peek(self):  # 查看栈顶元素
        if self.is_empty():
            print('为空栈!')
            return
        return self.value[-1]  

链栈：元素存储不连续，动态申请地址，可以以非常小的初始内存空间开始。当某块内存未使用时，可以将内存返还给系统利用，存储密度 < 1。链栈的 top 指针相当于链表的 head 指针，容易实现插入和删除操作。

# 链栈实现
# 注意栈用链表实现时，栈顶应在链表头（而非链表尾），这样才能保证出栈正确
class ListNode:
    def __init__(self, item, next = None):
        self.item = item
        self.next = next

class ListStack():
    def __init__(self):
        self.top = None
        
    def push(self, item):  # 入栈
        self.top = ListNode(item, self.top)
        
    def pop(self):   # 出栈
        if self.top is None:
            print("空栈")
            return
        t = self.top
        self.top = self.top.next
        return t.item
        
	def is_empty(self):   # 判断空栈
        return self.top is None
        
    def top(self):  # 查看栈顶元素
        if self.top is None:
            print("空栈")
            return
        return self.top.item
        
if __name__ == '__main__':
    st = ListStack()
    for i in range(1, 10, 2):
        st.push(i)
    while not st.is_empty():
        print(st.pop())

距离上一次对redis的学习【Redis从入门到放弃系列 三】数据结构居然已经过去一年多了，还是自己没有坚持下去吧，今年刚好在学中间件，那么还是继续顺着学下去吧，但是总要复习一下并且更好的总结提升，那么本篇blog在既往的三篇之上做好总结并且有更深入的探索，方便后续的学习。按照如下的目录去组织：

• Redis的基本概念与特点：Redis的基本概念是什么，有什么特点
• Redis的安装与使用：windows版本的服务端与客户端的安装
• Redis的应用场景：总体的应用场景有哪些，为什么有Reids的需求
• Redis的数据结构及对应场景：分类的数据结构及每一类的结构具体应用场景有哪些

那么从这四方面的角度出发来重新认识下Reids。

Redis的基本概念与特点

Redis通俗的说就是一种远程数据字典服务，用C语言开发的，那必须快，redis在现在的应用中使用的非常广泛。它的典型应用是：内容缓存，主要用于处理大量数据的高访问负载，优点就是快速查询。

在整个系统架构中其实一般用于热点信息或者高频信息的获取等。

Redis的安装与使用

简单的功能可以在Windows上安装一个，进行基本命令的操作，可以直接从我的网盘下载win-redis-64，提取码为redi，下载直接解压后可以看到Redis的目录非常简单，只有以下六个文件：

而我们实际常用的文件只有两个，一个客户端一个服务端，启动服务端后，就可以在客户端进行任意的操作，服务端界面如下：

一个服务端绑定一个端口，如果需要在一台机器上开启多个，需要复制几个实例，并且设置不同的端口号。而PID就是实例ID，每次启动都是一个随机值。客户端如下：

相当于一个命令窗口，使用命令进行Redis操作即可。

Redis的应用场景

实际上在【Redis从入门到放弃系列 二】基本概念这篇blog中已经详细论证过为什么需要使用NoSql
数据库以及它要解决的Web2.0时代的问题，在整个分布式技术系列文章中我也反复说明了，其实分布式的解决方案其实就是为了解决海量增长的业务数据的性能瓶颈问题：高并发读写、海量数据的高效率存储和访问、高可拓展性和高可用性，我之前整理的Kafka、ElasticSearch以及Cassandra都需要满足以上三个功能特性，然后作为服务的一部分被架构到系统中，所以Redis被设计出来也是为了对这类问题处理的补充，那么当然它也应该具备这些特性。

在一个经典的场景中各类中间件都承担一部分的职责，当然每一种职责都有其替代品。现在我司目前的这一套内容是【Cassandra（业务数据)+ElasticSearch(全文检索)+SqlServer\MySql(数据存储)+Redis（数据缓存）+Kafka（消息中间件）】，我相信任何公司使用的时候应该也是大同小异。但Redis的应用场景也不只是热点信息的存储，常用到的应用场景如下：

• 缓存，缓存现在几乎是所有中大型网站都在用的必杀技，合理的利用缓存不仅能够提升网站访问速度，还能大大降低数据库的压力。Redis提供了键过期功能，也提供了灵活的键淘汰策略，所以，现在Redis用在缓存的场合非常多。存储访问频率高的热数据防止穿透到数据库。
• 排行榜，很多网站都有排行榜应用的，如京东的月度销量榜单、商品按时间的上新排行榜等。Redis提供的有序集合数据类构能实现各种复杂的排行榜应用。sorted_set数据结构
• 计数器，什么是计数器，如电商网站商品的浏览量、视频网站视频的播放数等。为了保证数据实时效，每次浏览都得给+1，并发量高时如果每次都请求数据库操作无疑是种挑战和压力。Redis提供的incr命令来实现计数器功能，内存操作，性能非常好，非常适用于这些计数场景。
• 分布式会话，集群模式下，在应用不多的情况下一般使用容器自带的session复制功能就能满足，当应用增多相对复杂的系统中，一般都会搭建以Redis等内存数据库为中心的session服务，session不再由容器管理，而是由session服务及内存数据库管理。
• 分布式锁，在很多互联网公司中都使用了分布式技术，分布式技术带来的技术挑战是对同一个资源的并发访问，如全局ID、减库存、秒杀等场景，并发量不大的场景可以使用数据库的悲观锁、乐观锁来实现，但在并发量高的场合中，利用数据库锁来控制资源的并发访问是不太理想的，大大影响了数据库的性能。可以利用Redis的setnx功能来编写分布式的锁，如果设置返回1说明获取锁成功，否则获取锁失败，实际应用中要考虑的细节要更多。
• 社交网络，点赞、踩、关注/被关注、共同好友等是社交网站的基本功能，社交网站的访问量通常来说比较大，而且传统的关系数据库类型不适合存储这种类型的数据，Redis提供的哈希、集合等数据结构能很方便的的实现这些功能。hash、list数据结构
• 最新列表，Redis列表结构，LPUSH可以在列表头部插入一个内容ID作为关键字，LTRIM可用来限制列表的数量，这样列表永远为N个ID，无需查询最新的列表，直接根据ID去到对应的内容页即可。list数据结构
• 消息队列，消息队列是大型网站必用中间件，如ActiveMQ、RabbitMQ、Kafka等流行的消息队列中间件，主要用于业务解耦、流量削峰及异步处理实时性低的业务。Redis提供了发布/订阅及阻塞队列功能，能实现一个简单的消息队列系统。另外，这个不能和专业的消息中间件相比。list数据结构

接下来我们在对应的数据结构中一一探讨哪种数据结构适合哪种场景。

Redis的数据结构及对应场景

我们说Redis有五种常用的数据结构，在【Redis从入门到放弃系列 三】数据结构中也对每种数据结构的操作进行过介绍，那么本篇blog其实更侧重对于每种数据结构的应用场景的讨论。

需要注意的一点就是，Redis本身就是个Map，预置明确这个前提后，我感觉后续的讨论中才不会感觉凌乱。接下来每一部分都分为：基本操作、扩展操作【应用场景】、操作规范

String类型

string类型存储的其实就是一个字符串，需要注意的是如果字符串以整数的形式展示，可以作为数字操作使用，也就是我们说的自增操作。

基本操作

了解下基本命令和单指令多指令操作的区别。

基本命令

也就是一次就处理一个key，对key进行增（改）、删、查：

需要注意的是，操作状态返回的0和1要和返回结果做区分，并且set操作其实是【有则更新，无则新增】

当然还有多指令操作-顾名思义就是一次操作多个key和简单的获取及追加操作

单指令与多指令操作

基本的操作功能点分为单指令操作和多指令操作，也就是一次操作一个key或者一次操作多个key，什么情况下使用哪种指令模式需要注意：多指令效率高一些，但是有阻塞的风险，一条指令承载太多了

扩展操作【应用场景】

这里string一般有如下三个应用场景，其实说白了string类型做的操作都是最基本的操作。

• 场景一：利用数值操作特性为分布式数据库主键自增
• 场景二：利用key的生命周期做投票系统
• 场景三：利用string特性做热点数据刷新

当我们简单场景使用时，尤其是有些数值类型操作时，string是不二之选。

场景一：利用数值操作特性为分布式数据库主键自增

redis的string结构可以解决分布式数据库中的主键唯一性问题：

使用incr命令即可做到，在队列自增然后分发到各个数据库中

而且redis是单线程的，所以不存在并发问题

场景二：利用key的生命周期做投票系统

在投票的场景中，我们经常会有一天可投几次票这样的限制，那么这个就需要一个过期时间，当然其实也可以作为锁的过期时间来使用

使用setex来设置过期时间。

场景三：利用string特性做热点数据刷新

可以把大V的各种属性【粉丝数、blog数以及关注数】等设置为一个string类型的key，value为数量，直接简单增加或减少操作即可。

操作规范

一般数据库的热点数据设置格式如下：

只有每隔一个时间才把这些数据持久化，大大减少IO交互及性能的损耗。

Hash类型

其实在string类型中我们知道，string的字符串也可以是一个map格式的，但是map格式里的数据处理就需要编程进行了，基于我们实际场景中遇到的多为对象，我们对对象的更新操作必不可少，hash类型也就很有必要。

当然其底层存储数据结构为哈希表。

基本操作

hash的基本操作和string其实类似，只不过在值的指定和设置时多加了一个维度，也就是字段。

当然其也具备类多指令操作，一次修改多个字段值

扩展操作【应用场景】

hash的主要特性是对象存储模式，我们看基于这样的特性，常用的有哪些场景呢？

• 场景四：利用hash的对象存储特性设置用户的购物车
• 场景五：hash作为商品秒杀计数对象完成商品秒杀系统

这两个业务场景其实在我们生活中还是很常见到的。可以把hash理解为一个复合的string

场景四：利用hash的对象存储特性设置用户的购物车

一个人的购物车可以看做一个对象，而商品可以当做field，数量可以当做value。然后对购物车进行各种操作，hash基本都能满足：

例如对于一些操作场景：

除了基本操作，我们想要增加商品数量，全选查看等都可以使用如下操作：

当然我们当前只能拿到商品数量和商品，对于商品的详细信息一无所知，这个时候就需要对field做更细粒度的拆分：

此时我们又想到，其实商品的信息是公共的，可以将公共的商品信息维护一个商品的hash，可以避免不同的人重复放置购物车占据大量内存，还是只存商品的编号和数值，需要的时候从公共hash取商品详细信息，同时为了避免重复商品入商品hash，使用setnx实现，这样实现性能最优。

场景五：hash作为商品秒杀计数对象完成商品秒杀系统

可以利用hash多字段的特性，来用一个对象完成整体秒杀系统。

操作规范

hash操作有如下的使用规范，最主要的就是别无限套娃，禁止套娃！

同时我们知道string也能存类hash的字符串，但是不能对其中字段操作，但是查看起来是一个完整格式，所以我们总结：

List类型

list的核心特点是顺序性，主要是其底层实际上是一个双向链表结构：

基本操作

其实由于其双向链表的灵活性，很容易模拟出栈或者队列的模式，因为我们查询时是从左边查询的，所以我们一般的使用策略是，从右边进入，这样从表面上看符合进入顺序的，比较直观【队列】

需要注意的是查询索引：Start 只能为0，stop为-1就是倒数第一个，为-2就是倒数第二个

扩展操作【应用场景】

list的主要特性是顺序性，我们看基于这样的特性，常用的有哪些场景呢？

• 场景六：利用blpop特性实现任务队列
• 场景七：利用list顺序特性实现朋友圈点赞
• 场景八：利用list顺序特性进行分布式日志顺序性展示

我们来看看这三个业务场景。

场景六：利用blpop特性实现任务队列

轮询从任务队列里取数据【可以同时从多个队列获取】，如果取到数据就返回，如果没有数据就等待设置时间持续获取，直到数据过期。

一直等【从若干个列表中去等】，只要有数据就返回来

场景七：利用list顺序特性实现朋友圈点赞

因为点赞等信息都是有顺序性的，而且修改的效率高，适合使用list来操作

取消点赞的时候使用如下命令操作：

场景八：利用list顺序特性进行分布式日志顺序性展示

使用list顺序性实现多路数据汇总展示，利用其栈的特性实现最新的消息最先展示。

操作规范

list主要有如下几种使用规范：

Set类型

因为list的查询效率太低，所以需要新的数据模型来进行支持，Redis 的 Set 是 String 类型的无序集合。集合成员是唯一的，这就意味着集合中不能出现重复的数据

那么为什么我们的值不允许重复呢？，不支持vaule重复录入，因为我们原来hash里的field也不允许重复

基本操作

set的操作相对简单，主要明确一点，set里不会有重复数据：

扩展操作【应用场景】

set的主要特性是不重复性，我们看基于这样的特性，常用的有哪些场景呢？

• 场景九：利用set特性随机获取不重复数据实现简单推荐系统
• 场景十：利用set交并差实现推荐系统池
• 场景十一：利用set不重复特征获取所有业务系统权限
• 场景十二：利用set不重复特征获取UV和IP数据
• 场景十三：利用set不重复特征实现黑白名单

我们来看看这五个业务场景。

场景九：利用set特性随机获取不重复数据实现简单推荐系统

可以使用如下命令：

场景十：利用set交并差实现推荐系统池

可以使用如下命令实现：

总而言之就是实现数据的关联差异：

场景十一：利用set不重复特征获取所有业务系统权限

我们可以设置用户为一个set集合，他的权限为value，然后合并所有用户就可以拿到所有不重复权限

场景十二：利用set不重复特征获取UV和IP数据

我们可以采用将ip或者cookie放到set中保证不重复，对同类型数据进行快速去重

场景十三：利用set不重复特征实现黑白名单

实现时把对应黑白名单信息源添加到set中即可。

操作规范

Sorted_Set类型

redis 有序集合和集合一样也是string类型元素的集合,且不允许重复的成员。不同的是每个元素都会关联一个double类型的分数。redis正是通过分数来为集合中的成员进行从小到大的排序。有序集合的成员是唯一的,但分数(score)却可以重复。

基本操作

操作都是关联score的，获取时按照score值来进行排序获取。

同时需要注意，删除的时候按照值删除，而不是按照score删除。

扩展操作【应用场景】

sorted_set最经典的应用场景就是进行排行榜设置了。当然除此之外还有些带权重的操作都类似：

• 场景十四：利用set不重复排序特征实现计数器组合排序排行榜功能
• 场景十五：利用set不重复排序特征实现基于时效性任务提醒
• 场景十六：利用set不重复排序特征实现带权重任务队列

接下来看下这三种场景

场景十四：利用set不重复排序特征实现计数器组合排序排行榜功能

可以利用如下命令直接获取排名

场景十五：利用set不重复排序特征实现基于时效性任务提醒

队列中全部为vip，按照会员时间长短排序，短时间到期后提醒下一个。

场景十六：利用set不重复排序特征实现带权重任务队列

仅是任务队列可以通过队列，但是如果队列中的任务有优先级，则需要使用带权重的。

操作规范

Redis数据结构综合应用场景及总结

最后总结一下各类数据结构他们的性能和特点吧，方便之后用的时候好记忆：

数据类型	特点	查询性能	插入、删除性能	适用场景
string	性能高	O(1)【多指令时为O(N)】	O(1)【多指令时为O(N)】	计数器、分布式自增主键、按时按次服务计算、热点数据刷新、时效性投票系统
hash	结构性	O(1)【同时设置多字段时为O(N)】	O(1)【同时设置多字段时为O(N)】	购物车操作、抢购系统
list	顺序性	O（n）	O（1）	社交点赞、任务队列、分布式日志顺序显示
set	不重复性	O（1）【多值操作时为O(N)】	O（1）【多值操作时为O(N)】	黑白名单、推荐系统、业务系统权限整合、UV\IP数据统计
sorted_set	不重复排行榜	O（1）	O(log(n))	合并排行榜、带权重的任务队列、vip超时队列【时间作为得分】

总体而言，redis的设计就是简单、快，时间复杂度最多不超过O（N），并且设计了多种有特色的数据结构，利用这些数据结构服务现有的业务场景。

时间复杂度部分来源于 https://blog.csdn.net/zzm848166546/article/details/80360665，深度好文

限时限次结算的服务控制

按此结算的服务限制需要限制：每分钟最多调用10次。

选定类型：string，选定命令 setex , 设定redis的生命周期，每次incr后get一次，到10次的时候禁止调用,并且生命周期到期后清空值。

操作同理，但是可以设置数字的最大值，利用超过报异常来避免每次get操作

微信接收消息顺序通知

需要区分置顶用户和普通用户，并且后来的消息在最上边，先看到【按栈模型使用】

选定类型：list、set，选定命令 消息来了之后先和set比较是否为置顶用户然后加入不同的list，并且后来的list较新展示

如果需要做计数，再对相同的消息设备同步使用一个计数redis去实现。当然这里使用sorted_set也可以，用时间作为排行榜得分。

总结

通过一周的学习终于从场景的角度更深入的理解了redis的使用，基于这周的学习内容，依据redis的不同数据结构的特性，再次梳理下场景：

• string，redis对于KV的操作效率很高，可以直接用作计数器。例如，统计在线人数等等，另外string类型是二进制存储安全的，所以也可以使用它来存储图片，甚至是视频等。【计数器、分布式自增、分布式锁、热点数据刷新】
• hash，存放键值对，一般可以用来存某个对象的基本属性信息，例如，用户信息，商品信息等，另外，由于hash的大小在小于配置的大小的时候使用的是ziplist结构，比较节约内存，所以针对大量的数据存储可以考虑使用hash来分段存储来达到压缩数据量，节约内存的目的，例如，对于大批量的商品对应的图片地址名称。比如：商品编码固定是10位，可以选取前7位做为hash的key,后三位作为field，图片地址作为value。这样每个hash表都不超过999个，只要把redis.conf中的hash-max-ziplist-entries改为1024，即可。【数据对象存储、秒杀系统、分布式锁】
• list，列表类型【顺序性】，可以用于实现消息队列，也可以使用它提供的range命令，做分页查询功能。【任务队列、社交点赞、分布式日志顺序显示】
• set，集合，整数的有序列表可以直接使用set。可以用作某些去重功能，例如用户名不能重复等，另外，还可以对集合进行交集，并集操作，来查找某些元素的共同点。【推荐系统、数据去重、运营数据统计、黑白名单】
• Sorted_Set，有序集合，可以使用范围查找，排行榜功能或者topN功能。【排行榜】

总而言之，string当做计数器，hash存储对象，list实现消息队列（安全队列），set用来去重和联表查询，zset用来做排行榜。