关于redis:三次给你讲清楚Redis之Redis是个啥

46次阅读

共计 14066 个字符，预计需要花费 36 分钟才能阅读完成。

摘要：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）单机 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 world
OK
127.0.0.1:6379> get hello
"world"
127.0.0.1:6379> del hello
(integer) 1
127.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 -1
1) "item2"
2) "item"
3) "item3"
4) "item"
> lindex list-key 2
"item3"
> lpop list-key
"item2"
> lrange list-key 0 -1
1) "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-key
1) "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-key
1) "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-key
1) "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-key
1) "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 -1
1) "member1"
2) "member0"
> zrange zset-key 0 -1 withscores
1) "member1"
2) "728"
3) "member0"
4) "982"
> zrangebyscore zset-key 0 800 withscores
1) "member1"
2) "728"
> zrem zset-key member1
(integer) 1
> zrem zset-key member1
(integer) 0
> zrange zset-key 0 -1 withscores
1) "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

  • 配置数据库参数
# RedisProperties
spring.redis.database=11# 第 11 个库，这个轻易
spring.redis.host=localhost
spring.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;

@Configuration
public class RedisConfig {

    @Bean
    public 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 {

    @Autowired
    private RedisTemplate redisTemplate;

    @Test
    public 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));
    }

    @Test
    public 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"));
    }

    @Test
    public 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));
    }

    @Test
    public 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));
    }

    @Test
    public 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));
    }

    @Test
    public void testKeys() {redisTemplate.delete("test:user");

        System.out.println(redisTemplate.hasKey("test:user"));

        redisTemplate.expire("test:students", 10, TimeUnit.SECONDS);
    }
}

这样还是略微有点麻烦，咱们其实能够绑定 key

 // 屡次拜访同一个 key
    @Test
    public 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]used 2 的，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)。

点击关注，第一工夫理解华为云陈腐技术~

正文完
redis
发表至： redis
2021-04-08
 0
关于redis:Redis-系列redis-学习十四sortedset-初步探究梳理
关于redis:聊聊Redis的数据热点问题
关于redis:Redis系列之如何高效使用
关于redis:使用-Redis-实现一个轻量级的搜索引擎牛x啊