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該讀讀該寫寫，有錯處理就是了。