|
Hash表节点：
- typedef struct dictEntry {
- // 键
- void *key;
- // 值
- union {
- void *val;
- uint64_t u64;
- int64_t s64;
- } v;
- // 指向下个哈希表节点，形成链表
- struct dictEntry *next; // 单链表结构
- } dictEntry;
字典：
- typedef struct dict {
- // 类型特定函数
- dictType *type;
- // 私有数据
- void *privdata;
- // 哈希表
- dictht ht[2];
- // rehash 索引
- // 当 rehash 不在进行时，值为 -1
- int rehashidx; /* rehashing not in progress if rehashidx == -1 */
- } dict;
可以看出：
- Reids的Hash采用链地址法来处理冲突，然后它没有使用红黑树优化。
- 哈希表节点采用单链表结构。
- rehash优化。
下面我们讲一下它的rehash优化。
3.2 rehash
当哈希表的键对泰国或者太少，就需要对哈希表的大小进行调整，redis是如何调整的呢？
- 我们仔细可以看到dict结构里有个字段dictht ht[2]代表有两个dictht数组。第一步就是为ht[1]哈希表分配空间，大小取决于ht[0]当前使用的情况。
- 将保存在ht[0]中的数据rehash(重新计算哈希值)到ht[1]上。
- 当ht[0]中所有键值对都迁移到ht[1]后，释放ht[0]，将ht[1]设置为ht[0]，并ht[1]初始化，为下一次rehash做准备。
3.3 渐进式rehash
我们在3.2中看到，redis处理rehash的流程，但是更细一点的讲，它如何进行数据迁的呢？
这就涉及到了渐进式rehash，redis考虑到大量数据迁移带来的cpu繁忙(可能导致一段时间内停止服务)，所以采用了渐进式rehash的方案。步骤如下：
- 为ht[1]分配空间，同时持有两个哈希表(一个空表、一个有数据)。
- 维持一个技术器rehashidx，初始值0。
- 每次对字典增删改查，会顺带将ht[0]中的数据迁移到ht[1],rehashidx++(注意：ht[0]中的数据是只减不增的)。
- 直到rehash操作完成，rehashidx值设为-1。
它的好处：采用分而治之的思想，将庞大的迁移工作量划分到每一次CURD中，避免了服务繁忙。
4. 跳跃表
这个数据结构是我面试中见过最多的，它其实特别简单。学过的人可能都知道，它和平衡树性能很相似，但为什么不用平衡树而用skipList呢?
4.1 skipList & AVL 之间的选择
- 从算法实现难度上来比较，skiplist比平衡树要简单得多。
- 平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速。
- 查找单个key，skiplist和平衡树的时间复杂度都为O(log n)，大体相当。
- 在做范围查找的时候，平衡树比skiplist操作要复杂。
- skiplist和各种平衡树（如AVL、红黑树等）的元素是有序排列的。
可以看到，skipList中的元素是有序的，所以跳跃表在redis中用在有序集合键、集群节点内部数据结构
4.2 源码
跳跃表节点：
- typedef struct zskiplistNode {
- // 后退指针
- struct zskiplistNode *backward;
- // 分值
- double score;
- // 成员对象
- robj *obj;
- // 层
- struct zskiplistLevel {
- // 前进指针
- struct zskiplistNode *forward;
- // 跨度
- unsigned int span;
- } level[];
- } zskiplistNode;
（编辑：晋中站长网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
