阅读 0

redis源码:数据结构实现

redis源码:数据结构实现

Snipaste_2020-02-16_17-29-47.png

list

  • 源码目录

    adlist.h adlist.c

  • 底层数据结构

    双向链表

    • 节点源码

      typedef struct listNode {
      
      // 前置节点
          struct listNode *prev;
      
      // 后置节点
          struct listNode *next;
      
      // 值
          void *value;
      
      } listNode;复制代码
    • 链表源码

      typedef struct list {
      
      // 头节点
          listNode *head;
      
      // 尾节点
          listNode *tail;
      
      // 节点值复制函数
          void *(*dup)(void *ptr);
      
      // 节点值释放函数
          void (*free)(void *ptr);
      
      // 节点值对比函数
          int (*match)(void *ptr, void *key);
      
      // 链表所包含的节点数量
          unsigned long len;
      
      } list;复制代码
    • 图解说明

  • 特点

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

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

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

hash

  • 源码目录

    dict.h dict.c

  • 底层数据结构

    哈希表

    说明:在redis中解决hash冲突的方式为采用链地址法。key和v分别用于保存键值对的键和值

    • 哈希表

      typedef struct dictht {
          
      // 哈希表数组,数组的每个元素都指向dictEntry结构指针
      //链地址法解决哈希冲突
          dictEntry **table;
      
      // 哈希表大小,且一定是2的幂
          unsigned long size;
          
      // 哈希表大小掩码,用于计算索引值
      // 总是等于 size - 1
          unsigned long sizemask;
      
      // 该哈希表已有节点的数量
          unsigned long used;
      
      } dictht;复制代码
    • 字典

      typedef struct dict {
      
      // 类型特定函数
          dictType *type;
      
      // 私有数据
          void *privdata;
      
      // 哈希表
          dictht ht[2];
      
      // rehash 索引
      // 当 rehash 不在进行时,值为 -1
          int rehashidx; /* rehashing not in progress if rehashidx == -1 */
      
      // 目前正在运行的安全迭代器的数量
          int iterators; /* number of iterators currently running */
      
      } dict;复制代码
    • 图解说明

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

    • 节点源码

      typedef struct dictEntry {
          void *key;                //键
          union {
              void *val;            //值
              uint64_t u64;
              int64_t s64;
              double d;
          } v;
          struct dictEntry *next; //指向下一个节点,形成链表
      } dictEntry;复制代码
  • 总结

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

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

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

zset

  • 源码目录

    redis.c redis.h

  • 底层数据结构

    跳跃表(资料参考:blog.csdn.net/qpzkobe/art…

    • 跳跃表节点源码

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

      typedef struct zskiplist {
      
      // 表头节点和表尾节点
          struct zskiplistNode *header, *tail;
      
      // 表中节点的数量
          unsigned long length;
      
      // 表中层数最大的节点的层数
          int level;
      
      } zskiplist;复制代码
    • 图解

  • 总结

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

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

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

set

  • 源码目录

    insert.h insert.c

  • 低层数据结构

    数组

    • 源码

      typedef struct intset {
          
      // 编码方式
          uint32_t encoding;
      
      // 集合包含的元素数量
          uint32_t length;
      
      // 保存元素的数组
          int8_t contents[];
      
      } intset;复制代码
  • 升级操作

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

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

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

  • 总结

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

    • 只支持升级操作,不支持降级操作

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


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

扫码关注更多精彩
qrcode_for_gh_63e8f112ec74_258.jpg

温馨提示

如果你喜欢本文,请分享到朋友圈,想要获得更多信息,请关注我。



关注下面的标签,发现更多相似文章
评论