redis源码：数据结构实现

redis源码：数据结构实现

list

源码目录adlist.h adlist.c

底层数据结构双向链表

节点源码

typedefstructlistNode{

// 前置节点

structlistNode*prev;

// 后置节点

structlistNode*next;

// 值

void*value;

}listNode;

链表源码

typedefstructlist{

// 头节点

listNode*head;

// 尾节点

listNode*tail;

// 节点值复制函数

void*(*dup)(void*ptr);

// 节点值释放函数

void(*free)(void*ptr);

// 节点值对比函数

int(*match)(void*ptr,void*key);

// 链表所包含的节点数量

unsignedlonglen;

}list;

图解说明

特点

可以很容易获取当前节点的前一个节点和后一个节点

没有环结构，所有的节点以空节点结束

链表自带长度计数器，获取链表节点个数的时间复杂度为O(1)

hash

源码目录dict.h dict.c

底层数据结构哈希表说明：在redis中解决hash冲突的方式为采用链地址法。key和v分别用于保存键值对的键和值

哈希表

typedefstructdictht{

// 哈希表数组,数组的每个元素都指向dictEntry结构指针

//链地址法解决哈希冲突

dictEntry**table;

// 哈希表大小，且一定是2的幂

unsignedlongsize;

// 哈希表大小掩码，用于计算索引值

// 总是等于 size - 1

unsignedlongsizemask;

// 该哈希表已有节点的数量

unsignedlongused;

}dictht;

字典

typedefstructdict{

// 类型特定函数

dictType*type;

// 私有数据

void*privdata;

// 哈希表

dicththt[2];

// rehash 索引

// 当 rehash 不在进行时，值为 -1

intrehashidx;/* rehashing not in progress if rehashidx == -1 */

// 目前正在运行的安全迭代器的数量

intiterators;/* number of iterators currently running */

}dict;

图解说明

里面包含了一个特别重要的东西：rehash，单独拎出来总结

节点源码

typedefstructdictEntry{

void*key;//键

union{

void*val;//值

uint64_tu64;

int64_ts64;

doubled;

}v;

structdictEntry*next;//指向下一个节点，形成链表

}dictEntry;

总结

redis中字典使用哈希表作为底层实现的，每个字典带有两个哈希表，一个日常使用，另外一个作为rehash时使用；

哈希表解决冲突的方式是使用链地址法；

哈希表进行扩展或者是收缩的时候，采用的是rehash的方式，这个过程是渐进式的；

zset

跳跃表节点源码

typedefstructzskiplistNode{

// 成员对象

robj*obj;

// 分值

doublescore;

// 后退指针

structzskiplistNode*backward;

// 层

structzskiplistLevel{

// 前进指针

structzskiplistNode*forward;

// 跨度

unsignedintspan;

}level[];

}zskiplistNode;

跳跃表

typedefstructzskiplist{

// 表头节点和表尾节点

structzskiplistNode*header,*tail;

// 表中节点的数量

unsignedlonglength;

// 表中层数最大的节点的层数

intlevel;

}zskiplist;

图解

总结

每个跳跃表节点的层高都是在1到32之间的随机数

在同一跳跃表中，多个节点可以包含相同的分值，但是每个节点的成员对象必须是唯一的；

跳跃表中的节点按照分值的大小进行排序的，当分值相同时，节点按照成员对象的大小进行排序

set

源码目录insert.h insert.c

低层数据结构数组

源码

typedefstructintset{

// 编码方式

uint32_tencoding;

// 集合包含的元素数量

uint32_tlength;

// 保存元素的数组

int8_tcontents[];

}intset;

升级操作

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

2.将低层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位置，在放置元素的过程中，需要维持低层的数组的有序性质不变；

3.将新元素添加到低层数组中；

总结

集合的低层实现是数组；它是有序、无重复的方式保存；

只支持升级操作，不支持降级操作

升级操作可以有效的节省内存，而且可以根据新增元素的类型扩展相应的数据类型；

想了解学习更多C++后台服务器方面的知识，请关注：微信公众号：====CPP后台服务器开发====