Redis是工作中很常用的，这里将比较普遍使用的结构研究了下做个备忘。
hash
实现和dnspod的dataset半斤八两，本质上是个二维数组，通过将key哈希作为一维的下表，第二维的数组存相同哈希的元素，查找使用遍历的方式，所以这里redis做了优化，当满足条件的时候(数组数量太大)会进行rehash，动态扩大桶的数量来减少最后一维遍历的次数.
函数名称 | 作用 | 复杂度 |
dictCreate | 创建一个新字典 | O(1) |
dictResize | 重新规划字典的大小 | O(1) |
dictExpand | 扩展字典 | O(1) |
dictRehash | 对字典进行N步渐进式Rehash | O(N) |
_dictRehashStep | 对字典进行1步尝试Rehash | O(N) |
dictAdd | 添加一个元素 | O(1) |
dictReplace | 替换给定key的value值 | O(1) |
dictDelete | 删除一个元素 | O(N) |
dictRelease | 释放字典 | O(1) |
dictFind | 查找一个元素 | O(N) |
dictFetchValue | 通过key查找value | O(N) |
dictGetRandomKey | 随机返回字典中一个元素 | O(1) |
字典结构
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;
这里哈希表有两个，一般都用ht[0]，当需要rehash的时候会创建一个比ht[0]大的 2 的 N 次方的ht[1]，然后渐进式的将数据dictEntry移过去(除了定时的rehash，在每次操作哈希表时都会_dictRehashStep)，完成后将ht[1]替换ht[0]
zset
zset本质就是list,只不过每个元素都有若干个指向后继span长的指针，这样简单的设计大大提高了效率，使得可以比拟平衡二叉树，查找、删除、插入等操作都可以在对数期望时间内完成，对比平衡树，跳跃表的实现要简单直观很多。
/* 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;
/*
* 跳跃表
*/
typedef struct zskiplist {
// 表头节点和表尾节点
struct zskiplistNode *header, *tail;
// 表中节点的数量
unsigned long length;
// 表中层数最大的节点的层数
int level;
} zskiplist;
/*
* 有序集合
*/
typedef struct zset {
// 字典，键为成员，值为分值
// 用于支持 O(1) 复杂度的按成员取分值操作
dict *dict;
// 跳跃表，按分值排序成员
// 用于支持平均复杂度为 O(log N) 的按分值定位成员操作
// 以及范围操作
zskiplist *zsl;
} zset;
虽然这种方式排序查找很快，但是修改的话就得多做些工作了
/* Delete an element with matching score/object from the skiplist.
*
* 从跳跃表 zsl 中删除包含给定节点 score 并且带有指定对象 obj 的节点。
*
* T_wrost = O(N^2), T_avg = O(N log N)
*/
int zslDelete(zskiplist *zsl, double score, robj *obj)
intset
typedef struct intset {
uint32_t encoding; //所使用类型的长度，4\8\16
uint32_t length; //元素个数
int8_t contents[]; //保存元素的数组
} intset;
intset其实就是数组，有序、无重复地保存多个整数值，查找用的是二分查找 * T = O(log N)，添加的话在找到对应的数组中应该存在的位子后使用memmove向后移出空位填补(当然需要先realloc预分配空间)，同理删除也是用memmove向前移动
set
当使用整数时，使用intset，否则使用哈希表
其他的关于网络事件处理，epoll，回调，拆包都和正常使用差不多，关于错误处理EINTR(系统调用期间发生中断)和EAGAIN 继续重试而如果是EPOLLHUP或EPOLLERR则让io该读读该写写，有错处理就是了。