1.redis几种数据结构

●字符串
●无序列表
●有序列表
●hash

2.字符串

简单动态字符串（simple dynamic string sds）使用这种抽象类型作为redis的默认字符串表示。
redis需要一个可以被修改的字符串值时，redis使用sds来表示字符串值。redis数据库里，字符串值的键值对在底层都是由sds实现的。
set msg “hello world”

底层：键：保存着字符串"msg"的sds；值：保存着字符串"hello world"的sds
sds除了用来保存数据库中的字符串外，还被用作缓冲区。

2.1 sds的定义

/*

• 保存字符串对象的结构
  */
  struct sdshdr {

  // buf 中已占用空间的长度
  int len;

  // buf 中剩余可用空间的长度
  int free;

  // 数据空间
  char buf[];
  };

2.2 sds与c字符串的区别

2.2.1 常数复杂度获取字符串长度

sds记录len属性，不需要遍历获取字符串长度。

2.2.2 杜绝缓冲区溢出

c的字符串使用一些函数时，如　sdscat(s1,s2)（将s2拼接到s1后）可能会出现缓冲区溢出的情况。但是sds有free属性，api可以先获取free来作为判断是否需要扩展缓冲区。

2.2.3 减少修改字符串时带来的内存重新分配次数

内存重分配是一个比较耗时的操作。但是redis对速度要求严苛，数据会被频繁修改。采取一些策略减少重新分配内存的次数
●空间预先分配，extraBuf(free) = lenafter < 1mb ? lenafter : 1mb
●惰性空间释放：字符串缩短时，不立即执行内存重分配，而是使用free属性将这些空间记录下来

2.2.4 二进制安全

sds使用len属性的值而不是空字符来判断字符串是否结束

2.2.5 兼容部分c字符串函数

保留空字符串结尾的习惯

3.链表

redis中列表键包含了数量比较多的元素，或者在列表中包含的元素都是比较长的字符串时，redis就会使用链表作为列表键的底层实现。

3.1 链表和链表节点的实现

/*

• 双端链表节点
  */
  typedef struct listNode {

  // 前置节点
  struct listNode *prev;

  // 后置节点
  struct listNode *next;

  // 节点的值
  void *value;

} listNode;

list结构表示链表
/*

• 双端链表结构
  */
  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;

redis的链表特点
双端、无环、表头指针和表尾指针、长度计数器、多态
多态：链表节点使用void*指针来保存节点值，可以通过list结构中的dup、free、match三个属性为节点值设置类型特定函数。用于保存各种不同类型的值。

4.字典

redis实现了自己的字典。redis的数据库就是使用字典来作为底层实现的，对数据库的增删改查也是构建在对字典的操作之上。

4.1 字典的实现

redis的字典使用哈希表作为底层实现。一个hash表里可以有多个哈希表节点。每个哈希表节点就保存了字典中的一个键值对。

4.1.1 哈希表

/* This is our hash table structure. Every dictionary has two of this as we

• implement incremental rehashing, for the old to the new table. /
  /

• 哈希表

• 每个字典都使用两个哈希表，从而实现渐进式 rehash 。
  */
  typedef struct dictht {

  // 哈希表数组
  dictEntry **table;

  // 哈希表大小
  unsigned long size;

  // 哈希表大小掩码，用于计算索引值
  // 总是等于 size - 1
  unsigned long sizemask;

  // 该哈希表已有节点的数量
  unsigned long used;

} dictht;

为啥需要size的掩码，为啥已经有了size还需要有节点数量这个属性？是因为哈希表的大小不表示已经被使用的大小，而是表示预分配的大小，而used字段表示的是已经使用的大小？
答：是的，size表示预分配的大小，used表示已经使用的多少。

4.1.2 哈希表节点

/*

• 哈希表节点
  */
  typedef struct dictEntry {

  // 键
  void *key;

  // 值
  union {
  void *val;
  uint64_t u64; //这个字段是用来干嘛的？
  int64_t s64;
  } v;

  // 指向下个哈希表节点，形成链表
  struct dictEntry *next;

} dictEntry;

其中key属性表示键值对中的键，是void类型，所以可以表示多种类型。而v属性则保存着键值对中的值。键值对中的值可以是一个指针，或者是一个uint64_t整数。或者是一个int64_t整数。
next属性是指向另一个hash表节点的指针。这个指针可以将多个hash值相同的键值对连接在一起，以此来解决键冲突的问题。

4.1.3 字典

/*

• 字典
  */
  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;

问题：hash表和字典的区别是什么？
字典里有明确地指出数据类型，通过type字段。还有个字段ht表示hash表，但是为啥是2？还有个rehash索引，这是个什么东西？还有个iterators，迭代器。
type属性和private属性是针对不同类型的键值对，为创建多态字典而设置的。（意思是这个字典里保存的键值对类型可以不一样？）
●type：指向dictType结构的指针。每个dictType结构保存了一簇用于操作特定类型键值对的函数。redis会为不同的字典设置不同的类型特定函数。（指向函数，好奇怪啊。表示这套函数是为这种类型的键值准备的，为什么不能用范型？）
●private属性则保存了需要传给那些特定类型函数的可选参数（传给函数的可选参数？）
/*

• 字典类型特定函数
  */
  typedef struct dictType {

  // 计算哈希值的函数
  unsigned int (*hashFunction)(const void *key);

  // 复制键的函数
  void *(*keyDup)(void *privdata, const void *key);

  // 复制值的函数
  void *(*valDup)(void *privdata, const void *obj);

  // 对比键的函数
  int (*keyCompare)(void *privdata, const void *key1, const void *key2);

  // 销毁键的函数
  void (*keyDestructor)(void *privdata, void *key);

  // 销毁值的函数
  void (*valDestructor)(void *privdata, void *obj);

} dictType;

为什么需要有复制键、值的函数，以及为什么要有销毁的函数？删除后回收内存？
ht属性是一个包含两个项的数组。每一个项都是一个dictht哈希表。一般情况下，字典只使用ht[0]哈希表，ht[1]哈希表只会在对ht[0]rehash的时候使用。原来如此，需要有rehash，才会需要两个哈希表。
rehashidx，也是用来rehash的，记录rehash目前的进度。如果没有在进行rehash，它的值为-1。

普通状态下的字典。dict表示字典、里面有两个hash表，dictht里会有指向dictEntry[]数组的指针。dictEntry里包含多个dictEntry节点，节点里有键、值、next指针。

4.2 哈希算法

获取hash值的方法：字典里的类型字段，调用type里的hashFunction来进行hash
hash = dict -> type -> hashFunction(k0)
index = hash & ht[0].sizemask = 8 & 3 = 0
为什么按位与和取模是一样均匀的效果？只是一样均匀还是说和取模效果一样？
按位与不怎么均匀啊，如果size是3，还能比较均匀地分布在不同的位置上。但是如果size是4就完全不均匀了。所以是sizemask是么？sizemask一直是2^n - 1。这样就可以均匀地分布在这些位置。
当字典被用作数据库的底层实现，或者hash键的底层实现时候，redis使用MurmurHash2算法（随机分布额&速度快）来计算键的hash值。

4.3 解决键冲突

链地址法解决冲突。因为dictEntry没有指向链尾指针，所以新插入的节点都是在链表表头。why？这和指向表尾指针有啥关系？

4.4 rehash

rehash的情况
1.扩展
●不执行bgsave或者bgrewriteaof命令时，当负载因子>=1时
●执行bgsave或者bgrewriteaof命令，且负载因子>=5时
2.收缩
●负载因子<0.1时，执行收缩
rehash的步骤
1.为ht[1]分配大小
●扩展：最小的大于等于ht[0].used*2 的2^n
●收缩：最小的大于等于h[0].used的2^{n，这里为啥是最小大于等于的h[0].used的2}n？因为当负载因子小于0.1时才会执行收缩，此时used的值小于是size的0.1，大于等于第一个used的2^n绝大多数情况下都是缩小的
2.遍历ht[0]的节点，并重新计算hash值，table不一样了，并保存在ht[1]中
3.释放ht[0],将ht[1]置为ht[0]，并在ht[1]新创建一个空白的hash表，为下一次rehash做准备
rehash负载因子计算公式
load_factor = ht[0].used/ht[0].size
啥时候会出现load_factor>5呢？那就是used是包含冲突节点的。

4.5 渐进式rehash

关键：属性rehashidx
rehashidx记录当前需要rehash的索引。在执行rehash的期间，每次对字典进行添加、删除、查找或者更新操作时，除了执行这些操作，还会把rehashidx索引上的节点rehash到ht[1]。每次执行完成，rehashidx值就+1，直到rehas完成，会被置为-1。
添加操作时，新元素只会出现在ht[1]中。保证ht[1]只增不减
查找操作，先查ht[0]，再查ht[1]。
为什么要执行渐进式rehash
答：ht[0]里的元素可能非常多，一次性执行完会耗时比较久。分而治之的思想

4.6 字典api

创建、给定key返回value、添加元素、删除元素、释放字典
dictReplace和dictAdd有什么区别？不都是如果键已经存在于字典，那么用新值取代原有的值么？
答：区别：dictAdd如果key已经存在会返回error，replace会替换
dictAdd先entry->next=ht->table[index]再ht->table[index]=entry的原因是，链式地址解决冲突，新增元素都是放在链表头。entry的next就是原有链表的链表头
/* Add an element, discarding the old if the key already exists.

• Return 1 if the key was added from scratch, 0 if there was already an

• element with such key and dictReplace() just performed a value update

• operation. */
  static int dictReplace(dict *ht, void *key, void *val) {
  dictEntry *entry, auxentry;

  /* Try to add the element. If the key

  • does not exists dictAdd will suceed. /
    if (dictAdd(ht, key, val) == DICT_OK)
    return 1;
    / It already exists, get the entry /
    entry = dictFind(ht, key);
    / Free the old value and set the new one /
    / Set the new value and free the old one. Note that it is important
  • to do that in this order, as the value may just be exactly the same
  • as the previous one. In this context, think to reference counting,
  • you want to increment (set), and then decrement (free), and not the
  • reverse. */
    auxentry = *entry;
    dictSetHashVal(ht, entry, val);
    dictFreeEntryVal(ht, &auxentry);
    return 0;
    }

/* Add an element to the target hash table */
static int dictAdd(dict *ht, void *key, void *val) {
int index;
dictEntry *entry;

/* Get the index of the new element, or -1 if* the element already exists. */
if ((index = _dictKeyIndex(ht, key)) == -1)return DICT_ERR;/* Allocates the memory and stores key */
entry = malloc(sizeof(*entry));
entry->next = ht->table[index];
ht->table[index] = entry;/* Set the hash entry fields. */
dictSetHashKey(ht, entry, key);
dictSetHashVal(ht, entry, val);
ht->used++;
return DICT_OK;

}

5.跳跃表

跳跃表：一种有序的数据结构，通过在每个节点中维持指向多个其他节点的指针，从而达到快速访问节点的目的。
平均O(logN)、最坏O(N)复杂度的节点查找。还可以通过顺序性操作来批量处理节点
大部分情况下，跳跃表的效率可以和平衡树相媲美，并且因为跳跃表的实现更为简单。所以有不少程序都是用跳跃表来代替平衡树。
一个有序集合包含的元素数量比较多时/有序集合中元素的成员是比较长的字符串时，使用跳跃表。
另一个用途：集群节点中用作内部数据结构

5.1 跳跃表的实现

5.1.1 跳跃表节点

/* ZSETs use a specialized version of Skiplists /
/

• 跳跃表节点
  */
  typedef struct zskiplistNode {

  // 成员对象
  robj *obj;

  // 分值
  double score;

  // 后退指针
  struct zskiplistNode *backward;

  // 层
  struct zskiplistLevel {

   // 前进指针struct zskiplistNode *forward;// 跨度unsigned int span;
  

  } level[];

} zskiplistNode;

详细说明
1.层：
level数组包含多个元素，每个元素都包含一个指向其他节点的指针。层的数量越多，访问其他节点的速度就越快。
level的size的生成算法：随机生成1-32之间的值作为level的大小
// 层
struct zskiplistLevel {

    // 前进指针struct zskiplistNode *forward;// 跨度unsigned int span;} level[];

2.前进指针
每一个层都有一个指向表尾方向的前进指针（level[i].forward），用于从表头向表尾方向访问节点。
3.跨度
层的跨度（level[i].span属性）用于记录两个节点之间的距离
●两个节点之间的跨度越大，它们相距得就越远
●指向null的跨度为0
跨度和遍历操作无关，遍历操作只使用前进指针
跨度实际上是用来计算排位的（rank）：查找某个节点的过程中，将沿途访问过的所有层的跨度累计起来，得到的结果就是目标节点在跳跃表中的排位。（这个排位是用来干啥的？）
4.后退指针
每个节点只有一个后退指针，所以每次只能后退至前一个节点
5.分值和成员
score属性，是一个double类型的浮点数，跳跃表中的所有节点都按分值从小到大来排序。成员对象（obj）是一个指针，指向一个字符串对象，字符串对象则保存着一个sds值。
同一个跳跃表中，每个节点保存的obj需要唯一，但是score可以相同。score相同的节点将按照成员对象在字典序中的大小来进行排序。

5.1.2 跳跃表

zskiplist结构来持有这些节点

/*

• 跳跃表
  */
  typedef struct zskiplist {

  // 表头节点和表尾节点
  struct zskiplistNode *header, *tail;

  // 表中节点的数量
  unsigned long length;

  // 表中层数最大的节点的层数
  int level;

} zskiplist;

level:o(1)获取表中层最大的节点的层数。为啥要记录这个呢？

5.2 跳跃表API

函数 作用 时间复杂度
zslGetRank 返回包含给定成员和分值的节点在跳跃表中的排位， 平均O(logN)、最坏O(N);
N为跳跃表的长度
zslGetElementByRank 返回跳跃表在给定排位上的节点 平均O(logN)、最坏O(N);
N为跳跃表的长度
zslIsInRange 给定一个分值范围（range）,比如0到15，20到28，诸如此类。如果跳跃表中有至少一个节点的分值在这个范围内，那么返回1，否则返回0 跳跃表的表头节点和表尾节点，这个检测可以用O(1)复杂度完成

6.整数集合

intset(整数集合)是集合键的底层实现之一，当一个集合只包含整数值元素。并且这个集合的元素数量不多时。redis就会使用整数集合作为集合键的底层实现。

6.1 整数集合的实现

类型：int16_t、int32_t或者int64_t的整数值，并且保证集合中不会出现重复元素。
typedef struct intset {

// 编码方式
uint32_t encoding;// 集合包含的元素数量
uint32_t length;// 保存元素的数组
int8_t contents[];

} intset;

contents数组是整数集合的底层实现。整数集合的每个元素都是contents数组的一个组项。各个项在数组中按照值的大小，由小到大有序排列。且不包含重复项。

6.2 升级

添加元素到整数集合里时，并且新元素的类型比现有元素的所有类型都要长时，整数集合需要先进行升级。然后才能将元素添加到集合中。
升级步骤
1.扩充集合底层数组的空间大小，并为新元素分配空间
2.将现有元素变成现在的大小，并且放到正确的位置上，同时保持有序性
3.新元素添加到底层数组里。
向整数集里添加新元素的时间复杂度是O(N)

6.3 升级的好处

●灵活性
●节约内存

6.4 降级

不支持

7.压缩列表

列表键和哈希键的底层实现之一。列表键只包含少量列表项，且每个列表项都是小整数、长度短的字符串。redis就会使用压缩列表来做列表键的底层实现。
127.0.0.1:6379> rpush chen 1 2 “redis” “hello”
(integer) 4
127.0.0.1:6379> object encoding chen
“quicklist”

为啥我这出现的是quicklist。quicklist和ziplist有啥区别？
百度了下，quicklist是一个双向链表，一个quicklist里包含多个ziplist节点。所以ziplist还是有用的？

7.1 压缩列表的构成

压缩列表存在的目的：节约内存
它是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点，每个节点保存了一个字节数据或者一个整数值。

zlbytes：4个字节，记录整个压缩列表占用的内存字节数，内存重分配，计算zlend的位置时使用。
zltail：4字节，记录压缩列表表尾节点距离压缩列表起始地址能有多少字节，通过这个偏移量，无须遍历整个压缩列表就可以确定表尾节点的地址。
zllen：2字节，记录了压缩列表包含的节点数量，这个属性的值小于uint_max(65535)时，这个属性的值就是压缩列表包含的节点的数量。等于uint_max(65535) ，需要遍历才能得出。也就是说zllen最大等于65535，字节数限制。超过后失效
entryx：节点列表，节点的长度由节点保存的内容决定
zlend：1字节，特殊值0xff，用于标记压缩列表的末端

7.2 压缩列表节点的构成

节点可以保存：一个字节数组或者一个整数值，其中，字节数可以是以下的三种长度之一
●长度小于等于63（2^6 - 1） 字节的字节数组
●长度小于等于16383（2^14 -1 ）字节的字节数组
●长度小于等于4294967295（2^32 - 1）字节的字节数组
整数值则可以是以下六种长度的其中一种（why）
●4位长，介于0-12之间的无符号整数
●1字节长的有符号整数
●3字节长的有符号整数
●int16_t类型整数
●int32_t类型整数
●int64_t类型整数
每个节点都由previous_entry_length、encoding、content三个部分组成。

7.2.1 previous_entry_length

记录压缩列表中的前一个节点的长度。previous_entry_length属性的长度可以是1字节或者5字节。
●长度小于254字节时，1字节。否则5字节。由属性的长度决定能存的上限
这个字段的作用，可以通过指针运算。根据当前节点的起始地址来计算出前一个节点的起始地址。表尾向表头遍历时需要。

7.2.2. encoding

该属性记录了节点的content属性所保存数据的类型以及长度：

●00、01、10开头的，都是字节数组，数组的长度由编码除去最高两位之后的其他位记录
●11开头的是整数。整数的类型和长度由编码除去最高两位之后的其他位记录。

7.2.3 content

content属性负责保存节点的值。节点值可以是一个字节数组或者整数。值的类型和长度由节点的encoding属性决定。

●00:节点保存的时候一个字节数组
●001011记录了字节数组的长度11
●content属性保存着节点值“hello world”

7.3 连锁更新

redis将这种在特殊情况下产生的多次空间扩展操作称之为“连锁更新（cascade update）”
连续多个节点长度介于250-253字节的节点，如果在压缩列表的表头节点前添加一个节点，且其长度大于254，此时老的表头节点存前一个节点长度的previous_entry_length的大小会从1字节变成5字节，它本身的长度也会突破254，引发下一个节点需要重新分配内存。
最坏的情况需要对压缩列表执行n次空间重分配操作。每次空间重分配的最坏的复杂度是O(N)，连锁更新的最坏复杂度是O(N^2)
●但是因为实际发生的概率较低。对性能的影响会比较小

7.4 压缩列表api

不想写了，一些插入、删除、查找。虽然一个类是由他的属性和行为共同决定的，但是好像没啥特别的。