redis数据结构（redis数据结构详解）

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

本文目录一览：

• 1、Redis的五种数据结构及其底层实现原理
• 2、Redis底层数据结构
• 3、redis的基本数据结构有哪些，都有什么应用
• 4、redis 常见数据结构以及使用场景分析?
• 5、redis数据结构

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)，每个节点可以保存一个字节数组或一个整数值。

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

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

Redis底层数据结构

Redis中值的数据结构有String（字符串）、List（列表）、Hash（哈希）、Set（集合）和 Sorted Set（有序集合）五种，使用可参考 。

而底层数据结构一共有 6 种，分别是简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组。它们和数据类型的对应关系如下图所示：

可以看到，String 类型的底层实现只有一种数据结构，也就是简单动态字符串。而 List、Hash、Set 和 Sorted Set 这四种数据类型，都有两种底层实现结构。通常情况下，我们会把这四种类型称为集合类型，它们的特点是一个键对应了一个集合的数据。

为了实现从键到值的快速访问，Redis 使用了一个哈希表来保存所有键值对。一个哈希表，其实就是一个数组，数组的每个元素称为一个哈希桶。哈希桶中的元素保存的并不是值本身，而是指向具体值的指针。

这也就是说，不管值是 String，还是集合类型，哈希桶中的元素都是指向它们的指针。在下图中，可以看到，哈希桶中的歼明 entry 元素中保存了 key和 value指针，分别指向了实际的键和值。

哈希冲突，也就是指，两个 key 的哈希值和哈希桶计算对应关系时，正好落在了同一个哈希桶中。毕竟，哈希桶的个数通常要少于 key 的数量，这也就是说，难免会有一些 key 的哈希值对应到了同一个哈希桶中。Redis 解决哈希冲突的方式，就是 链式哈希 。链式哈希也很容易理解，就是指同一个哈希桶中的多个元素用一个链表来保存，它们之间依次用指针连接。

如下图所示：entry1、entry2 和 entry3 都需要保存在哈希桶 3 中，导致了哈希冲突。此时，entry1 元素会通过一个 next指针指向 entry2，同样，entry2 也会通过 next指针指向 entry3。这样一来，即使哈希桶 3 中的元素有 100 个，我们也可以通过 entry 元素中的指针，把它们连起来。

其实，为了使 rehash 操作更高效，Redis 默认使用了两个全局哈希表：哈希表 1 和哈希表 2。一开始，当你刚插入数据时，默认使用哈希表 1，此时的哈希表 2 并没有被分配空间。随着数据逐步增多，Redis 开始执行 rehash，这个过程分为三步：

这个过程看似简单，但是第二步涉及大量的数据拷贝，如果一次性悔蔽把哈希表 1 中的数据都迁移完，会造成 Redis 线程阻塞，无法服务其他请求。此时，Redis 就无法快速访问数据了。为了避免这个问题，Redis 采用了 渐进式 rehash 。

简单来说就是在第二步拷贝数据时，Redis 仍然正常处理客户端请求，每处理一个请求时，从哈希表 1 中的第一个索引位置开始，顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中；等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个索引位置的 entries。如下图所示：

对于 String 类型来说，找到哈希桶就能直接增删改查了碧改州，所以，哈希表的 O(1) 操作复杂度也就是它的复杂度了。

一个集合类型的值，第一步是通过全局哈希表找到对应的哈希桶位置，第二步是在集合中再增删改查。首先，操作复杂度与集合的底层数据结构有关。例如，使用哈希表实现的集合，要比使用链表实现的集合访问效率更高。其次，操作效率和这些操作本身的执行特点有关，比如读写一个元素的操作要比读写所有元素的效率高。

String类型对应的简单动态字符串到后面再说，集合类型的底层数据结构主要有 5 种：整数数组、双向链表、哈希表、压缩列表和跳表。

整数数组和双向链表也很常见，它们的操作特征都是顺序读写，也就是通过数组下标或者链表的指针逐个元素访问，操作复杂度基本是 O(N)，操作效率比较低；压缩列表和跳表我们平时接触得可能不多，但它们也是 Redis 重要的数据结构。

压缩列表 实际上类似于一个数组，数组中的每一个元素都对应保存一个数据。和数组不同的是，压缩列表在表头有三个字段 zlbytes、zltail 和 zllen，分别表示列表长度、列表尾的偏移量和列表中的 entry 个数；压缩列表在表尾还有一个 zlend，表示列表结束。

跳表 在链表的基础上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位，如下图所示：

Redis 之所以能快速操作键值对，一方面是因为 O(1) 复杂度的哈希表被广泛使用，包括 String、Hash 和 Set，它们的操作复杂度基本由哈希表决定，另一方面，Sorted Set 也采用了 O(logN) 复杂度的跳表。不过，集合类型的范围操作，因为要遍历底层数据结构，复杂度通常是 O(N)。

不能忘了复杂度较高的 List 类型，它的两种底层实现结构：双向链表和压缩列表的操作复杂度都是 O(N)。因此，因地制宜地使用 List 类型。例如，既然它的 POP/PUSH 效率很高，那么就将它主要用于 FIFO 队列场景，而不是作为一个可以随机读写的集合。

[img]

redis的基本数据结构有哪些，都有什么应用

1. String——字符串

String 数据结构是简单的 key-value 类型，value 不仅可以是 String，也可以是数字（当数字类型用 Long

可以表示的时候encoding 就是整型，其他都存储在 sdshdr 当做字符串）。使用 Strings 类型，可以完全实现目前 Memcached

的功能，并且效率更高。还可以享受 Redis 的定时持久化（可以选择 RDB 模式或者 AOF 模式），操作日志及 Replication 等功能。除了提供与

Memcached 一样的 get、set、incr、decr 等操作外，Redis 还提供了下面一些操作：

2. Hash——字典

在 Memcached 中，我们经常将一些结构化的信息打包成 hashmap，在客户端序列化后存储为一个字符串的值（一般是 JSON

格式），比如用户的昵称、年龄、性别、积分等。这时候在需要修改其中某一项时，通常需要将字符串（JSON）取出来，然后进行反序列化，修改某一项的值，再序列化成字符串（JSON）存储回去。简单修改一个属性就干这么多事情，消耗必定是很大的，也不适用于一些可能并发操作的场合（比如两个并发的操贺乱旦作都需要修改积分）。而

Redis 的 Hash 结构可以使你像在数据库中 Update 一个属性一样只修改某一项属性值。

3. List——列表

List 说白了就是链表（redis 使用双端链表实现的 List），相信学过数据结构知识的人都应该能理解其结构。使用 List

结构，我们可以轻松地实现最新消息排行等功能（比如新浪微博的 TimeLine ）。List 的另一个应用就是消息队列，可以利用 List 的 *PUSH

操作，将任务存在 List 中，然后工作线程再用 POP 操作将任务取出进行执行。Redis 还提供了操作 List 中某一段元素的

API，你可以直接查询，删除 List 中某一段的元素。

4. Set——集合

Set 就是一个集合，集合的概念就是一堆不重复值的组合。利用 Redis 提供的 Set

数据结构，可以存储一禅扰些集合性的数据。比如在微博应用中，可以将一个用户所有的关注人存在一个集合中，将其所有粉丝存在一个集合。因为 Redis

非常人性化的为集合提供了求交集、并集、差集等操作，那么就可以非常方便的实现如共同关注、共同喜好、二度好友等功能，对上面的所有集合操作，你还可以使用不同的命令选择将结果返回给客户端还是存集到一个新的集合中。

1.共同好友、二度好友

2.利用唯一性，可以统计访问网站的所有独立 IP

3.好友推荐的时候，根据 tag 求交集，大于某个

threshold 就可以推荐

5. Sorted Set——有序集合

和Sets相比，Sorted Sets是将 Set 中的元素增加了一个权重参数 score，使得集合中的元素能够按 score

进行有序排列，比如一个存储全班同学成绩的 Sorted Sets，其集合 value 可以是同学的学号，而 score

就可以是其考试得分，这样在数据插入集合的时候，就已经进行了天然的排序。另外还可以用 Sorted Sets 来做带权重的队列，比如普通消息的 score

为1，重要消息的 score 为2，然后工作线程可以选择按 score 的倒序来获取工作任务。让重要的任务优先执行。陪饥

redis 常见数据结构以及使用场景分析?

Redis 提供了 5种数据结构，每一种数据结构有各种的使用场段弯景。

1、String 字符串

字符串类型是 Redis 最基础的数据结构，首先键都是字符串类型，而且 其他几种数据结构都是在字符串类型基础上构建的，我们常使用的 set key value 命令就是字符串。常用在缓存、计数、共享Session、限速等。

2、Hash 哈希

在Redis中，哈希类型是指键值本身又是一个键值对 结构，形如value={{field1，value1}，...{fieldN，valueN}}，添加命令：hset key field value。哈希可以用来存陵燃友放用户信息，比如实现购物车

3、List 列表

列表（list）类型是用来存储多个有序的字符串。可以做简单的消息队列的功能。另外，可以利用 lrange 命令，做基于 Redis的分页功能，性能极佳，用户体验好。

4、Set 集合

集合（set）类型也是用来保存多个的字符串元素，但和列表类型不一 样的是，集合中不允许有重复元素，并且集合中的元素是无序的，不能通过 索引下标获取元素。利用 Set 的交集尺槐、并集、差集等操作，可以计算共同喜好，全部的喜好，自己独有的喜好等功能。

5、Sorted Set 有序集合

Sorted Set 多了一个权重参数 Score，集合中的元素能够按 Score 进行排列。可以做排行榜应用，取 TOP N 操作。

redis数据结构

redis数据结构

Redis是一种存储key-value的内存型数据库，它的key都是字符串类型，value支持存储5种类型的数据：String（字符串类型）、List（列表类型）、Hash（哈希表类型、即key-value类型）、Set（无序集合类型，元素不可重复）、Zset（有序集合类型，元素不可重复）。

针对这5种数据类型，Redis在底层都是使用的redisObject对象表示的。redisObject有3个重要的属性：type、encoding、ptr。

其中，type表示value的数据类型，也就是我们上面说的5种数据类型（REDIS_STRING、REDIS_LIST、REDIS_HASH、REDIS_SET、REDIS_ZSET）；encoding表示value的编码，即底层使用了哪种数据结构；ptr是一个指向保存value的底层数据结构的指针。

其中type和ptr属性不用做过多的解释，一看就知道什么意思，本篇文章主要分析value的encoding编码，也就是不同数据类型的value对应的底层数据结构是什么以及数蔽余据结构的原理分析。

Redis（Remote Dictionary Server )，即远程字典服务，是一个开源的使用ANSI C语言编写、支持网络、磨清可基于内存亦可持久瞎并前化的日志型、Key-Value数据库，并提供多种语言的API。

redis是一个key-value存储系统。和Memcached类似，它支持存储的value类型相对更多，包括string(字符串)、list(链表)、set(集合)、zset(sorted set --有序集合)和hash（哈希类型）。这些数据类型都支持push/pop、add/remove及取交集并集和差集及更丰富的操作，而且这些操作都是原子性的。

在此基础上，redis支持各种不同方式的排序。与memcached一样，为了保证效率，数据都是缓存在内存中。区别的是redis会周期性的把更新的数据写入磁盘或者把修改操作写入追加的记录文件，并且在此基础上实现了master-slave(主从)同步。

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