你的位置:首页 > 数据库

[数据库]Redis入门笔记


redis是一个轻量级的Nodsql数据库,使用kev-value的形式存储数据,在redis的世界里,没有整数、浮点数等概念,大多数情况下数据以字符串形式展现,偶尔会出现Long类型数据的场景。

一、字符串

为了提高字符串使用的效率,redis源代码中使用字符串的结构如下:

typedef char *sds;struct sdshdr {// buf 已占用长度int len;// buf 剩余可用长度int free;// 实际保存字符串数据的地方char buf[];};//其中,类型sds 是char * 的别名(alias),而结构sdshdr 则保存了len 、free 和buf 三个属性。

每次调用strlen复杂度为O(1),而对于字符串拼接处理,redis使用如下策略:

  • 初始化的数据,free为0
  • append长度为K的数据,重新分配空间,free大小为N+K+1,N为原字符串长度len,
  • 再次append,如果len+K1<free,不再重新分配,否则重新使用前一条策略分配空间。

二、双端链表

 redis多处使用到了该结构

  •  事务模块使用双端链表来按顺序保存输入的命令;

  • 服务器模块使用双端链表来保存多个客户端;

  • 订阅/发送模块使用双端链表来保存订阅模式的多个客户端;

  • 事件模块使用双端链表来保存时间事件(time event)。

redis双向链表实现代码:

//其中,listNode 是双端链表的节点:typedef struct listNode {  // 前驱节点  struct listNode *prev;  // 后继节点  struct listNode *next;  // 值  void *value;} listNode;//而list 则是双端链表本身: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;

三、字典

字典的实现:

/** 字典**每个字典使用两个哈希表,用于实现渐进式rehash*/typedef struct dict {// 特定于类型的处理函数dictType *type;  // 类型处理函数的私有数据  void *privdata;  // 哈希表(2 个)  dictht ht[2];  // 记录rehash 进度的标志,值为-1 表示rehash 未进行  int rehashidx;  // 当前正在运作的安全迭代器数量  int iterators;} dict;

哈希表的实现:

/** 哈希表*/typedef struct dictht {  // 哈希表节点指针数组(俗称桶,bucket)  dictEntry **table;  // 指针数组的大小  unsigned long size;  // 指针数组的长度掩码,用于计算索引值  unsigned long sizemask;  // 哈希表现有的节点数量  unsigned long used;} dictht;

哈希表节点:

/** 哈希表节点*/typedef struct dictEntry {  // 键  void *key;  // 值  union {    void *val;    uint64_t u64;    int64_t s64;  } v;  // 链往后继节点  struct dictEntry *next;} dictEntry;

hash表结构图:

rehash 实际上是一次表的扩容,或者说修改表容量的操作,将ht(0)复制到ht(1),并将新的ht(1)作为ht(0)这样一个过程

四、跳跃表

跳跃表实现:

//表结构
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;

跳跃表在Redis 的唯一作用,就是实现有序集数据类型。