摘要：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次。
而数据库的查问自身是ＩＯ操作，效率低，频率高也不好。
总而言之，一个网站总归是有大量的数据是用户共享的，然而如果每个用户都去数据库查问，效率就太低了。

解决：

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

特点：

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 {    @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]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)。

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