Redis简单介绍一下Redis是一个开源的、使用C语言编写的、支持网络交互的、可基于内存也可持久化的Key-Value数据库。有哪些数据结构说起Redis数据结构，肯定先想到Redis的5 种基本数据结构：String（字符串）、List（列表）、Set（集合）、Hash（散列）、Zset（有序集合）。但是Redis用C语言封装了一些底层数据结构：SDS、Linked List、Dict、Skip List、整数集合、压缩列表。要把基本数据结构和底层数据结构区分开来，基本数据结构是由底层数据结构实现。SDSSDS：Simple Dynamic String(简单动态字符串)SDS定义源码(源码位置：src/sds.h/sdshdr)Redis3.0版本源码struct sdshdr{ int len;//buf数组已使用的字节数量 int free;//buf数组未使用的字节数量 char buf[];//char数组，保存字符串}Redis6.0版本源码struct __attribute__ ((__packed__)) sdshdr8 {    uint8_t len; // 已使用长度     uint8_t alloc; // 总长度，用1字节存储     unsigned char flags; // 低三位存储，高五位预留     char buf[]; //char数组，保存字符串};struct __attribute__ ((__packed__)) sdshdr16 {    uint16_t len; // 已使用长度     uint16_t alloc; // 总长度，用2字节存储     unsigned char flags; // 低三位存储，高五位预留     char buf[];//char数组，保存字符串};.... //省略 32和64因为Redis源码是C语言写的，所以源码看一下简单了解就可以。主要看看SDS的数据结构，这里以Redis3.0为例int len：记录了buf数组已使用的字节数量int free：记录了buf数组未使用的字节数量char buf[]：定义了一个char数组，用于保存字符串举例：存储一个Redis的String基本数据类型，其中一个String包含一个Key和一个Value，如下但是Redis用C语言封装了一些底层数据结构：SDS为什么不直接用C字符串，而要封装一个SDS：Redis很注重性能，通过SDS的len可以以O(1)复杂度获取字符串长度SDS封装了API，方便字符串操作使用SDS空间分配策略在每次对SDS修改的时候会检查SDS空间是否满足需求，不满足会对空间进行扩展，而C字符串需要在修改前对空间进行手动扩展分配(不进行分配可能导致缓冲区溢出)C字符串使用空字符'\0'来判断结尾，SDS根据实际长度len判断字符结尾Linked ListLinked List即我们比较熟悉的数据结构——链表，Linked List是Redis基本数据结构列表的底层实现之一，当列表对象的所有字符串元素长度都小于64字节，并且保存的元素数量小于512个时，列表采用另外一个底层数据结构“压缩列表”实现，后续会介绍。Linked List节点源码(位置：src/adlist.h/listNode)//Redis3.0~Redis6.0的Linked List源码实现一致//listNode为链表节点typedef struct listNode {    //前置节点    struct listNode * prev;    //后置节点    struct listNode * next;    //节点的值    void * value;}listNode;从源码的定义有前置节点和后置节点可以看出，Redis链表为双向链表，如下图所示Redis Linked List源码(位置：src/adlist.h/list)typedef struct list {    //表头节点    listNode * head;    //表尾节点    listNode * tail;    //链表所包含的节点数量    unsigned long len;    //节点值复制函数    void *(*dup)(void *ptr);    //节点值释放函数    void (*free)(void *ptr);    //节点值对比函数    int (*match)(void *ptr,void *key);} list;list结构中的head、tail分别为头尾节点，head的prev和tail的next都指向NULL，即Linked List为无环的双向链表len保存了链表的节点个数量，通过len可以O(1)复杂度获取链表长度dup函数用于复制链表节点保存的值free函数用于释放链表节点保存的值match函数用于对比链表节点所保存的值和另外一个输入的值是否相等Dict 字典字典即我们熟知的Map，用来保存键值对的抽象数据结构。字典是基本数据结构 Hash的底层实现之一。字典源码比较多，涉及三个部分：哈希表、哈希表节点、字典哈希表和哈希表节点源码如下（位置dict.h/dictht）typedef struct dictht {    //哈希表数组    dictEntry **table;    //哈希表大小    unsigned long size;    //哈希表大小掩码，用于计算索引值。总是等于size-1    unsigned long sizemask;    //该哈希表已有节点的数量    unsigned long used;} dictht;//每个dictEntry结构都保存着一个键值对typedef struct dictEntry {    //键    void *key;    //值    union{        void *val;        uint64_tu64;        int64_ts64;    } v;    //指向下个哈希表节点，形成链表    struct dictEntry *next;} dictEntry;字典源码（位置 src/dict.h/dict）typedef struct dict {    //类型特定函数    dictType *type;    //私有数据    void *privdata;    //哈希表    dictht ht[2];    //rehash 索引。当rehash 不在进行时，值为-1    in trehashidx; /* rehashing not in progress if rehashidx == -1 */} dict; //为保证字典具有多态及泛型，dictType中提供了如哈希函数以及K-V的各种操作函数，使得字典适用于多重情景typedef struct dictType {    //计算哈希值的函数    unsigned int (*hashFunction)(const void *key);    //复制键的函数    void *(*keyDup)(void *privdata, const void *key);    //复制值的函数    void *(*valDup)(void *privdata, const void *obj);    //对比键的函数    int (*keyCompare)    (void *privdata, const void *key1, const void *key2);    //销毁键的函数    void (*keyDestructor)(void *privdata, void *key);    //销毁值的函数    void (*valDestructor)(void *privdata, void *obj);} dictType; 字典采用哈希实现，哈希就是通过哈希算法计算一个哈希值，哈希值作为存储在哈希表数组dictEntry **table的下标，所以会不可避免的出现两个数据计算出来同一个哈希值，即出现“哈希冲突”。字典采用“链地址法”来解决哈希冲突，链地址法即在出现冲突的下标位置建一个链表，然后把后来的数据存储在当前下标的链表下，如下图所示：（亲身经历：这里如果在面试中自己提到了哈希冲突，面试官会顺着往下挖，问你有哪些解决哈希冲突的方法或者问“你了解哪些计算哈希值的哈希算法”，这里不做更多补充，可以参考《大话数据结构》一书8.10、8.11章节）Skip List跳跃表 SkipList 是一种有序数据结构，通过在每个节点中维持多个指向其它节点的指针，达到快速访问节点的目的平均时间复杂度 O（logN），在大部分情况下，跳跃表的效率与平衡树相近，由于跳跃表实现的简易性，所以 Redis 使用跳表代替平衡树。Redis中的基本数据结构有序集合ZSet采用跳表和哈希表实现typedef struct zset {    dict *dict;    zskiplist *zsl;} zset;Redis 跳跃表由 redis.h/zskiplistNode 和 redis.h/zskiplist 两个结构定义typedef struct zskiplist {    // 头节点，尾节点    struct zskiplistNode *header, *tail;    // 节点数量（不算表头）    unsigned long length;    // 目前表内节点的最大层数    int level;} zskiplist;typedef struct zskiplistNode {    // member 对象    robj *obj;    // 分值    double score;    // 后退指针，指向当前节点的前一个节点，用于表尾向表头遍历时使用    struct zskiplistNode *backward;    // 层，节点使用 L1、L2、L3 标记节点中的各个层，每个层里面又带有两个属性    struct zskiplistLevel {        // 前进指针，指向表尾方向的其它节点，当程序从表头向表尾遍历时，会沿着层的前进指针进行        struct zskiplistNode *forward;        // 这个层跨越的节点数量        unsigned int span;    } level[];} zskiplistNode;跳表查找过程跳表的查找会从顶层链表的头部元素开始，然后遍历该链表，直到找到元素大于或等于目标元素的节点，如果当前元素正好等于目标，那么就直接返回它。如果当前元素小于目标元素，那么就垂直下降到下一层继续搜索，如果当前元素大于目标或到达链表尾部，则移动到前一个节点的位置，然后垂直下降到下一层。整数集合整数集合（intset）是集合键的底层实现之一，当一个集合只包含整数值元素，并且这 个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现。  整数集合的实现 整数集合（intset）是Redis用于保存整数值的集合抽象数据结构，它可以保存类型为 int16_t、int32_t或者int64_t的整数值，并且保证集合中不会出现重复元素。   源码：src/intset.h/intset结构表示一个整数集合∶  typedef struct intset (    //编码方式     uint32_t encoding;    // 集合包含的元素数量 ,即contents数组的长度    uint32_t length:    //保存元素的数组    int8_t contents[]:)intset; 一个包含五个int16 t类型整数值的整数集合 ： contents 数组是整数集合的底层实现∶整数集合的每个元素都是contents 数组的 一个数组项（item），各个项在数组中按值的大小从小到大有序地排列，并且数组中不包含 任何重复项。  contents属性声明为int8 t类型的数组，但contents数组的真正类型取决于encoding属性的值：如果 encoding 属性的值为INTSETENC_INT16，数组里的每个项都是一个int16类型的整数值（最小值 为-32768，最大值为32767）。  如果 encoding属性的值为 INTSETENC_INT32，数组里的每个项都是一个int32类型的整数值（最小值 为-2147483648，最大值为2147 483647）。  如果 encoding属性的值为INTSET ENC INT64，数组里的每个项都是一个int64类型的整数值（最小值为-9 223 372036854775808，最大值为9223 372 036854775807）。  升级 每当我们要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有 元素的类型都要长时，整数集合需要先进行升级（upgrade），然后才能将新元素添加到整数 集合里面。  升级的好处提示灵活性，整数集合可以通过自动升级底层数组来适应新元素，所以我们可以随意地将 int16 t、int32 t或者int64t类型的整数添加到集合中，而不必担心出现类型错误， 这种做法非常灵活。  节约内存，整数集合升级的做法既可以让集合能同时保存三种不同类型的值，又可以确保升级操 作只会在有需要的时候进行，这可以尽量节省内存。  压缩列表Ziplist 是由一系列特殊编码的内存块构成的列表，是为了节约内存而开发的顺序型数据结构， 一个 ziplist 可以包含多个节点（entry）， 每个节点可以保存一个长度受限的字符数组（不以 \0 结尾的 char 数组）或者整数压缩列表的组成属性类型长度用途zlbytesuint32_t4字节整个 ziplist 占用的内存字节数，对 ziplist 进行内存重分配，或者计算末端时使用。zltailuint32_t4字节到达 ziplist 表尾节点的偏移量。 通过这个偏移量，可以在不遍历整个 ziplist 的前提下，弹出表尾节点。zllenuint16_t2字节ziplist 中节点的数量。 当这个值小于 UINT16_MAX （65535）时，这个值就是 ziplist 中节点的数量； 当这个值等于 UINT16_MAX 时，节点的数量需要遍历整个 ziplist 才能计算得出。entryX列表节点\ziplist 所保存的节点，各个节点的长度根据内容而定。zlenduint8_t1字节255 的二进制值 1111 1111 （UINT8_MAX） ，用于标记 ziplist 的末端。ziplist 可以包含多个节点，每个节点可以划分为以下几个部分：属性用途pre_entry_length记录压缩列表中前一个节点的长度encoding 、length 记录content属性保存的数据的类型和长度content保存节点的值，节点值可以是字节数组或者整数参考：《Redis设计与实现》