redis学习(上)
(0)

什么是NoSQL

Nosql = not only sql(不仅仅是SQL)

关系型数据库:列+行,同一个表下数据的结构是一样的。

非关系型数据库:数据存储没有固定的格式,并且可以进行横向扩展。

NoSQL泛指非关系型数据库,随着web2.0互联网的诞生,传统的关系型数据库很难对付web2.0大数据时代!尤其是超大规模的高并发的社区,暴露出来很多难以克服的问题,NoSQL在当今大数据环境下发展的十分迅速,Redis是发展最快的。

传统RDBMS和NoSQL

RDBMS
 - 组织化结构
 - 固定SQL
 - 数据和关系都存在单独的表中(行列)
 - DML(数据操作语言)、DDL(数据定义语言)等
 - 严格的一致性(ACID): 原子性、一致性、隔离性、持久性
 - 基础的事务
NoSQL
 - 不仅仅是数据
 - 没有固定查询语言
 - 键值对存储(redis)、列存储(HBase)、文档存储(MongoDB)、图形数据库(不是存图形,放的是关系)(Neo4j)
 - 最终一致性(BASE):基本可用、软状态/柔性事务、最终一致性

redis是什么

Redis = Remote Dictionary Server,即远程字典服务。

是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库,并提供多种语言的API。

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

redis.png

redis五大基本类型

Redis是一个开源,内存存储的数据结构服务器,可用作数据库,高速缓存和消息队列代理。它支持字符串、哈希表、列表、集合、有序集合,位图,hyperloglogs等数据类型。内置复制、Lua脚本、LRU收回、事务以及不同级别磁盘持久化功能,同时通过Redis Sentinel提供高可用,通过Redis Cluster提供自动分区。

由于redis类型大家很熟悉,且网上命令使用介绍很多,下面重点介绍五大基本类型的底层数据结构与应用场景,以便当开发时,可以熟练使用redis。

1 String(字符串)

Redis 里的字符串是动态字符串,会根据实际情况动态调整。类似于 Go 里面的切片-slice,如果长度不够则自动扩容。至于如何扩容,方法大致如下:当 length 小于 1M 的时候,扩容规则将目前的字符串翻倍;如果 length 大于 1M 的话,则每次只会扩容 1M,直到达到 512M。

string.png

应用场景

1、缓存功能:String字符串是最常用的数据类型,不仅仅是redis,各个语言都是最基本类型,因此,利用redis作为缓存,配合其它数据库作为存储层,利用redis支持高并发的特点,可以大大加快系统的读写速度、以及降低后端数据库的压力。

2、计数器:许多系统都会使用redis作为系统的实时计数器,可以快速实现计数和查询的功能。而且最终的数据结果可以按照特定的时间落地到数据库或者其它存储介质当中进行永久保存。

3、统计多单位的数量:eg,uid:gongming count:0 根据不同的uid更新count数量。

4、共享用户session:用户重新刷新一次界面,可能需要访问一下数据进行重新登录,或者访问页面缓存cookie,这两种方式做有一定弊端,1)每次都重新登录效率低下 2)cookie保存在客户端,有安全隐患。这时可以利用redis将用户的session集中管理,在这种模式只需要保证redis的高可用,每次用户session的更新和获取都可以快速完成。大大提高效率。

List(列表)

Redis 里的 List 是一个链表,由于链表本身插入和删除比较块,但是查询的效率比较低,所以常常被用做异步队列。Redis 里的 List 设计非常牛,当数据量比较小的时候,数据结构是压缩链表,而当数据量比较多的时候就成为了快速链表。

可运用的场景:在业务中异步队列使用 rpush/lpush 操作队列,使用 lpop 和 rpop 出队列,具体结构如下图所示:

list.png

应用场景

1、消息队列:reids的链表结构,可以轻松实现阻塞队列,可以使用左进右出的命令组成来完成队列的设计。比如:数据的生产者可以通过Lpush命令从左边插入数据,多个数据消费者,可以使用BRpop命令阻塞的“抢”列表尾部的数据。

2、文章列表或者数据分页展示的应用。比如,我们常用的博客网站的文章列表,当用户量越来越多时,而且每一个用户都有自己的文章列表,而且当文章多时,都需要分页展示,这时可以考虑使用redis的列表,列表不但有序同时还支持按照范围内获取元素,可以完美解决分页查询功能。大大提高查询效率。

Set(集合)

Redis 中的 set 是一个无序 Map,由于 Go 中没有 set 结构,所以这里只能类比 Java 中的 HashSet 概念。Redis 的 set 底层也是一个 Map 结构,不同于 Java 的是:alue 是一个 NULL。由于 set 的特性,它可以用于去重逻辑,这一点在 Java 中也经常使用。

应用场景

1、标签:比如我们博客网站常常使用到的兴趣标签,把一个个有着相同爱好,关注类似内容的用户利用一个标签把他们进行归并。

2、共同好友功能,共同喜好,或者可以引申到二度好友之类的扩展应用。

3、统计网站的独立IP。利用set集合当中元素不唯一性,可以快速实时统计访问网站的独立IP。

数据结构

set的底层结构相对复杂写,使用了intset和hashtable两种数据结构存储,intset可以理解为数组。

sorted set(有序集合)

Redis 中的字典类型大家不陌生,也许其他语言都有这种结构(python,Java,Go), hash 的扩容 rehash 过程和 Go 里面的设计颇有类似,也就是维护了两个 hash 结构,如果需要扩容的时候,就把新的数据写入新字典中,然后后端起一个线程来逐步迁移,总体上来说就是采用了空间换时间的思想。

set.png

应用场景

1、 排行榜:有序集合经典使用场景。例如视频网站需要对用户上传的视频做排行榜,榜单维护可能是多方面:按照时间、按照播放量、按照获得的赞数等。

2、用Sorted Sets来做带权重的队列,比如普通消息的score为1,重要消息的score为2,然后工作线程可以选择按score的倒序来获取工作任务。让重要的任务优先执行。

hash(哈希)

Redis hash数据结构 是一个键值对(key-value)集合,它是一个 string 类型的 field 和 value 的映射表,
redis本身就是一个key-value型数据库,因此hash数据结构相当于在value中又套了一层key-value型数据。
所以redis中hash数据结构特别适合存储关系型对象

应用场景

1、由于hash数据类型的key-value的特性,用来存储关系型数据库中表记录,是redis中哈希类型最常用的场景。一条记录作为一个key-value,把每列属性值对应成field-value存储在哈希表当中,然后通过key值来区分表当中的主键。

2、经常被用来存储用户相关信息。优化用户信息的获取,不需要重复从数据库当中读取,提高系统性能。

五大基本类型底层数据存储结构

在学习基本类型底层数据存储结构前,首先看下redis整体的存储结构。

redis内部整体的存储结构是一个大的hashmap,内部是数组实现的hash,key冲突通过挂链表去实现,每个dictEntry为一个key/value对象,value为定义的redisObject。

结构图如下:

1.png

dictEntry是存储key->value的地方,再让我们看一下dictEntry结构体

/*
 * 字典
 */
typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        // 指向具体redisObject
        void *val;
        // 
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点,形成链表
    struct dictEntry *next;
} dictEntry;

1 redisObject

我们接着再往下看redisObject究竟是什么结构的

/*
 * Redis 对象
 */
typedef struct redisObject {
    // 类型 4bits
    unsigned type:4;
    // 编码方式 4bits
    unsigned encoding:4;
    // LRU 时间(相对于 server.lruclock) 24bits
    unsigned lru:22;
    // 引用计数 Redis里面的数据可以通过引用计数进行共享 32bits
    int refcount;
    // 指向对象的值 64-bit
    void *ptr;
} robj;

*ptr指向具体的数据结构的地址;type表示该对象的类型,即String,List,Hash,Set,Zset中的一个,但为了提高存储效率与程序执行效率,每种对象的底层数据结构实现都可能不止一种,encoding 表示对象底层所使用的编码。

redis对象底层的八种数据结构

REDIS_ENCODING_INT(long 类型的整数)
 REDIS_ENCODING_EMBSTR embstr (编码的简单动态字符串)
 REDIS_ENCODING_RAW (简单动态字符串)
 REDIS_ENCODING_HT (字典)
 REDIS_ENCODING_LINKEDLIST (双端链表)
 REDIS_ENCODING_ZIPLIST (压缩列表)
 REDIS_ENCODING_INTSET (整数集合)
 REDIS_ENCODING_SKIPLIST (跳跃表和字典)

好了,通过redisObject就可以具体指向redis数据类型了,总结一下每种数据类型都使用了哪些数据结构,如下图所示

2.png

2 String数据结构

String类型的转换顺序

当保存的值为整数且值的大小不超过long的范围,使用整数存储

当字符串长度不超过44字节时,使用EMBSTR 编码

它只分配一次内存空间,redisObject和sds是连续的内存,查询效率会快很多,也正是因为redisObject和sds是连续在一起,伴随了一些缺点:当字符串增加的时候,它长度会增加,这个时候又需要重新分配内存,导致的结果就是整个redisObject和sds都需要重新分配空间,这样是会影响性能的,所以redis用embstr实现一次分配而后,只允许读,如果修改数据,那么它就会转成raw编码,不再用embstr编码了。

大于44字符时,使用raw编码

SDS

embstr和raw都为sds编码,看一下sds的结构体

/* 针对不同长度整形做了相应的数据结构
 * Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. 
 */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

由于redis底层使用c语言实现,可能会有疑问为什么不用c语言的字符串呢,而是用sds结构体。

1) 低复杂度获取字符串长度:由于len存在,可以直接查出字符串长度,复杂度O(1);如果用c语言字符串,查询字符串长度需要遍历整个字符串,复杂度为O(n);

2) 避免缓冲区溢出:进行两个字符串拼接c语言可使用strcat函数,但如果没有足够的内存空间。就会造成缓冲区溢出;而用sds在进行合并时会先用len检查内存空间是否满足需求,如果不满足,进行空间扩展,不会造成缓冲区溢出;

3)减少修改字符串的内存重新分配次数:c语言字符串不记录字符串长度,如果要修改字符串要重新分配内存,如果不进行重新分配会造成内存缓冲区泄露;

redis sds实现了空间预分配和惰性空间释放两种策略

空间预分配:

1)如果sds修改后,sds长度(len的值)将于1mb,那么会分配与len相同大小的未使用空间,此时len与free值相同。例如,修改之后字符串长度为100字节,那么会给分配100字节的未使用空间。最终sds空间实际为 100 + 100 + 1(保存空字符'0');

2)如果大于等于1mb,每次给分配1mb未使用空间
惰性空间释放:对字符串进行缩短操作时,程序不立即使用内存重新分配来回收缩短后多余的字节,而是使用 free 属性将这些字节的数量记录下来,等待后续使用(sds也提供api,我们可以手动触发字符串缩短);

4)二进制安全:因为C字符串以空字符作为字符串结束的标识,而对于一些二进制文件(如图片等),内容可能包括空字符串,因此C字符串无法正确存取;而所有 SDS 的API 都是以处理二进制的方式来处理 buf 里面的元素,并且 SDS 不是以空字符串来判断是否结束,而是以 len 属性表示的长度来判断字符串是否结束;

5)遵从每个字符串都是以空字符串结尾的惯例,这样可以重用 C 语言库<string.h> 中的一部分函数。

学习完sds,我们回到上面讲到的,为什么小于44字节用embstr编码呢?

再看一下rejectObject和sds定义的结构(短字符串的embstr用最小的sdshdr8)

typedef struct redisObject {
    // 类型 4bits
    unsigned type:4;
    // 编码方式 4bits
    unsigned encoding:4;
    // LRU 时间(相对于 server.lruclock) 24bits
    unsigned lru:22;
    // 引用计数 Redis里面的数据可以通过引用计数进行共享 32bits
    int refcount;
    // 指向对象的值 64-bit
    void *ptr;
} robj;
typedef struct redisObject {
    // 类型 4bits
    unsigned type:4;
    // 编码方式 4bits
    unsigned encoding:4;
    // LRU 时间(相对于 server.lruclock) 24bits
    unsigned lru:22;
    // 引用计数 Redis里面的数据可以通过引用计数进行共享 32bits
    int refcount;
    // 指向对象的值 64-bit
    void *ptr;
} robj;

redisObject占用空间

4 + 4 + 24 + 32 + 64 = 128bits = 16字节

sdshdr8占用空间

1(uint8_t) + 1(uint8_t)+ 1 (unsigned char)+ 1(buf[]中结尾的'0'字符)= 4字节

初始最小分配为64字节,所以只分配一次空间的embstr最大为 64 - 16- 4 = 44字节

3 List存储结构

Redis3.2之前的底层实现方式:压缩列表ziplist 或者 双向循环链表linkedlist

当list存储的数据量比较少且同时满足下面两个条件时,list就使用ziplist存储数据:

list中保存的每个元素的长度小于 64 字节;
列表中数据个数少于512个

Redis3.2及之后的底层实现方式:quicklist

quicklist是一个双向链表,而且是一个基于ziplist的双向链表,quicklist的每个节点都是一个ziplist,结合了双向链表和ziplist的优点。

ziplist

ziplist是一种压缩链表,它的好处是更能节省内存空间,因为它所存储的内容都是在连续的内存区域当中的。当列表对象元素不大,每个元素也不大的时候,就采用ziplist存储。但当数据量过大时就ziplist就不是那么好用了。因为为了保证他存储内容在内存中的连续性,插入的复杂度是O(N),即每次插入都会重新进行realloc。如下图所示,redisObject对象结构中ptr所指向的就是一个ziplist。整个ziplist只需要malloc一次,它们在内存中是一块连续的区域。

ziplist结构如下:

3.png

1、zlbytes:用于记录整个压缩列表占用的内存字节数
 
2、zltail:记录要列表尾节点距离压缩列表的起始地址有多少字节
 
3、zllen:记录了压缩列表包含的节点数量。

4、entryX:要说列表包含的各个节点

5、zlend:用于标记压缩列表的末端

为什么数据量大时不用ziplist?

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

快速列表(quickList)

快速列表是ziplist和linkedlist的混合体,是将linkedlist按段切分,每一段用ziplist来紧凑存储,多个ziplist之间使用双向指针链接。

为什么不直接使用linkedlist?

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

quicklist结构

typedef struct quicklist {
    // 指向quicklist的头部
    quicklistNode *head;
    // 指向quicklist的尾部
    quicklistNode *tail;
    unsigned long count;
    unsigned int len;
    // ziplist大小限定,由list-max-ziplist-size给定
    int fill : 16;
    // 节点压缩深度设置,由list-compress-depth给定
    unsigned int compress : 16;
} quicklist;

typedef struct quicklistNode {
    // 指向上一个ziplist节点
    struct quicklistNode *prev;
    // 指向下一个ziplist节点
    struct quicklistNode *next;
    // 数据指针,如果没有被压缩,就指向ziplist结构,反之指向quicklistLZF结构
    unsigned char *zl;
    // 表示指向ziplist结构的总长度(内存占用长度)
    unsigned int sz;
    // ziplist数量
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    // 预留字段,存放数据的方式,1--NONE,2--ziplist
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    // 解压标记,当查看一个被压缩的数据时,需要暂时解压,标记此参数为1,之后再重新进行压缩
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    // 扩展字段
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

typedef struct quicklistLZF {
    // LZF压缩后占用的字节数
    unsigned int sz; /* LZF size in bytes*/
    // 柔性数组,存放压缩后的ziplist字节数组
    char compressed[];
} quicklistLZF;

4.png

ziplist的长度

quicklist内部默认单个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 都不压缩。

4 Hash类型

当Hash中数据项比较少的情况下,Hash底层才用压缩列表ziplist进行存储数据,随着数据的增加,底层的ziplist就可能会转成dict,具体配置如下

hash-max-ziplist-entries 512
hash-max-ziplist-value 64

在List中已经介绍了ziplist,下面来介绍下dict。

看下数据结构


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

typedef struct dictht {
    //指针数组,这个hash的桶
    dictEntry **table;
    //元素个数
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

dictEntry大家应该熟悉,在上面有讲,使用来真正存储key->value的地方
typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        // 指向具体redisObject
        void *val;
        // 
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点,形成链表
    struct dictEntry *next;
} dictEntry;

我们可以看到每个dict中都有两个hashtable

结构图如下:

5.png

虽然dict结构有两个hashtable,但是通常情况下只有一个hashtable是有值的。但是在dict扩容缩容的时候,需要分配新的hashtable,然后进行渐近式搬迁,这时候两个hashtable存储的旧的hashtable和新的hashtable。搬迁结束后,旧hashtable删除,新的取而代之。

5 渐进式rehash

所谓渐进式rehash是指我们的大字典的扩容是比较消耗时间的,需要重新申请新的数组,然后将旧字典所有链表的元素重新挂接到新的数组下面,是一个O(n)的操作。但是因为我们的redis是单线程的,无法承受这样的耗时过程,所以采用了渐进式rehash小步搬迁,虽然慢一点,但是可以搬迁完毕。

扩容条件

我们的扩容一般会在Hash表中的元素个数等于第一维数组的长度的时候,就会开始扩容。扩容的大小是原数组的两倍。不过在redis在做bgsave(RDB持久化操作的过程),为了减少内存页的过多分离(Copy On Write),redis不会去扩容。但是如果hash表的元素个数已经到达了第一维数组长度的5倍的时候,就会强制扩容,不管你是否在持久化。

不扩容主要是为了尽可能减少内存页过多分离,系统需要更多的开销去回收内存。

缩容条件

当我们的hash表元素逐渐删除的越来越少的时候。redis于是就会对hash表进行缩容来减少第一维数组长度的空间占用。缩容的条件是元素个数低于数组长度的10%,并且缩容不考虑是否在做redis持久化。

不用考虑bgsave主要是因为我们的缩容的内存都是已经使用过的,缩容的时候可以直接置空,而且由于申请的内存比较小,同时会释放掉一些已经使用的内存,不会增大系统的压力。

rehash步骤

1、为ht[1] 分配空间,让字典同时持有ht[0]和ht[1]两个哈希表;

2、定时维持一个索引计数器变量rehashidx,并将它的值设置为0,表示rehash 开始;

3、在rehash进行期间,每次对字典执行CRUD操作时,程序除了执行指定的操作以外,还会将ht[0]中的数据rehash 到ht[1]表中,并且将rehashidx加一;

4、当ht[0]中所有数据转移到ht[1]中时,将rehashidx 设置成-1,表示rehash 结束;

(采用渐进式rehash 的好处在于它采取分而治之的方式,避免了集中式rehash 带来的庞大计算量。特别的在进行rehash时只能对h[0]元素减少的操作,如查询和删除;而查询是在两个哈希表中查找的,而插入只能在ht[1]中进行,ht[1]也可以查询和删除。)

5、将ht[0]释放,然后将ht[1]设置成ht[0],最后为ht[1]分配一个空白哈希表。

过程如下图:

6.png

6 set数据结构

Redis 的集合相当于Java中的 HashSet,它内部的键值对是无序、唯一的。它的内部实现相当于一个特殊的字典,字典中所有的 value 都是一个值 NULL。集合Set类型底层编码包括hashtable和inset。

当存储的数据同时满足下面这样两个条件的时候,Redis 就采用整数集合intset来实现set这种数据类型:

存储的数据都是整数
存储的数据元素个数小于512个

当不能同时满足这两个条件的时候,Redis 就使用dict来存储集合中的数据

hashtable在上面介绍过了,我们就只介绍inset。

inset结构体


typedef struct intset {
    uint32_t encoding;
    // length就是数组的实际长度
    uint32_t length;
    // contents 数组是实际保存元素的地方,数组中的元素有以下两个特性:
    // 1.没有重复元素
    // 2.元素在数组中从小到大排列
    int8_t contents[];
} intset;

// encoding 的值可以是以下三个常量的其中一个
#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

inset的查询

intset是一个有序集合,查找元素的复杂度为O(logN)(采用二分法),但插入时不一定为O(logN),因为有可能涉及到升级操作。比如当集合里全是int16_t型的整数,这时要插入一个int32_t,那么为了维持集合中数据类型的一致,那么所有的数据都会被转换成int32_t类型,涉及到内存的重新分配,这时插入的复杂度就为O(N)了。是intset不支持降级操作。

inset是有序不要和我们zset搞混,zset是设置一个score来进行排序,而inset这里只是单纯的对整数进行升序而已

7 Zset数据结构

Zset有序集合和set集合有着必然的联系,他保留了集合不能有重复成员的特性,但不同的是,有序集合中的元素是可以排序的,但是它和列表的使用索引下标作为排序依据不同的是,它给每个元素设置一个分数,作为排序的依据。

zet的底层编码有两种数据结构,一个ziplist,一个是skiplist。

Zset也使用了ziplist做了排序,所以下面讲一下ziplist如何做排序。

ziplist做排序

每个集合元素使用两个紧挨在一起的压缩列表节点来保存,第一个节点保存元素的成员(member),而第二个元素则保存元素的分值(score)。

存储结构图如下一目了然:

skiplist跳表

结构体如下,skiplist是与dict结合来使用的,这个结构比较复杂。

/*
 * 跳跃表
 */
typedef struct zskiplist {
    // 头节点,尾节点
    struct zskiplistNode *header, *tail;
    // 节点数量
    unsigned long length;
    // 目前表内节点的最大层数
    int level;
} zskiplist;

/*
 * 跳跃表节点
 */
typedef struct zskiplistNode {
    // member 对象
    robj *obj;
    // 分值
    double score;
    // 后退指针
    struct zskiplistNode *backward;
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 这个层跨越的节点数量
        unsigned int span;
    } level[];
} zskiplistNode;

跳表是什么?

我们先看下链表
8.png

如果想查找到node5需要从node1查到node5,查询耗时

但如果在node上加上索引:
9.png

这样通过索引就能直接从node1查找到node5

redis跳跃表

让我们再看下redis的跳表结构(图太复杂,直接从网上找了张图说明)

10.png

header:指向跳跃表的表头节点,通过这个指针程序定位表头节点的时间复杂度就为O(1);

tail:指向跳跃表的表尾节点,通过这个指针程序定位表尾节点的时间复杂度就为O(1);

level:记录目前跳跃表内,层数最大的那个节点的层数(表头节点的层数不计算在内),通过这个属性可以再O(1)的时间复杂度内获取层高最好的节点的层数;

length:记录跳跃表的长度,也即是,跳跃表目前包含节点的数量(表头节点不计算在内),通过这个属性,程序可以再O(1)的时间复杂度内返回跳跃表的长度。

结构右方的是四个 zskiplistNode结构,该结构包含以下属性

层(level):

节点中用L1、L2、L3等字样标记节点的各个层,L1代表第一层,L2代表第二层,以此类推。

每个层都带有两个属性:前进指针和跨度。前进指针用于访问位于表尾方向的其他节点,而跨度则记录了前进指针所指向节点和当前节点的距离(跨度越大、距离越远)。在上图中,连线上带有数字的箭头就代表前进指针,而那个数字就是跨度。当程序从表头向表尾进行遍历时,访问会沿着层的前进指针进行。

每次创建一个新跳跃表节点的时候,程序都根据幂次定律(powerlaw,越大的数出现的概率越小)随机生成一个介于1和32之间的值作为level数组的大小,这个大小就是层的“高度”。

后退(backward)指针:

节点中用BW字样标记节点的后退指针,它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。与前进指针所不同的是每个节点只有一个后退指针,因此每次只能后退一个节点。

分值(score):

各个节点中的1.0、2.0和3.0是节点所保存的分值。在跳跃表中,节点按各自所保存的分值从小到大排列。

成员对象(oj):

各个节点中的o1、o2和o3是节点所保存的成员对象。在同一个跳跃表中,各个节点保存的成员对象必须是唯一的,但是多个节点保存的分值却可以是相同的:分值相同的节点将按照成员对象在字典序中的大小来进行排序,成员对象较小的节点会排在前面(靠近表头的方向),而成员对象较大的节点则会排在后面(靠近表尾的方向)。

本文为作者admin发布,未经允许禁止转载!
上一篇 下一篇
评论
暂无评论 >_<
加入评论