redislist数据结构（redis list的数据结构）

本篇文章给大家谈谈redislist数据结构，以及redis list的数据结构对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、Redis的五种数据结构及其底层实现原理
• 2、Redis数据结构--List（列表）
• 3、搞懂Redis（二）-2：List数据结构
• 4、redis面试之数据结构
• 5、Redis数据结构之string类型和list类型

Redis的五种数据结构及其底层实现原理

redis的字符串类型是由一种叫做简单动态字符串(SDS)的数据类型来实现

SDC和C语言字符串的区别：

1：SDS保存了字符串的长度，而C语言不保存，盯棚凯只能遍历找到第一个\0的结束符才能确定字符串的长度

2：修改SDS，会检查空间是否足够，不足会先扩展空间，防止缓冲区溢出，C字符串不会检查

3：SDS的预分配空间机制，可以减少为字符串重新分配空间的次数

备注：重新分配空间方式，小于1M的数据 翻倍+1，例如：13K+13K+1，如果大于1M，每次多分配1M，例如：10M+1M+1,如果字符串变短，并不会立即缩短，而是采用惰性空间释放，有专门的API可以释放多余空间

hash结构里其实是一个字典，有许多的键值对

redis的哈希表是一个dictht结构体：

哈希表节点的结构体如下：

hash算法：

当要将一个新的键值对添加到字典里面时， 程序需要先根据键值对的键计算出哈希值和索引值， 然后再根据索引值， 将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。

hash冲突解决方式：链表法，后入的放到最前面

rehash：

键值数据量变动时，时为了让哈希表的负载因子（load factor）维持在一个合理的范围之内， 当哈希表保存的键值对数量太多或者太少时， 程序需要对哈希表的大小进行相应的扩展或和仿者收缩。

如果是扩充，新数组的空间大小为 大于2*used的2的n次方，比如：used=5,则去大于10的第一个2的n次方，为16

如果是缩小，新数组的空间大小为第一个不大于used的2的n次方，比如：used=5,则新大小为4

redis的list列表是使用双向链表来实现的

···

typedef struct listNode {

struct listNode * pre; //前置节点

struct listNode * next; //后置节点

void * value; //节点的值

}

typedef struct list {

listNode *head; //表头节点

listNode tail; //表尾节点

unsigned long len; //链表所包含的节点数量

void ( dup) (void ptr); //节点值赋值函数 这里有问题

void ( free) (void ptr); //节点值释放函数

int ( match) (void *ptr, void *key) //节点值对比函数

}

···

1：有序集合的底层实现之一是跳表， 除此之外跳表它在 Redis 中没有其他应用。

2：整数集合（intset）是集合键的底层实现之一： 当一个集合只包含整数值元素， 并且这个集合的元素数量不多时， Redis 就会使用整数集合作为集合键的底层实现。

3：数据少是，使用ziplist(压缩列表)，占用连续内存，每项元素都是(数据+score)的方式连续存储，按照score从小到大排序。ziplist为了节省内存，每个元素占用的空间可以不同，对于大数据(long long),就多用一些字节存储，而对于小的数据(short)，就少用一些字节来存储。因此查找的时候需要按顺序遍历。ziplist省内存但是查找效率低。

无序集合可以用整数集合(intset)或者凯唤字典实现

Redis的5.0版本中，放出一个新的数据结构Stream。其实也是一个队列，没一个不同的key对应的是不同的队列，没个队列的元素，也就是消息，都有一个msgid，并且需要保证msgid是严格递增的。在Stream当中，消息是默认持久化的，即便是Redis重启，也能够读取到信息。

Stream的多播，与其它队列系统相似，对不同的消费者，也有消费者Group这样的概念，不同的消费组，可以消费通一个消息，对于不同的消费组，都维护一个Idx下标，表示这一个消费群组费到了哪里，每次进行消费，都会更新一下这个下标，往后面一位进行偏移。

跳跃表是一种有序数据结构，它通过在每个节点中维持多个指向其它节点的指针，从而大道快速访问节点的目的，具有以下性质：

1：有很多层结构组成

2：每一层都是一个有序的链表，排列顺序为由高到低，都至少包含两个链表节点，分别是前面的head节点和后面的nil节点

3：最底层的链表包含了所有的元素

4：如果一个元素出现在某一层的链表中，那么在该层之下的链表也全部都会出现

5：链表中的每个节点都包含两个指针，一个指向同一层的下一个链表节点，另一个指向下一层的通一个链表节点

多个跳跃表节点构成一个跳跃表

1：搜索，从最高层的链表节点开始，如果比当前节点要大和比当前层的下一个节点要小，那么则往下找，也及时和当前层的下一层的节点下一个节点

2：插入，首先确定插入的层数，有一种方法是抛一个硬币，如果是正面就累加，直到遇到反面为止，最后记录正面的次数作为插入的层数，当确定插入的层数K后，则需要将新元素插入从底层到K层

3：删除，在各个层中找到包含指定值得节点，然后将节点从链表中删除即可，如果删除以后只剩下头尾两个节点，则删除这一层。

整数集合是Redis用于保存整数值集合的抽象数据类型，它可以保存int16_t、int32_t、int64_t的整数值，并且保证集合中不会出现重复元素。

整数集合的每个元素都是contents数组的一个数据项，他们按照从小到大的顺序排列，并且不包含任何重复项。

length属性记录了contents数组的大小。

需要注意的是虽然contents数组声明为int8_t类型，但是实际上contents数组并不保存任何int8_t类型的值，其真正类型由encoding来决定。

压缩列表(ziplist)是Redis为了节省内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构，一个压缩列表可以包含任意多个节点(entry)，每个节点可以保存一个字节数组或一个整数值。

压缩列表的原理：压缩列表并不是对数据利用某种算法进行压缩的，而是将数据按照一定规则编码在一块连续的内存区域，目的是节省内存。

压缩列表的每个节点构成如下：

[img]

Redis数据结构--List（列表）

Redis列表是简单的字符串列表，按照插入顺序排序，你可以添加一个元素到皮空列表的头部（左边）或者尾部（右边）

一个列表最多可以包含超过 40亿个元素

列表的常用命令（持续扩充）：

1、lpush key value1 [value2]： 将一个或多个值插入列表头部（左边）

通过执行lpush animal cat dog   向animal中左边同时插入 cat和dog，下方提示的（Integer）2,是指当前列表中元素的个数；

然后通过查询命令，我们可以看到排在第一个的是dog 第二个是cat，这是因为从左边插入，县插入cat，然后再在左侧插入dog，这就导致dog在cat的前面。

2、rpush key value1 [value2]： 将一个或多个值插入列表尾部（右边）

执行rpush animal monkey：向列表的右侧插入一个元素monkey，此时列表中的元素就有3个

通过查询命令我们可以看到monkey出现在了列表的尾部

3、lrange key start stop： 获取列表指定范围内的元素（包含start和stop）

执行lrange animal 1 2  查询物银列表的第2个和第3个元素（注意列表中的索引是从0开始计算的）

4、llen key： 获取列表长度

在前面几个步骤中我们一共插入了三个元素dog、cat、monkey

5、lpop key： 移出并获取列表的第一个元素

列表中第一个元素是dog，执行lpop animal后，弹出左边第一个元素并燃蚂瞎返回，再次查询，我们看到只剩下两个元素

6、rpop key： 移出并获取列表的最后一个元素

执行rpop animal，移除并返回monkey，最后列表中只剩下cat一个元素

搞懂Redis（二）-2：List数据结构

压缩链表. 好处:节省内存空间,因为它存储的内容都是在连续的内存区域当中的.当列表对象元素不大,每个元素也不大的时候,就采用zipList存储. 但当数据量过大时,zipList就不那么好用了. 因为为了保证它存储内容在内存中的连续性,插入的复杂度为O(N),即每次插入都会重新进行realloc.

zipList的结构如下:

因为zipList是一段连续的内存,插入的时间复杂度O(n),而且每当插入新的元素需要realloc做内存拓展;而且如果超出zipList内存大小,还会做重新分配的内存空间,并将内容复制到新的地址. 如果数量大的话,重新分配内存和拷贝内存会消耗大量时间. 所以不适合大型字符串,也不适合存储量多的元素.

是zipList和linkedList的混合明答体,是瞎纯将linkedList按段切分,每一段用zipList来紧凑存储,多个zipList之间使用双向指针链接.

linkedList的附加空间相对太高,prev和next指针就要占去16字节,而且每个节点都是单独分配,会加剧内存的碎片化,影响内存管理效率.

quickList结构如下

结构图如下:

zipList的长度

内部默认单个zipList的长度为8K字节,超出了这个字节数,就会新起一个zipList.关于长度可以使用list-max-zipList-size决定.

压缩深度

quickList是由多个zipList组成的,同时为了进一步节省空间,Redis还会对zipList进行压缩存储,使用LZF算法压缩,可以选择压激神慧缩深度.quickList默认压缩深度为0,即不压缩. 压缩的实际深度由配置参数list-compress-depth决定.为了支持快速push/pop操作,quickList的首尾两个zipList不压缩,此时深度就是1.如果深度为2,就表示quickList的首尾第一个zipList以及首尾第二个zipList都不压缩.

redis面试之数据结构

redis是面试中最常问的中间件，关于数据结构主要集中在列举和用法。下面我们就数据结构和主要的使用方式做一个描述。

大家都知道redis的几种数据结构，包括string （字符串),hash（哈希），list（列表），set（集合），zset（有序集合）。下面我们来列举一下关于这几种结构的常用命令和一些使用场景。

string是redis的最基本的数据类型。

string类型是二进制安全的，也就是说string里可以包含任何的数据类型。

string类型的值最大能存储512MB

1、 普通的单值缓存

2、对象数据缓存(json格式)

3、分布式锁的应用

4、计数器的使用，使用INCR和DECR

redis hash 是一个string类型的field(字段)和value(值)的映射表，很适合存储对象。

hash最适合的就是做对象缓存

list是redis的字符串列表，可以选择将值插入到头部或尾部。

1、 可以利用list的头部尾部增删属性实现栈和队列

2、 可以用来实现时间轴模型，根据时间依次插入数据，使用LPUSH插入和LRANGE获取最近范围的数据

set是redis的无序集合，是通过哈希表实现的，因此任何操作(添加、删除和测试成员的存在性等)的时间复杂度是O(1)。(无判族好论集合中包含多少元素，时间都是常量)

1、 可以根据set集合的不可重复的特性，统计一些像网站访问IP啊，访问用户啊这些信息，无论访问多少次，SADD加入的都只有一条。

2、 也可以使用SRANDMEMBER和SPOP获取数据穗游的随机性 ，做一些抽奖的小程序等随机功能

3、 作为集合，可以利用交并运算等计算一些复杂的逻辑关系，比如说人掘铅物关系之间的网络关系。

ZSet和set类似，都是字符串的非重复集合。不同之处在于，ZSet的每个成员都与分数相关，分数是用来进行排序的。然后可以使用分数来取一个范围内的数

应用场景：

ZSet是有序的集合，可以使用它来做一个排行榜。

Redis数据结构之string类型和list类型

        String是redis最基础和最常用的数据结构，其值最大能存储 512MB，可以是简单字符串、复杂的xml/json的字符串、二进制图像或者音频的字符串、以及可以是数字的字符串。String底层使用的是SDS，是Redis的一种基本数据结构，主要是用于存储字符串和整数。

    2.1  set命令  set key value

        用于设置给定key的值，如果key存储了其他值，覆盖写入，无视类型。

    2.2 get命令 get key

        获取指定key的值，如果key不存在返回nil

    2.3 getset命令 get key [value]

        该命令用于获取指定的key的旧值，然后按照新值对key进行赋值。当key中没有旧值的时候返回nil。

    2.4 mget命令 get key1 [key2 keyN]

        返回多个key的值，某个key不存在时返回nil

    2.5 decr命令 decr key

        对key对应的数字做减1操作。如果key不存在，那么在操作之前，这个key对应的值会被置为0。如果key有一个错误类型的value或者是一个不能表示成数字的字符串，就返回错误。

    2.6 incr命令 incr key

        对key对应的数字做减1操作。如果key不存在，那么在操作之前，这个key对应的值会被置为0。如果key有一个错误类型的value或者是一个不能表示成数字的字符串，就返回错误。

    2.7 append命令 append key value

    如果 key 已经存在，并且值为字符串，那么这个命令会把 value 追加到原来值（value）的结尾。 如果 key 不存在，那么它将首先创建一个空字符串的key，再执行追加操作，这种情况 APPEND 将类似于 SET 操作。返回append后字符串值（value）的长度。

    3.1 SDS动态字符串

   悔洞岁     struct sdshdr {

            unsigned int len;

            unsigned int free;

            char buf[];

        }

        其中，buf表示数据空间，用于存储字符串；len表示buf中已占用的字节数；free表示空闲的字节数。

    3.2 新的SDS结构

        增加了一个flags来标识类型，用一个字节（8位）来存储，前3位表示字符串的类型；剩余5位，存储长度小于32的段字符串。

        创建 SDS 的大致流程是这样的：首先根据字符串长度计算得到 type，根据 type 计算头部所需长度，然后动态分配内存空间。

        注意：① 创建空字符串时，SDS_TYPE_5 被强制转换为 SDS_TYPE_8（原因是创建空字符串后，内容可能会频繁更新而引发扩容操作，故直接创建为 sdshdr8）

                    ②长度计算有 +1 操作，因为结束符 \0 会占用一个长度的空间。

                    ③返回的是指向 buf 的指针 s。

    4.1 session共享

    4.2 计数器（商品浏览记录）

     4.3 访问限速

    list类型用来存储多个有序的字符串，列表当中的每一个字符看做一个元素，一个列表当中可以存储有一个或者多个元素，redis的list支持存储2^32次方-1个元素。

    Redis可以从两端push和pop元素，支持读取指定范围或者制定下表的元素。list是一种灵活的链式结构，可以充当队列或者栈的角色。

    list的元素是有序的，且列表内的元碧睁素是可以重复的。

    注意：Redis3.2以前，列表底层的编码是ziplist(压缩列表)和linkedlist(双向列表)实现的，因为双线列表占用的内存比压缩列表多，所以当创建新的列表键时，列表会优先考虑用压缩列表，只有在需要的时候才会转换到双向列表实现。3.2以后重新引入了一个quicklist，列表底层都是有quicklist实现，quicklist是一个由ziplist组成的双向列表，每个节点使用ziplist来存储数据。

       2.1 Lpush命令 lpush key value

        将一个或多个值插入到列表头部。 如果 key 不存在，则创建list，然后再插入数据操作。 当 key 存在但不是列表类型时，返回颤野一个错误。

    2.2 Rpush命令 rpush key value

        将一个或多个值从list的尾部插入

    2.3 Blpop命令 blpop key seconds

        Blpop是取出列表的第一个元素，如果list中没有元素则会一直等到到超时，或者发现有数据为止，seconds是指定多少秒返回。如没有数据，则返回nil。

        同理，Bropo为移除list列表的最后一个元素

    2.4 Linsert命令 linsert key before/after val1 val2

        在list列表的某一个元素前或者后插入另外一个元素。当指的的元素不存在时，不执行任何动作。如果列表不存在时，视为空列表，不执行任何动作。

    2.5 Lindex命令 lindex key index

        通过链表的下标获取列表中的元素，可以是-1表示链表最后一个元素，-2代表倒数第二个元素，没有返回nil

    2.6 Llen命令 llen key

        返回list的长度，如果list不存在，返回0

    2.7 Lrange命令

        返回指定list区间内的元素，区间以偏移量start和end决定。其中 0 表示列表的第一个元素， 1 表示列表的第二个元素，以此类推。 也可以使用负数下标，以 -1 表示列表的最后一个元素， -2 表示列表的倒数第二个元素，以此类推。

    5.1 队列秒杀抢购

        list类型的lpop和rpush（或者反过来，lpush和rpop）能实现队列的功能，故而可以用Redis的list类型实现简单的点对点的消息队列。不过不推荐在实战中这么使用，因为现在已经有Kafka、NSQ、RabbitMQ等成熟的消息队列了，它们的功能已经很完善了，除非是为了更深入地理解消息队列，不然没必要去重复造轮子。

    5.2 排行榜

        list类型的lrange命令可以分页查看队列中的数据。可将每隔一段时间计算一次的排行榜存储在list类型中。只有定时计算的排行榜才适合使用list类型存储，与定时计算的排行榜相对应的是实时计算的排行榜，list类型不能支持实时计算的排行榜。

关于redislist数据结构和redis list的数据结构的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。