写点什么

三次给你讲清楚 Redis 之 Redis 是个啥

发布于: 2021 年 04 月 08 日

摘要:Redis 是一款基于键值对的 NoSQL 数据库,它的值支持多种数据结构:字符串(strings)、哈希(hashes)、列表(lists)、集合(sets)、有序集合(sorted sets)等。


本文分享自华为云社区《三次给你聊清楚Redis》之Redis是个啥》,原文作者:兔老大。


一、入门

Redis 是一款基于键值对的 NoSQL 数据库,它的值支持多种数据结构:字符串(strings)、哈希(hashes)、列表(lists)、集合(sets)、有序集合(sorted sets)等。


• Redis 将所有的数据都存放在内存中,所以它的读写性能十分惊人,用作数据库,缓存和消息代理。


• Redis 具有内置的复制,Lua 脚本,LRU 逐出,事务和不同级别的磁盘持久性,并通过 Redis Sentinel 和 Redis Cluster 自动分区提供了高可用性。


• Redis 典型的应用场景包括:缓存、排行榜、计数器、社交网络、消息队列等


1.1NoSql 入门概述 1)


1)单机 Mysql 的美好时代


瓶颈:


  • 数据库总大小一台机器硬盘内存放不下;

  • 数据的索引(B + tree)一个机器的运行内存放不下;

  • 访问量(读写混合)一个实例不能承受;


2)Memcached(缓存)+ MySql + 垂直拆分


通过缓存来缓解数据库的压力,优化数据库的结构和索引。


垂直拆分指的是:分成多个数据库存储数据(如:卖家库与买家库)。


3)MySql 主从复制读写分离


  1. 主从复制:主库来一条数据,从库立刻插入一条;

  2. 读写分离:读取(从库 Master),写(主库 Slave);


​4)分表分库+水平拆分+MySql 集群


  1. 主库的写压力出现瓶颈(行锁 InnoDB 取代表锁 MyISAM);

  2. 分库:根据业务相关紧耦合在同一个库,对不同的数据读写进行分库(如注册信息等不常改动的冷库与购物信息等热门库分开);

  3. 分表:切割表数据(例如 90W 条数据,id 1-30W 的放在 A 库,30W-60W 的放在 B 库,60W-90W 的放在 C 库);


MySql 扩展的瓶颈


  1. 大数据下 IO 压力大

  2. 表结构更改困难


常用的 Nosql


Redis

memcache

Mongdb 以

上几种 Nosql 请到各自的官网上下载并参考使用


Nosql 的核心功能点


KV(存储)

Cache(缓存)

Persistence(持久化)

……


1.2redis 的介绍和特点:


问题:


传统数据库:持久化存储数据。

solr 索引库:大量的数据的检索。

在实际开发中,高并发环境下,不同的用户会需要相同的数据。

因为每次请求,在后台我们都会创建一个线程来处理,这样造成,同样的数据从数据库中查询了 N 次。

而数据库的查询本身是IO操作,效率低,频率高也不好。

总而言之,一个网站总归是有大量的数据是用户共享的,但是如果每个用户都去数据库查询,效率就太低了。


解决:


将用户共享数据缓存到服务器的内存中。


特点:


1、基于键值对

2、非关系型(redis)关系型数据库:

存储了数据以及数据之间的关系,oracle,mysql

非关系型数据库:存储了数据,redis,mdb.

3、数据存储在内存中,服务器关闭后,持久化到硬盘中

4、支持主从同步


实现了缓存数据和项目的解耦。


redis 存储的数据特点:

大量数据

用户共享数据数据不经常修改。

查询数据


redis 的应用场景:

网站高并发的主页数据

网站数据的排名

消息订阅


1.3redis——数据结构和对象的使用介绍


redis 官网

微软写的windows下的redis


我们下载第一个,然后基本一路默认就行了。


安装后,服务自动启动,以后也不用自动启动。


​出现这个表示我们连接上了。


1.3.1 String


数据结构

struct sdshdr{    //记录buf数组中已使用字节的数量    int len;    //记录buf数组中未使用的数量    int free;    //字节数组,用于保存字符串    char buf[];}
复制代码

常见操作

127.0.0.1:6379> set hello worldOK127.0.0.1:6379> get hello"world"127.0.0.1:6379> del hello(integer) 1127.0.0.1:6379> get hello(nil)127.0.0.1:6379>
复制代码

应用场景

String 是最常用的一种数据类型,普通的 key/value 存储都可以归为此类,value 其实不仅是 String,也可以是数字:比如想知道什么时候封锁一个 IP 地址(访问超过几次)。INCRBY 命令让这些变得很容易,通过原子递增保持计数。


1.3.2 LIST


数据结构


typedef struct listNode{    //前置节点    struct listNode *prev;    //后置节点    struct listNode *next;    //节点的值    struct value;}
复制代码

常见操作

> lpush list-key item(integer) 1> lpush list-key item2(integer) 2> rpush list-key item3(integer) 3> rpush list-key item(integer) 4> lrange list-key 0 -11) "item2"2) "item"3) "item3"4) "item"> lindex list-key 2"item3"> lpop list-key"item2"> lrange list-key 0 -11) "item"2) "item3"3) "item"
复制代码

应用场景

Redis list 的应用场景非常多,也是 Redis 最重要的数据结构之一。我们可以轻松地实现最新消息排行等功能。Lists 的另一个应用就是消息队列,可以利用 Lists 的 PUSH 操作,将任务存在 Lists 中,然后工作线程再用 POP 操作将任务取出进行执行。


1.3.3 HASH


数据结构

dictht 是一个散列表结构,使用拉链法保存哈希冲突的 dictEntry。

typedef struct dictht{    //哈希表数组    dictEntry **table;    //哈希表大小    unsigned long size;    //哈希表大小掩码,用于计算索引值    unsigned long sizemask;    //该哈希表已有节点的数量    unsigned long used;}
typedef struct dictEntry{ //键 void *key; //值 union{ void *val; uint64_tu64; int64_ts64; } struct dictEntry *next;}
复制代码

Redis 的字典 dict 中包含两个哈希表 dictht,这是为了方便进行 rehash 操作。在扩容时,将其中一个 dictht 上的键值对 rehash 到另一个 dictht 上面,完成之后释放空间并交换两个 dictht 的角色。


typedef struct dict {    dictType *type;    void *privdata;    dictht ht[2];    long rehashidx; /* rehashing not in progress if rehashidx == -1 */    unsigned long iterators; /* number of iterators currently running */} dict;
复制代码

rehash 操作并不是一次性完成、而是采用渐进式方式,目的是为了避免一次性执行过多的 rehash 操作给服务器带来负担。


渐进式 rehash 通过记录 dict 的 rehashidx 完成,它从 0 开始,然后没执行一次 rehash 例如在一次 rehash 中,要把 dict[0] rehash 到 dict[1],这一次会把 dict[0] 上 table[rehashidx] 的键值对 rehash 到 dict[1] 上,dict[0] 的 table[rehashidx] 指向 null,并令 rehashidx++。


在 rehash 期间,每次对字典执行添加、删除、查找或者更新操作时,都会执行一次渐进式 rehash。

采用渐进式 rehash 会导致字典中的数据分散在两个 dictht 中,因此对字典的操作也会在两个哈希表上进行。例如查找时,先从 ht[0]查找,没有再查找 ht[1],添加时直接添加到 ht[1]中。


常见操作

> hset hash-key sub-key1 value1(integer) 1> hset hash-key sub-key2 value2(integer) 1> hset hash-key sub-key1 value1(integer) 0> hgetall hash-key1) "sub-key1"2) "value1"3) "sub-key2"4) "value2"> hdel hash-key sub-key2(integer) 1> hdel hash-key sub-key2(integer) 0> hget hash-key sub-key1"value1"> hgetall hash-key1) "sub-key1"2) "value1"
复制代码

1.3.4 SET


常见操作

> sadd set-key item(integer) 1> sadd set-key item2(integer) 1> sadd set-key item3(integer) 1> sadd set-key item(integer) 0> smembers set-key1) "item2"2) "item"3) "item3"> sismember set-key item4(integer) 0> sismember set-key item(integer) 1> srem set-key item(integer) 1> srem set-key item(integer) 0> smembers set-key1) "item2"2) "item3"
复制代码

应用场景

Redis 为集合提供了求交集、并集、差集等操作,故可以用来求共同好友等操作。

1.3.5 ZSET


数据结构


typedef struct zskiplistNode{//后退指针 struct zskiplistNode *backward;//分值 double score;//成员对象 robj *obj;//层 struct zskiplistLever{//前进指针 struct zskiplistNode *forward;//跨度 unsigned int span;}lever[];}


typedef struct zskiplist{    //表头节点跟表尾结点    struct zskiplistNode *header, *tail;    //表中节点的数量    unsigned long length;    //表中层数最大的节点的层数    int lever;}
复制代码


跳跃表,基于多指针有序链实现,可以看作多个有序链表。


与红黑树等平衡树相比,跳跃表具有以下优点:


  • 插入速度非常快速,因为不需要进行旋转等操作来维持平衡性。

  • 更容易实现。

  • 支持无锁操作。


常见操作

> zadd zset-key 728 member1(integer) 1> zadd zset-key 982 member0(integer) 1> zadd zset-key 982 member0(integer) 0> zrange zset-key 0 -11) "member1"2) "member0"> zrange zset-key 0 -1 withscores1) "member1"2) "728"3) "member0"4) "982"> zrangebyscore zset-key 0 800 withscores1) "member1"2) "728"> zrem zset-key member1(integer) 1> zrem zset-key member1(integer) 0> zrange zset-key 0 -1 withscores1) "member0"2) "982"
复制代码


应用场景

以某个条件为权重,比如按顶的次数排序。ZREVRANGE 命令可以用来按照得分来获取前 100 名的用户,ZRANK 可以用来获取用户排名,非常直接而且操作容易。


Redis sorted set 的使用场景与 set 类似,区别是 set 不是自动有序的,而 sorted set 可以通过用户额外提供一个优先级(score)的参数来为成员排序,并且是插入有序的,即自动排序。

1.4 Spring 整合 Redis

引入依赖

- spring-boot-starter-data-redis

<dependency>			<groupId>org.springframework.boot</groupId>			<artifactId>spring-boot-starter-data-redis</artifactId>		</dependency>
复制代码


配置 Redis

- 配置数据库参数

# RedisPropertiesspring.redis.database=11#第11个库,这个随便spring.redis.host=localhostspring.redis.port=6379#端口
复制代码

- 编写配置类,构造 RedisTemplate

这个 springboot 已经帮我们配了,但是默认 object,我想改成 string


import org.springframework.context.annotation.Bean;import org.springframework.context.annotation.Configuration;import org.springframework.data.redis.connection.RedisConnectionFactory;import org.springframework.data.redis.core.RedisTemplate;import org.springframework.data.redis.serializer.RedisSerializer;


@Configurationpublic class RedisConfig {


@Beanpublic RedisTemplate<String, Object> redisTemplate(RedisConnectionFactory factory) {    RedisTemplate<String, Object> template = new RedisTemplate<>();    template.setConnectionFactory(factory);
// 设置key的序列化方式 template.setKeySerializer(RedisSerializer.string()); // 设置value的序列化方式 template.setValueSerializer(RedisSerializer.json()); // 设置hash的key的序列化方式 template.setHashKeySerializer(RedisSerializer.string()); // 设置hash的value的序列化方式 template.setHashValueSerializer(RedisSerializer.json());
template.afterPropertiesSet(); return template;}
复制代码


}


访问 Redis

- redisTemplate.opsForValue()

- redisTemplate.opsForHash()

- redisTemplate.opsForList()

- redisTemplate.opsForSet()

- redisTemplate.opsForZSet()



@RunWith(SpringRunner.class)@SpringBootTest@ContextConfiguration(classes = CommunityApplication.class)public class RedisTests {


@Autowiredprivate RedisTemplate redisTemplate;
@Testpublic void testStrings() { String redisKey = "test:count";
redisTemplate.opsForValue().set(redisKey, 1);
System.out.println(redisTemplate.opsForValue().get(redisKey)); System.out.println(redisTemplate.opsForValue().increment(redisKey)); System.out.println(redisTemplate.opsForValue().decrement(redisKey));}
@Testpublic void testHashes() { String redisKey = "test:user";
redisTemplate.opsForHash().put(redisKey, "id", 1); redisTemplate.opsForHash().put(redisKey, "username", "zhangsan");
System.out.println(redisTemplate.opsForHash().get(redisKey, "id")); System.out.println(redisTemplate.opsForHash().get(redisKey, "username"));}
@Testpublic void testLists() { String redisKey = "test:ids";
redisTemplate.opsForList().leftPush(redisKey, 101); redisTemplate.opsForList().leftPush(redisKey, 102); redisTemplate.opsForList().leftPush(redisKey, 103);
System.out.println(redisTemplate.opsForList().size(redisKey)); System.out.println(redisTemplate.opsForList().index(redisKey, 0)); System.out.println(redisTemplate.opsForList().range(redisKey, 0, 2));
System.out.println(redisTemplate.opsForList().leftPop(redisKey)); System.out.println(redisTemplate.opsForList().leftPop(redisKey)); System.out.println(redisTemplate.opsForList().leftPop(redisKey));}
@Testpublic void testSets() { String redisKey = "test:teachers";
redisTemplate.opsForSet().add(redisKey, "刘备", "关羽", "张飞", "赵云", "诸葛亮");
System.out.println(redisTemplate.opsForSet().size(redisKey)); System.out.println(redisTemplate.opsForSet().pop(redisKey)); System.out.println(redisTemplate.opsForSet().members(redisKey));}
@Testpublic void testSortedSets() { String redisKey = "test:students";
redisTemplate.opsForZSet().add(redisKey, "唐僧", 80); redisTemplate.opsForZSet().add(redisKey, "悟空", 90); redisTemplate.opsForZSet().add(redisKey, "八戒", 50); redisTemplate.opsForZSet().add(redisKey, "沙僧", 70); redisTemplate.opsForZSet().add(redisKey, "白龙马", 60);
System.out.println(redisTemplate.opsForZSet().zCard(redisKey)); System.out.println(redisTemplate.opsForZSet().score(redisKey, "八戒")); System.out.println(redisTemplate.opsForZSet().reverseRank(redisKey, "八戒")); System.out.println(redisTemplate.opsForZSet().reverseRange(redisKey, 0, 2));}
@Testpublic void testKeys() { redisTemplate.delete("test:user");
System.out.println(redisTemplate.hasKey("test:user"));
redisTemplate.expire("test:students", 10, TimeUnit.SECONDS);}
复制代码


}

这样还是稍微有点麻烦,我们其实可以绑定 key


// 多次访问同一个key@Testpublic void testBoundOperations() {    String redisKey = "test:count";    BoundValueOperations operations = redisTemplate.boundValueOps(redisKey);    operations.increment();    operations.increment();    operations.increment();    operations.increment();    operations.increment();    System.out.println(operations.get());}
复制代码


二、数据结构原理总结


这部分在我看来是最有意思的,我们有必要了解底层数据结构的实现,这也是我最感兴趣的。比如,


  • 你知道 redis 中的字符串怎么实现的吗?为什么这么实现?

  • 你知道 redis 压缩列表是什么算法吗?

  • 你知道 redis 为什么抛弃了红黑树反而采用了跳表这种新的数据结构吗?

  • 你知道 hyperloglog 为什么用如此小的空间就可以有这么好的统计性能和准确性吗?

  • 你知道布隆过滤器为什么这么有效吗?有没有数学证明过?

  • 你是否还能很快写出来快排?或者不断优化性能的排序?

  • 是不是只会调库了甚至库函数怎么实现的都不知道?真的就是快排?


包括数据库,持久化,处理事件、客户端服务端、事务的实现、发布和订阅等功能的实现,也需要了解。


2.1 数据结构和对象的实现


1) 字符串


redis 并未使用传统的 c 语言字符串表示,它自己构建了一种简单的动态字符串抽象类型。


在 redis 里,c 语言字符串只会作为字符串字面量出现,用在无需修改的地方。


当需要一个可以被修改的字符串时,redis 就会使用自己实现的 SDS(simple dynamic string)。比如在 redis 数据库里,包含字符串的键值对底层都是 SDS 实现的,不止如此,SDS 还被用作缓冲区(buffer):比如 AOF 模块中的 AOF 缓冲区以及客户端状态中的输入缓冲区。


下面来具体看一下 sds 的实现:

struct sdshdr{    int len;//buf已使用字节数量(保存的字符串长度)    int free;//未使用的字节数量    char buf[];//用来保存字符串的字节数组};
复制代码

sds 遵循 c 中字符串以'\0'结尾的惯例,这一字节的空间不算在 len 之内。这样的好处是,我们可以直接重用 c 中的一部分函数。比如 printf;


sds 相对 c 的改进


获取长度:c 字符串并不记录自身长度,所以获取长度只能遍历一遍字符串,redis 直接读取 len 即可。


缓冲区安全:c 字符串容易造成缓冲区溢出,比如:程序员没有分配足够的空间就执行拼接操作。而 redis 会先检查 sds 的空间是否满足所需要求,如果不满足会自动扩充。


内存分配:由于 c 不记录字符串长度,对于包含了 n 个字符的字符串,底层总是一个长度 n+1 的数组,每一次长度变化,总是要对这个数组进行一次内存重新分配的操作。因为内存分配涉及复杂算法并且可能需要执行系统调用,所以它通常是比较耗时的操作。


redis 内存分配:


1、空间预分配:如果修改后大小小于 1MB,程序分配和 len 大小一样的未使用空间,如果修改后大于 1MB,程序分配 1MB 的未使用空间。修改长度时检查,够的话就直接使用未使用空间,不用再分配。


2、惰性空间释放:字符串缩短时不需要释放空间,用 free 记录即可,留作以后使用。


二进制安全


c 字符串除了末尾外,不能包含空字符,否则程序读到空字符会误以为是结尾,这就限制了 c 字符串只能保存文本,二进制文件就不能保存了。


而 redis 字符串都是二进制安全的,因为有 len 来记录长度。


2) 链表


作为一种常用数据结构,链表内置在很多高级语言中,因为 c 并没有,所以 redis 实现了自己的链表。


链表在 redis 也有一定的应用,比如列表键的底层实现之一就是链表。(当列表键包含大量元素或者元素都是很长的字符串时)发布与订阅、慢查询、监视器等功能也用到了链表。


具体实现:

//redis的节点使用了双向链表结构typedef struct listNode {    // 前置节点    struct listNode *prev;    // 后置节点    struct listNode *next;    // 节点的值    void *value;} listNode;
复制代码


//其实学过数据结构的应该都实现过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;
复制代码

总结一下 redis 链表特性:


双端、无环、带长度记录


多态:使用 void* 指针来保存节点值, 可以通过 dup 、 free 、 match 为节点值设置类型特定函数, 可以保存不同类型的值。

3)字典


其实字典这种数据结构也内置在很多高级语言中,但是 c 语言没有,所以 redis 自己实现了。应用也比较广泛,比如 redis 的数据库就是字典实现的。不仅如此,当一个哈希键包含的键值对比较多,或者都是很长的字符串,redis 就会用字典作为哈希键的底层实现。


来看看具体是实现:

//redis的字典使用哈希表作为底层实现typedef struct dictht {    // 哈希表数组    dictEntry **table;// 哈希表大小    unsigned long size;    // 哈希表大小掩码,用于计算索引值    // 总是等于 size - 1    unsigned long sizemask;
// 该哈希表已有节点的数量 unsigned long used;
} dictht;
复制代码


table 是一个数组, 数组中的每个元素都是一个指向 dictEntry 结构的指针, 每个 dictEntry 结构保存着一个键值对


图为一个大小为 4 的空哈希表。我们接着就来看 dictEntry 的实现:

typedef struct dictEntry {    // 键    void *key;    // 值    union {void *val;        uint64_t u64;        int64_t s64;    } v;
// 指向下个哈希表节点,形成链表 struct dictEntry *next;} dictEntry;
复制代码

(v 可以是一个指针, 或者是一个 uint64_t 整数, 又或者是一个 int64_t 整数。)


next 就是解决键冲突问题的,冲突了就挂后面,这个学过数据结构的应该都知道吧,不说了。


下面我们来说字典是怎么实现的了。

typedef struct dict {    // 类型特定函数    dictType *type;    // 私有数据    void *privdata;    // 哈希表    dictht ht[2];    // rehash 索引    int rehashidx; //* rehashing not in progress if rehashidx == -1 } dict;
复制代码

type 和 privdata 是对不同类型的键值对, 为创建多态字典而设置的:


type 指向 dictType , 每个 dictType 保存了用于操作特定类型键值对的函数, 可以为用途不同的字典设置不同的类型特定函数。


而 privdata 属性则保存了需要传给那些类型特定函数的可选参数。


dictType 就暂时不展示了,不重要而且字有点多。。。还是讲有意思的东西吧


rehash(重新散列)


随着我们不断的操作,哈希表保存的键值可能会增多或者减少,为了让哈希表的负载因子维持在合理的范围内,有时需要对哈希表进行合理的扩展或者收缩。 一般情况下, 字典只使用 ht[0] 哈希表, ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。


redis 字典哈希 rehash 的步骤如下:


1)为 ht[1]分配合理空间:如果是扩展操作,大小为第一个大于等于 ht[0]used2 的,2 的 n 次幂。


如果是收缩操作,大小为第一个大于等于 ht[0]*used 的,2 的 n 次幂。


2)将 ht[0]中的数据 rehash 到 ht[1]上。


3)释放 ht[0],将 ht[1]设置为 ht[0],ht[1]创建空表,为下次做准备。


渐进 rehash


数据量特别大时,rehash 可能对服务器造成影响。为了避免,服务器不是一次性 rehash 的,而是分多次。


我们维持一个变量 rehashidx,设置为 0,代表 rehash 开始,然后开始 rehash,在这期间,每个对字典的操作,程序都会把索引 rehashidx 上的数据移动到 ht[1]。


随着操作不断执行,最终我们会完成 rehash,设置 rehashidx 为-1.


需要注意:rehash 过程中,每一次增删改查也是在两个表进行的。

4)整数集合


整数集合(intset)是 Redis 用于保存整数值的集合抽象数据结构, 可以保存 int16_t 、 int32_t 、 int64_t 的整数值, 并且保证集合中不会出现重复元素。


实现较为简单:

typedef struct intset {    // 编码方式    uint32_t encoding;    // 集合包含的元素数量    uint32_t length;    // 保存元素的数组    int8_t contents[];} intset;
复制代码

各个项在数组中从小到大有序地排列, 并且数组中不包含任何重复项。


虽然 intset 结构将 contents 属性声明为 int8_t 类型的数组, 但实际上 contents 数组并不保存任何 int8_t 类型的值 —— contents 数组的真正类型取决于 encoding 属性的值:


  • 如果 encoding 属性的值为 INTSET_ENC_INT16 , 那么 contents 就是一个 int16_t 类型的数组, 数组里的每个项都是一个 int16_t 类型的整数值 (最小值为 -32,768 ,最大值为 32,767 )。

  • 如果 encoding 属性的值为 INTSET_ENC_INT32 , 那么 contents 就是一个 int32_t 类型的数组, 数组里的每个项都是一个 int32_t 类型的整数值 (最小值为 -2,147,483,648 ,最大值为 2,147,483,647 )。

  • 如果 encoding 属性的值为 INTSET_ENC_INT64 , 那么 contents 就是一个 int64_t 类型的数组, 数组里的每个项都是一个 int64_t 类型的整数值 (最小值为 -9,223,372,036,854,775,808 ,最大值为 9,223,372,036,854,775,807 )。


升级


c 语言是静态类型语言,不允许不同类型保存在一个数组。这样第一,灵活性较差,第二,有时会用掉不必要的内存。


比如用 long long 储存 1


为了提高整数集合的灵活性和节约内存,我们引入升级策略。


当我们要将一个新元素添加到集合里, 并且新元素类型比集合现有元素的类型都要长时, 集合需要先进行升级。


分为三步进行:


  1. 根据新元素的类型, 扩展整数集合底层数组的空间大小, 并为新元素分配空间。

  2. 将底层数组现有的所有元素都转换成与新元素相同的类型, 并将类型转换后的元素放置到正确的位上

  3. 将新元素添加到底层数组里面。


因为每次添加新元素都可能会引起升级, 每次升级都要对已有元素类型转换, 所以添加新元素的时间复杂度为 O(N) 。


因为引发升级的新元素比原数据都长,所以要么他是最大的,要么他是最小的。我们把它放在开头或结尾即可。


降级


略略略,不管你们信不信,整数集合不支持降级操作。。我也不知道为啥

5)压缩


列表压缩列表是列表键和哈希键的底层实现之一。


当一个列表键只包含少量列表项,并且列表项都是小整数或者短字符串,redis 就会用压缩列表做列表键底层实现。


压缩列表是 Redis 为了节约内存而开发的, 由一系列特殊编码的连续内存块组成的顺序型(sequential)数据结构。


一个压缩列表可以包含任意多个节点(entry), 每个节点可以保存一个字节数组或者一个整数值。


具体实现:



​具体说一下 entry:


由三个部分组成:


1、previous_entry_length:记录上一个节点的长度,这样我们就可以从最后一路遍历到开头。


2、encoding:记录了 content 所保存的数据类型和长度。(具体编码不写了,不重要)


3、content:保存节点值,可以是字节数组或整数。(具体怎么压缩的等我搞明白再补)


连锁更新


前面说过, 每个节点的 previous_entry_length 属性都记录了前一个节点的长度:


  • 如果前一节点的长度< 254 KB, 那么 previous_entry_length 需要用 1 字节长的空间

  • 如果前一节点的长度>=254 KB, 那么 previous_entry_length 需要用 5 字节长的空间


现在, 考虑这样一种情况: 在一个压缩列表中, 有多个连续的、长度介于 250 字节到 253 字节之间的节点 ,这时, 如果我们将一个长度大于等于 254 字节的新节点 new 设置为压缩列表的表头节点。。。。


然后脑补一下,就会导致连锁扩大每个节点的空间对吧?e(i)因为 e(i-1)的扩大而扩大,i+1 也是如此,以此类推... ...


删除节点同样会导致连锁更新。


这个事情只是想说明一个问题:插入删除操作的最坏时间复杂度其实是 o(n*n),因为每更新一个节点都要 o(n)。


但是,也不用太过担心,因为这种特殊情况并不多见,这些命令的平均复杂度依旧是 o(n)。


点击关注,第一时间了解华为云新鲜技术~

发布于: 2021 年 04 月 08 日阅读数: 47
用户头像

提供全面深入的云计算技术干货 2020.07.14 加入

华为云开发者社区,提供全面深入的云计算前景分析、丰富的技术干货、程序样例,分享华为云前沿资讯动态,方便开发者快速成长与发展,欢迎提问、互动,多方位了解云计算! 传送门:https://bbs.huaweicloud.com/

评论

发布
暂无评论
三次给你讲清楚Redis之Redis是个啥