神刀安全网

redis数据结构的底层实现(下)

上两篇我们分享了演示数据,动态字符串和链表的底层实现,现在,我们分享一下字典,跳跃表和压缩列表的具体实现:

4、字典

字典又称为符号表或者关联数组、或映射(map),是一种用于保存键值对的抽象数据结构。字典中的每一个键 key 都是唯一的,通过 key 可以对值来进行查找或修改。C 语言中没有内置这种数据结构的实现,所以字典依然是 Redis自己构建的。

typedef struct dictht{      //哈希表数组      dictEntry **table;      //哈希表大小      unsigned long size;      //哈希表大小掩码,用于计算索引值      //总是等于 size-1      unsigned long sizemask;      //该哈希表已有节点的数量      unsigned long used;   }dictht 

哈希表是由数组 table 组成,table 中每个元素都是指向 dict.h/dictEntry 结构,dictEntry 结构定义如下:

typedef struct dictEntry{      //键      void *key;      //值      union{           void *val;           uint64_tu64;           int64_ts64;      }v;        //指向下一个哈希表节点,形成链表      struct dictEntry *next; }dictEntry 

key 用来保存键,val 属性用来保存值,值可以是一个指针,也可以是uint64_t整数,也可以是int64_t整数。

redis数据结构的底层实现(下)

字典.png

注意这里还有一个指向下一个哈希表节点的指针,我们知道哈希表最大的问题是存在哈希冲突,如何解决哈希冲突,有开放地址法和链地址法。这里采用的便是链地址法,通过next这个指针可以将多个哈希值相同的键值对连接在一起,用来解决哈希冲突。

5、跳跃表

跳跃表(skiplist)是一种有序数据结构,它通过在每个节点中维持多个指向其它节点的指针,从而达到快速访问节点的目的。具有如下性质:

1、由很多层结构组成;

2、每一层都是一个有序的链表,排列顺序为由高层到底层,都至少包含两个链表节点,分别是前面的head节点和后面的nil节点;

3、最底层的链表包含了所有的元素;

4、如果一个元素出现在某一层的链表中,那么在该层之下的链表也全都会出现(上一层的元素是当前层的元素的子集);

5、链表中的每个节点都包含两个指针,一个指向同一层的下一个链表节点,另一个指向下一层的同一个链表节点;
  

redis数据结构的底层实现(下)

跳跃表.png

Redis中跳跃表节点定义如下:

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

多个跳跃表节点构成一个跳跃表:

typedef struct zskiplist{      //表头节点和表尾节点      structz skiplistNode *header, *tail;      //表中节点的数量      unsigned long length;      //表中层数最大的节点的层数      int level;   }zskiplist; 

6、压缩列表

压缩列表(ziplist)是Redis为了节省内存而开发的,是由一系列特殊编码的连续内存块组成的顺序型数据结构,一个压缩列表可以包含任意多个节点(entry),每个节点可以保存一个字节数组或者一个整数值。

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

redis数据结构的底层实现(下)

压缩列表.png

大多数情况下,Redis使用简单字符串SDS作为字符串的表示,相对于C语言字符串,SDS具有常数复杂度获取字符串长度,杜绝了缓存区的溢出,减少了修改字符串长度时所需的内存重分配次数,以及二进制安全能存储各种类型的文件,并且还兼容部分C函数。

通过为链表设置不同类型的特定函数,Redis链表可以保存各种不同类型的值,除了用作列表键,还在发布与订阅、慢查询、监视器等方面发挥作用。
  
  Redis的字典底层使用哈希表实现,每个字典通常有两个哈希表,一个平时使用,另一个用于rehash时使用,使用链地址法解决哈希冲突。

跳跃表通常是有序集合的底层实现之一,表中的节点按照分值大小进行排序。

压缩列表是Redis为节省内存而开发的顺序型数据结构,通常作为列表键和哈希键的底层实现之一。

到这里redis中的数据结构我们差不多就实现了,更多干货和资料请直接联系我,也可以加群710520381,邀请码:柳猫,欢迎大家共同讨论

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » redis数据结构的底层实现(下)

分享到:更多 ()