引言

redis面向客户端有8种数据结构，而底层有多种实现方式

1.底层实现

1.1 SDS

简单动态字符串(simple dy namic string,SDS)的抽象类型,并将SDS用作Redis的默认字符串表示

struct sdshdr {
    int len;        //buf中已占用空间的长度
    int free;       //buf中剩余可用空间的长度
    char buf[];     //初始化sds分配的数据空间，而且是柔性数组（Flexible array member）
};

优点：

兼容C的部分函数，二进制安全(不会遇0而止)，len方法复杂度为o(1),杜绝缓冲区溢出
惰性空间释放：当要缩短SDS保存的字符串时，程序并不立即使用内存充分配来回收缩短后多出来的字节，而是使用表头的free成员将这些字节记录起来，并等待将来使用。

1.2 linkedlist

双向链表，链表结点类型

typedef struct listNode {
    struct listNode *prev; //前驱节点，如果是list的头结点，则prev指向NULL
    struct listNode *next;//后继节点，如果是list尾部结点，则next指向NULL
    void *value;            //万能指针，能够存放任何信息
} listNode;

优点：prev和next指针：获取某个节点的前驱节点和后继节点复杂度为O(1)。

表头类型

typedef struct list {
    listNode *head;     //链表头结点指针
    listNode *tail;     //链表尾结点指针

    //下面的三个函数指针就像类中的成员函数一样
    void *(*dup)(void *ptr);    //复制链表节点保存的值
    void (*free)(void *ptr);    //释放链表节点保存的值
    int (*match)(void *ptr, void *key); //比较链表节点所保存的节点值和另一个输入的值是否相等
    unsigned long len;      //链表长度计数器
} list;

利用list表头管理链表信息的好处：

head和tail指针：对于链表的头结点和尾结点操作的复杂度为O(1)。
len 链表长度计数器：获取链表中节点数量的复杂度为O(1)。
dup、free和match指针：实现多态，链表节点listNode使用万能指针void *保存节点的值，而表头list使用dup、free和match指针来针对链表中存放的不同对象从而实现不同的方法。

1.3 字典

redis的字典是由哈希表实现的，一个哈希表有多个节点，每个节点保存一个键值对，通过链地址法解决hash冲突

typedef struct dictht { //哈希表
    dictEntry **table;      //存放一个数组的地址，数组存放着哈希表节点dictEntry的地址。
    unsigned long size;     //哈希表table的大小，初始化大小为4
    unsigned long sizemask; //用于将哈希值映射到table的位置索引。它的值总是等于(size-1)。
    unsigned long used;     //记录哈希表已有的节点（键值对）数量。
} dictht;

typedef struct dictEntry {//字典结点
    void *key;                  //key
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;                        //value
    struct dictEntry *next;     //指向下一个hash节点，用来解决hash键冲突（collision）
} dictEntry;

typedef struct dict { //字典
    dictType *type;     //指向dictType结构，dictType结构中包含自定义的函数，这些函数使得key和value能够存储任何类型的数据。
    void *privdata;     //私有数据，保存着dictType结构中函数的参数。
    dictht ht[2];       //两张哈希表。
    long rehashidx;     //rehash的标记，rehashidx==-1，表示没在进行rehash
    int iterators;      //正在迭代的迭代器数量
} dict;

typedef struct dictType {
    unsigned int (*hashFunction)(const void *key);      //计算hash值的函数
    void *(*keyDup)(void *privdata, const void *key);   //复制key的函数
    void *(*valDup)(void *privdata, const void *obj);   //复制value的函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);  //比较key的函数
    void (*keyDestructor)(void *privdata, void *key);   //销毁key的析构函数
    void (*valDestructor)(void *privdata, void *obj);   //销毁val的析构函数
} dictType;

rehash

当哈希表的大小不能满足需求，就可能会有两个或者以上数量的键被分配到了哈希表数组上的同一个索引上，于是就发生冲突（collision），在Redis中解决冲突的办法是链接法（separate chaining）。但是需要尽可能避免冲突，希望哈希表的负载因子（load factor），维持在一个合理的范围之内，就需要对哈希表进行扩展或收缩。

Redis对哈希表的rehash操作步骤如下：

扩展或收缩
- 扩展：ht[1]的大小为第一个大于等于ht[0].used * 2的 2n2n 。
- 收缩：ht[1]的大小为第一个大于等于ht[0].used的 2n2n 。
将所有的ht[0]上的节点rehash到ht[1]上。
释放ht[0]，将ht[1]设置为第0号表，并创建新的ht[1]。

渐进式rehash

渐进式rehash的关键：

字典结构dict中的一个成员rehashidx，当rehashidx为-1时表示不进行rehash，当rehashidx值为0时，表示开始进行rehash。
在rehash期间，每次对字典的添加、删除、查找、或更新操作时，都会判断是否正在进行rehash操作，如果是，则顺带进行单步rehash，并将rehashidx+1。
当rehash时进行完成时，将rehashidx置为-1，表示完成rehash。

1.4 sikplist

定义：跳跃表是一个有序链表，其中每个节点包含不定数量的链接，节点中的第i个链接构成的单向链表跳过含有少于i个链接的节点。
跳跃表支持平均O(logN)，最坏O(N)复杂度的节点查找，大部分情况下，跳跃表的效率可以和平衡树相媲美。
跳跃表在redis中当数据较多时作为有序集合键的实现方式之一

typedef struct zskiplistNode { //跳跃表结点
    robj *obj;                          //保存成员对象的地址
    double score;                       //分值
    struct zskiplistNode *backward;     //后退指针
    struct zskiplistLevel {
        struct zskiplistNode *forward;  //前进指针
        unsigned int span;              //跨度
    } level[];                          //层级，柔型数组
} zskiplistNode;

typedef struct zskiplist { //跳跃表结构
    struct zskiplistNode *header, *tail;//header指向跳跃表的表头节点，tail指向跳跃表的表尾节点
    unsigned long length;       //跳跃表的长度或跳跃表节点数量计数器，除去第一个节点
    int level;                  //跳跃表中节点的最大层数，除了第一个节点
} zskiplist;

1.5 intset

整数集合（intset）是集合键底层实现之一。集合键另一实现是值为空的散列表（hash table），虽然使用散列表对集合的加入删除元素，判断元素是否存在等等操作时间复杂度为O(1)，但是当存储的元素是整型且元素数目较少时，如果使用散列表存储，就会比较浪费内存，因此整数集合（intset）类型因为节约内存就存在

typedef struct intset {
    uint32_t encoding;  //编码格式，有如下三种格式，初始值默认为INTSET_ENC_INT16
    uint32_t length;    //集合元素数量
    int8_t contents[];  //保存元素的数组，元素类型并不一定是ini8_t类型，柔性数组不占intset结构体大小，并且数组中的元素从小到大排列。
} intset;               //整数集合结构

intset整数集合之所以有三种表示编码格式的宏定义，是因为根据存储的元素数值大小，能够选取一个最”合适”的类型存储，”合适”可以理解为：既能够表示元素的大小，又可以节省空间。

intset不能降级

升级过程：调整内存空间，类型转换并复制原数据，添加新数据

1.6 ziplist

压缩列表(ziplist)是哈希键的底层实现之一。它是经过特殊编码的双向链表，和整数集合(intset)一样，是为了提高内存的存储效率而设计的。当保存的对象是小整数值，或者是长度较短的字符串，那么redis就会使用压缩列表来作为哈希键的实现。

压缩列表ziplist结构本身就是一个连续的内存块，由表头、若干个entry节点和压缩列表尾部标识符zlend组成，通过一系列编码规则，提高内存的利用率，使用于存储整数和短字符串。
压缩列表ziplist结构的缺点是：每次插入或删除一个元素时，都需要进行频繁的调用realloc()函数进行内存的扩展或减小，然后进行数据”搬移”，甚至可能引发连锁更新，造成严重效率的损失。

![2020-08-02 13-37-38 的屏幕截图](/home/laglangyue/Pictures/2020-08-02 13-37-38 的屏幕截图.png)

![2020-08-02 13-35-16 的屏幕截图](/home/laglangyue/Pictures/2020-08-02 13-35-16 的屏幕截图.png)

1.7 quicklist

quicklist结构是在redis 3.2版本中新加的数据结构，用在列表的底层实现。

quicklist由ziplist组成的双向链表,一个quicklist节点保存的是一片数据，而不再是一个数据，特点是

quicklist宏观上是一个双向链表，因此，它具有一个双向链表的有点，进行插入或删除操作时非常方便，虽然复杂度为O(n)，但是不需要内存的复制，提高了效率，而且访问两端元素复杂度为O(1)。
quicklist微观上是一片片entry节点，每一片entry节点内存连续且顺序存储，可以通过二分查找以 log2(n)log2(n) 的复杂度进行定位。

一个quicklist节点保存的是一片数据，而不再是一个数据

2.对象类型

2.1 key和String字符串对象

字符串对象的编码可以是int、raw或者embstr。如果一个字符串对象保存的是整数值,并且这个整数值可以用long类型来表示,那么字符串对象会将整数值保存在字符串对象结构的ptr属性里面(将void*转换成long),并将字符串对象的编码设置为int。

2.2 列表对象

列表对象的编码可以是ziplist或者linkedlist。ziplist编码的列表对象使用压缩列表作为底层实现,每个压缩列表节点(entry )保存了一个列表元素

当列表对象可以同时满足以下两个条件时,列表对象使用ziplist编码:

列表对象保存的所有字符串元素的长度都小于64字节;
列表对象保存的元素数量小于512个;不能满足这两个条件的列表对象需要使用linkedlist编码。

以上两个条件的上限值是可以修改的,具体请看配置文件中关于list-max-ziplist-value选
项和list-max-ziplist-entries选项的说明

2.3 哈希对象

哈希对象的编码可以是ziplist或者hashtable

ziplist编码的哈希对象使用压缩列表作为底层实现,每当有新的键值对要加入到哈希对象时,程序会先将保存了键的压缩列表节点推入到压缩列表表尾,然后再将保存了值的压缩列表节点推入到压缩列表表尾,因此:

保存了同一键值对的两个节点总是紧挨在一起,保存键的节点在前,保存值的节点在
后;
先添加到哈希对象中的键值对会被放在压缩列表的表头方向,而后来添加到哈希对象中
的键值对会被放在压缩列表的表尾方向。

当哈希对象可以同时满足以下两个条件时,哈希对象使用ziplist编码:

哈希对象保存的所有键值对的键和值的字符串长度都小于64字节;
哈希对象保存的键值对数量小于512个;不能满足这两个条件的哈希对象需要使用
hashtable编码。

这两个条件的上限值是可以修改的,具体请看配置文件中关于hash-max-ziplist-value选项和hash-max-ziplist-entries选项的说明。

2.4 集合对象

集合对象的编码可以是intset或者hashtable，当集合对象可以同时满足以下两个条件时,对象使用intset编码:

集合对象保存的所有元素都是整数值
集合对象保存的元素数量不超过512个

不能满足这两个条件的集合对象需要使用hashtable编码

2.5 有序集合

有序集合的编码可以是ziplist或者skiplist。

ziplist编码的压缩列表对象使用压缩列表作为底层实现,每个集合元素使用两个紧挨在一起的压缩列表节点来保存,第一个节点保存元素的成员(member),而第二个元素则保存元素的分值(score)。

压缩列表内的集合元素按分值从小到大进行排序,分值较小的元素被放置在靠近表头的方向,而分值较大的元素则被放置在靠近表尾的方向

zset结构中的zsl跳跃表按分值从小到大保存了所有集合元素,每个跳跃表节点都保存了一个集合元素:跳跃表节点的object属性保存了元素的成员,而跳跃表节点的score属性则保存了元素的分值。通过这个跳跃表,程序可以对有序集合进行范围型操作,比如ZRANK、ZRANGE等命令就是基于跳跃表API来实现的。

除此之外,zset结构中的dict字典为有序集合创建了一个从成员到分值的映射,字典中的每个键值对都保存了一个集合元素:字典的键保存了元素的成员,而字典的值则保存了元素的分值。通过这个字典,程序可以用O(1)复杂度查找给定成员的分值,ZSCORE命令就是根据这一特性实现的,而很多其他有序集合命令都在实现的内部用到了这一特性

当有序集合对象可以同时满足以下两个条件时,对象使用ziplist编码:

有序集合保存的元素数量小于128个;
有序集合保存的所有元素成员的长度都小于64字节;

不能满足以上两个条件的有序集合对象将使用skiplist编码

命令大全

key

keys * 获取所有的key
select 0 选择第一个库
move myString 1 将当前的数据库key移动到某个数据库,目标库有，则不能移动
flush db      清除指定库
randomkey     随机key
type key      类型
set key1 value1 设置key
get key1    获取key
mset key1 value1 key2 value2 key3 value3
mget key1 key2 key3
del key1   删除key
exists key      判断是否存在key
expire key 10   10过期
pexpire key 1000 毫秒
persist key     删除过期时间

string

set name cxx
get name
getrange name 0 -1        字符串分段
getset name new_cxx       设置值，返回旧值
mset key1 key2            批量设置
mget key1 key2            批量获取
setnx key value           不存在就插入（not exists）
setex key time value      过期时间（expire）
setrange key index value  从index开始替换value
incr age        递增
incrby age 10   递增
decr age        递减
decrby age 10   递减
incrbyfloat     增减浮点数
append          追加
strlen          长度
getbit/setbit/bitcount/bitop    位操作

hash

    hset myhash name cxx
    hget myhash name
    hmset myhash name cxx age 25 note "i am notes"
    hmget myhash name age note   
    hgetall myhash               获取所有的
    hexists myhash name          是否存在
    hsetnx myhash score 100      设置不存在的
    hincrby myhash id 1          递增
    hdel myhash name             删除
    hkeys myhash                 只取key
    hvals myhash                 只取value
    hlen myhash                  长度

list

lpush mylist a b c  左插入
rpush mylist x y z  右插入
lrange mylist 0 -1  数据集合
lpop mylist  弹出元素
rpop mylist  弹出元素
llen mylist  长度
lrem mylist count value  删除
lindex mylist 2          指定索引的值
lset mylist 2 n          索引设值
ltrim mylist 0 4         删除key
linsert mylist before a  插入
linsert mylist after a   插入
rpoplpush list list2     转移列表的数据

set

sadd myset redis 
smembers myset       数据集合
srem myset set1         删除
sismember myset set1 判断元素是否在集合中
scard key_name       个数
sdiff | sinter | sunion 操作：集合间运算：差集 | 交集 | 并集
srandmember          随机获取集合中的元素
spop                 从集合中弹出一个元素

zset

zadd zset 1 one
zadd zset 2 two
zadd zset 3 three
zincrby zset 1 one              增长分数
zscore zset two                 获取分数
zrange zset 0 -1 withscores     范围值
zrangebyscore zset 10 25 withscores 指定范围的值
zrangebyscore zset 10 25 withscores limit 1 2 分页
zrevrangebyscore zset 10 25 withscores  指定范围的值
Zcard zset  元素数量
Zcount zset 获得指定分数范围内的元素个数
Zrem zset one two        删除一个或多个元素
Zremrangebyrank zset 0 1  按照排名范围删除元素
Zremrangebyscore zset 0 1 按照分数范围删除元素
Zrank zset 0 -1    分数最小的元素排名为0
Zrevrank zset 0 -1  分数最大的元素排名为0
Zinterstore
zunionstore rank:last_week 7 rank:20150323 rank:20150324 rank:20150325  weights 1 1 1 1 1 1 1

排序：

    sort mylist  排序
    sort mylist alpha desc limit 0 2 字母排序
    sort list by it:* desc           by命令
    sort list by it:* desc get it:*  get参数
    sort list by it:* desc get it:* store sorc:result  sort命令之store参数：表示把sort查询的结果集保存起来

订阅与发布：

    订阅频道：subscribe chat1
    发布消息：publish chat1 "hell0 ni hao"
    查看频道：pubsub channels
    查看某个频道的订阅者数量: pubsub numsub chat1
    退订指定频道： unsubscrible chat1   , punsubscribe java.*
    订阅一组频道： psubscribe java.*

redis事务：

     隔离性，原子性， 
     步骤：  开始事务，执行命令，提交事务
             multi  //开启事务
             sadd myset a b c
             sadd myset e f g
             lpush mylist aa bb cc
             lpush mylist dd ff gg

redis的数据结构

引言