搜云库技术团队
redis底层是用什么结构来存储数据的呢？
我们从源码上去理解就会容易的多：
redis底层是使用C语言来编写的，我们可以看到它的数据结构声明。一个 dict 有两个dictht，一个dictht有一个dictEntry数组，每个dictEntry有next指针，redisObject是真正存储redis各种类型的结构。因此是一个链表结构。从上面的分析可以看出Redis用拉链法解决冲突的哈希表结构。
“链地址法”的问题在于当碰撞剧烈时，性能退化严重，例如：当有n个数据，m个槽位，如果m=1，则整个Hash表退化为链表，查询复杂度O(n)
为了避免Hash碰撞，Redis的方案是“双dictht”，正常流程使用一个dictht，当发现碰撞剧烈（判断依据为当前槽位数和Key数的对比），分配一个更大的dictht，然后逐步将数据从老的dictht迁移到新的dictht上去。这就需要进行rehash。
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
unsigned long iterators; /* number of iterators currently running */
} dict;
/* This is our hash table structure. Every dictionary has two of this as we
* implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
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;
double d;
} v;
struct dictEntry *next;
} dictEntry;
//redisObject是真正存储redis各种类型的结构，定义如下：
#define REDIS_STRING 0
#define REDIS_LIST 1
#define REDIS_SET 2
#define REDIS_ZSET 3
#define REDIS_HASH 4
typedef struct redisObject {
unsigned type:1; //逻辑类型
unsigned notused:2; /* Not used */
unsigned encoding:4; //物理存储类型
unsigned lru:22; /* lru time (relative to server.lruclock) */
int refcount;
void *ptr; //具体数据
} robj;
如下是rehash方法的源码：
rehash 操作不是一次性完成，而是采用渐进方式，这是为了避免一次性执行过多的 rehash 操作给服务器带来过大的负担。
- 渐进式 rehash 通过记录 dict 的 rehashidx 完成，它从0开始然后每执行一次rehash都会递增。例如在一次 rehash 中，要把 dict[0] rehash到dict[1]，这一次会把 dict[0] 上 table[rehashidx] 的键值对 rehash 到 dict[1] 上，dict[0] 的 table[rehashidx] 指向 null，并令 rehashidx++。
- 在 rehash 期间，每次对字典执行添加、删除、查找或者更新操作时，都会执行一次渐进式 rehash。
- 采用渐进式 rehash 会导致字典中的数据分散在两个 dictht 上，因此对字典的操作也需要到对应的 dictht 去执行。
int dictRehash(dict *d, int n) {
int empty_visits = n * 10; /* Max number of empty buckets to visit. */
if (!dictIsRehashing(d)) return 0;
while (n-- && d->ht[0].used != 0) {
dictEntry *de, *nextde;
/* Note that rehashidx can't overflow as we are sure there are more
* elements because ht[0].used != 0 */
assert(d->ht[0].size > (unsigned long) d->rehashidx);
while (d->ht[0].table[d->rehashidx] == NULL) {
d->rehashidx++;
if (--empty_visits == 0) return 1;
}
de = d->ht[0].table[d->rehashidx];
/* Move all the keys in this bucket from the old to the new hash HT */
while (de) {
uint64_t h;
nextde = de->next;
/* Get the index in the new hash table */
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
d->ht[0].used--;
d->ht[1].used++;
de = nextde;
}
d->ht[0].table[d->rehashidx] = NULL;
d->rehashidx++;
}
/* Check if we already rehashed the whole table... */
if (d->ht[0].used == 0) {
zfree(d->ht[0].table);
d->ht[0] = d->ht[1];
_dictReset(&d->ht[1]);
d->rehashidx = -1;
return 0;
}
/* More to rehash... */
return 1;
}
那底层数据的有序性是如何实现的呢？
跳跃表是有序集合的底层实现之一。
- 跳跃表是基于多指针有序链表实现的，可以看成多个有序链表。
- 跳跃表是一种随机化数据结构，查找、添加、删除操作都可以在对数期望时间下完成。
- 跳跃表目前在 Redis 的唯一作用，就是作为有序集类型的底层数据结构（之一，另一个构成有序集的结构是字典）。
- 与红黑树等平衡树相比，跳跃表具有以下优点：
- 插入速度非常快速，因为不需要平衡树的旋转操作；
- 更容易实现；
- 支持无锁操作。
跳跃表的定义可以在任何一本算法或数据结构的书中找到， 在这不介绍跳跃表的具体实现方式或者具体的算法。推荐一篇漫画，可以快速理解跳跃表，想要深入理解跳跃表，推荐一篇博客。
