Redis有五种主要的数据结构：字符串（Strings）、列表（List）、哈希表（Hashes）、集合（Sets）、有序集合（Sorted Sets）
字符串（Strings）：是redis中最基本的数据类型，它可以包含数字，字符串等数据。在redis中，字符串是二进制安全的，这说明他们可以有任何的长度，而且不会因为包含空字符而被截断。
列表（Lists）：简单的字符串列表，按照插入的顺序排序。你可以添加一个元素到头部或者尾部。
哈希表（Hashes）：是键值对的集合，是字符串类型的字段和值的映射表，适合用来存储对象
集合（Sets）：是字符串类型的无序集合。它是通过哈希表实现的，可以做到添加、删除等基本操作的时间复杂度都是O(1)。
有序集合（Sorted Sets）：和Sets相似，但每个字符串元素都会关联在一个浮点数的分数。元素的分数用来排序，如果两个成员有相同的分数，那么他们的排名按照字典序计算。
什么是二进制安全？
大家都知道，redis的底层是由C语言实现的。在C语言中的字符串存在一个缺陷，那就是字符串是以“\O”来结尾的，这也就是空字符串。如果字符串中包含空字符串，那么程序在读取字符串的时候，会将空字符后面的字符忽略掉，这样读出来的字符串就不是原有的字符串了。
那么Redis是如何解决的呢？
redis中定义了一个字符串，叫做简单动态字符串（SDS）。SDS的API会以安全的方式读取字符串，即使这个字符串中存在空字符，也会将这个字符串完整的读出来。
redis之所以能够将整个字符串都读出来，是由SDS的结构决定的，SDS本身会保存字符串的长度，这样API在读取字符串的时候，就会根据这个长度去读取，从而不会丢掉空字符后面的字符了。
字符串底层实现：简单动态字符串（SDS）
源码：
struct sdshdr {
int len; //记录buf数组中已使用字节的数量，等于SDS所保存字符串的长度
int free; //记录buf数组中未使用字节的数量
int buf[]; //字节数组，用于保存字符串。这个数组没有指定长度，柔性数组
}
SDS示例：
使用简单动态数组的优势：
预分配：SDS会为buf分配额外的未使用空间（通过free字段记录），这意味着当你像一个SDS字符串追加内容的时候，如果你的free中记录的未使用的空间足够，Redis就不需要重新为其分配内存。这样就减少了内存分配的次数，从而提高了性能。
常数时间复杂度获取字符串长度：由于SDS结构内部维护了一个len字段来记录字符串的当前长度，获取字符串长度的操作可以在常数时间复杂度O(1)内完成，而不需要像C语言的字符串那样遍历整个字符串。
二进制安全：SDS可以存储任意二进制数据，当然就包括了空字符“\0”，C语言的原生字符串以空字符作为结束的标志，这也就限制了他们的字符中不能包含空字符。而SDS通过len字段来解决了这个问题，所以不受空字符串的影响。
列表的底层实现：双向链表与压缩列表
压缩列表：
当列表的元素数量较少且元素较小的时候，Redis会使用压缩列表（ziplist）作为底层实现来节省内存。压缩列表是一个紧凑的、连续的内存块，它按顺序存储了列表中的元素。
ziplist结构：
Zlbyte:压缩列表的头部信息，包含了特殊编码和压缩列表的长度信息。
Len：每个元素前的长度字段，用于记录该元素的长度或者和前一个元素到当前元素的偏移量。
one、two ：实际的列表元素，他们被连续的存储到压缩列表中。
使用Ziplist的优势：
内存的利用率高，因为元素是连续的，没有额外的指针开销。
对于小列表，操作速度可以很快，因为所有的数据都在一个连续的内存块中。
双向链表：
当列表的元素数量较多或者元素较大的时候，Redis会选择使用双向链表作为底层实现。双向链表中的每个节点都保存了前一个结点和后一个结点的指针，这使得在列表的任何位置插入或者删除元素都变得相对容易。
typedef struct listNode {
struct listNode *prev; //指向前一个节点的指针
struct listNode *next; //指向后一个结点的指针
void *value; //节点保存的数据
} listNode;
typedef struct list {
listNode *head; //指向链表头部的指针
listNode *tail; //指向链表尾部的指针
unsigned long len; //链表的长度
......
...
}
优势：
可以在O(1)时间复杂度内完成在列表头部或者尾部的元素插入和删除。
当需要遍历列表的时候，可以从头部或者尾部开始，沿着节点的指针依次访问。
哈希的底层实现：Redis中的字典与压缩列表
Redis的哈希（Hashes）类型允许用户在单个键中存储多个字段和对应的值。为了高效的支持这种数据结构，Redis在底层使用了两种主要的数据结构来实现哈希：字典（也被称为哈希表）和压缩列表。
压缩列表在实现列表的时候讲过了，所以在这里展开讲一下字典：
字典（Hash表、hashtable）：
当哈希中的字段和值较大或者较多的时候，Redis会选择使用字典作为底层实现。字典是一种通过键来直接访问值的数据结构，它能够在平均情况下提供O（1）时间复杂度的查找、插入和删除操作。
typede struct dictEntry {
void *key; //键 字段
union {
void *val;
uint64_t u64;
int64_t s64;
......
} v; //值
struct dicEntry *next; //指向下一个节点的指针
} dicEntry;
typedef struct dict {
dicEntry **table; //哈希表的数组
unsigned long size; //哈希表的大小
unsigned long sizemask; //用于计算索引的
unsigned long used; //已使用节点的数量
//...可能还有其他的字段
} dict
使用字典的优势：
提供了快速的字段查询、插入和删除操作
集合的底层实现：整数集合和字典
redis的集合（Sets）是一个无序的、元素不重复的集合。为了高效地支持这种数据结构及其操作，Redis在底层使用了两种主要的数据结构：整数集合（intset）和字典（hashtable）。
整数集合:
当集合中的元素都是整数，并且元素数量较少的时候，Redis会选择使用整数集合作为底层实现。整数集合是一个紧凑的数组，数组中的每个元素都是集合中的一个整数。
typedef struct intset {
//编码方式
uint32_t encodding;
//集合包含的元素数量
uint32_t length;
//保存元素的数组
int8_t contents[];
} intset;
优势：
没内存利用效率高：整数集合将整数存储在一个连续的内存块中，没有额外的指针开销。
操作速度快：对于整数集合中的元素，Redis可以直接通过数组索引访问，这使得查找、添加和删除的操作非常的快。
劣势：
整数集合有局限性。由于它要求集合中二元素必须是整数，并且元素的数量比较少，因此在处理非整数元素或大量的元素时，整数集合就比较鸡肋了。
有序集合的实现：调表和压缩列表
Redis的有序集合（Sorted Sets）是一个有序的、元素不重复的集合，其中每个元素都关联了一个分数（score）。为了实现这种数据结构及其相关操作的高效性，Redis在底层主要使用了两种数据结构：压缩列表（ziplist）和跳表（skiplist）。
跳表（skiplist）
当有序集合的元素数量较多或者较大时，Redis会使用跳表作为底层实现。跳表是一种多层的有序链表，它通过维护多个层次的指针来加快查找、插入和删除的速度。
跳表的查找规则：
从顶层链表的首元素开始，从左向右搜索，直至找到一个大于或者等于目标的元素，或者到达当前链表层的尾部。
如果该元素等于目标元素，则表示该元素已经被找到。
如果该元素大于目标元素或者已到达链表的尾部，则退回到当前层的前一个元素，然后转入下一层进行搜索。
例子：我想查询值为5的元素
首先从顶层开始搜索，从1开始向右搜索 到达该层的尾部，返回到顶层的元素1的位置，然后进到第二层的1 开始搜索，1的下一个元素是4 比我们要找的目标数5小 继续向右搜索，4的下一个元素是6 比5大，所以返回当前层的元素4 然后转入下一层进行搜索，第三层的元素4的下一个元素是6 还是比五小，所以返回到第三层的元素4 然后转入下一层进行搜索，第四层（也就是最底层）的元素4的下一个元素是5，5等于我们要找的目标元素，所以改元素被找到。
优势：
查找的效率高：通过维护多个层次的指针，跳表可以在平均情况下提供O（logN）时间负责度的查找操作（N是元素的数量）。
插入和删除操作快速：跳表的插入和删除操作只需要局部地调整指针，而不需要移动大量的数据。
支持范围查询：调表可以方便的支持按照分数范围进行查询元素。
版权归原作者 刽子手发艺 所有， 如有侵权，请联系我们删除。