文章目录

Redis底层数据结构一、字典1.1 Hash表节点Entry1.2 Hash表dictht1.3 字典dict1.4 字典reHash1.5 小结 二、跳跃表2.1 跳跃表节点zskiplistNode2.2 跳跃表zskiplist2.3 有序集合zset2.4 跳跃表操作2.5 小结 三、参考

Redis底层数据结构

Redis底层数据结构是Redis基本数据类型和诸多功能实现的基础，字典和跳跃表是最重要的两种数据结构。

一、字典

Redis中的字典是一种以Hash表为基础的数据结构，在Redis的很多功能实现中都使用到了字典。我们来看看Hash表和字典在Redis源码中的定义等信息。下面代码在Redis源码的src/dict.h文件中，可阅读参考文章[2]。

1.1 Hash表节点Entry

dictEntry是hash表存储的单个元素，类似于Java的HashMap中的Entry /* * 哈希表节点 */ typedef struct dictEntry { // 键 void *key; // 值 union { void *val; uint64_t u64; int64_t s64; } v; // 指向下个哈希表节点，形成链表 struct dictEntry *next; } dictEntry;

1.2 Hash表dictht

/* 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;

1.3 字典dict

dict是Redis的字典，其中包含两个哈希表dictht，这是为了方便进行rehash操作。在扩容时，将其中一个dictht上的键值对rehash到另一个dictht上面，完成之后释放空间并交换两个dictht 的角色。其实字典本身的数据结构特点和Hash表是一样的，内部保存2个 Hash表以及rehashindex等辅助信息是便于实现渐进式rehash。 /* * 字典 */ 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; 字典的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去执行。

1.4 字典reHash

下面是字典结构的rehash操作函数。我对比了源码，这个是Redis2.8及一下的版本源码，3.0及以上版本源码略有不同。 /* Performs N steps of incremental rehashing. Returns 1 if there are still * keys to move from the old to the new hash table, otherwise 0 is returned. * * 执行 N 步渐进式 rehash 。 * * 返回 1 表示仍有键需要从 0 号哈希表移动到 1 号哈希表， * 返回 0 则表示所有键都已经迁移完毕。 * * Note that a rehashing step consists in moving a bucket (that may have more * than one key as we use chaining) from the old to the new hash table. * * 注意，每步 rehash 都是以一个哈希表索引（桶）作为单位的， * 一个桶里可能会有多个节点， * 被 rehash 的桶里的所有节点都会被移动到新哈希表。 * * T = O(N) */ int dictRehash(dict *d, int n) { // 只可以在 rehash 进行中时执行 if (!dictIsRehashing(d)) return 0; // 进行 N 步迁移 // T = O(N) while(n--) { dictEntry *de, *nextde; /* Check if we already rehashed the whole table... */ // 如果 0 号哈希表为空，那么表示 rehash 执行完毕 // T = O(1) if (d->ht[0].used == 0) { // 释放 0 号哈希表 zfree(d->ht[0].table); // 将原来的 1 号哈希表设置为新的 0 号哈希表 d->ht[0] = d->ht[1]; // 重置旧的 1 号哈希表 _dictReset(&d->ht[1]); // 关闭 rehash 标识 d->rehashidx = -1; // 返回 0 ，向调用者表示 rehash 已经完成 return 0; } /* Note that rehashidx can't overflow as we are sure there are more * elements because ht[0].used != 0 */ // 确保 rehashidx 没有越界 assert(d->ht[0].size > (unsigned)d->rehashidx); // 略过数组中为空的索引，找到下一个非空索引 while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++; // 指向该索引的链表表头节点 de = d->ht[0].table[d->rehashidx]; /* Move all the keys in this bucket from the old to the new hash HT */ // 将链表中的所有节点迁移到新哈希表 // T = O(1) while(de) { unsigned int 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; // 更新 rehash 索引 d->rehashidx++; } return 1; }

1.5 小结

字典也是和Hash表一样的k-v存储集合，但是是基于Hash表来实现的。在字典的内部维护了2个Hash表，来实现渐进式rehash。rehash的时候不是一次性完成，而是渐进式的将元素从一个Hash表迁移到另一个Hash表，注意一次迁移的不是一个k-v对结构dictEntry，而是按照桶为单位进行迁移的。在Redis的本身源码中，字典是很多基础功能实现的基础数据结构，比如在Redis集群中使用字典来保存集群的所有服务器节点信息，在Redis中默认包含16个数据库，每一个库对应一个redisDb的数据结构，在redisDb内部就是通过一个dict字典来保存该库下的全部键值对字典可以理解为一个优化后的Hash表，其功能和Hash几乎一样，但是做rehash的时候性能更好，以空间换取了时间。

二、跳跃表

跳跃表是一种数据结构，它基于多指针有序链表实现的，可以看成多个有序链表。在Redis中它是有序集合的底层实现之一。另外在Redis中一些涉及到排序的场景也会使用到跳跃表，比如Redis分片集群中使用跳跃表保存了槽和key之间的关系，以槽为分值键为成员对槽进行排序，便于进行区间操作，或者处理槽和键之间的关系和对槽进行rehash。

Redis中的有序集合是一种以跳跃表为基础的数据结构，我们来看看跳跃表和有序集合在Redis源码中的定义等信息。下面代码在Redis源码的src/redis.h文件中，可阅读参考文章[2]。

2.1 跳跃表节点zskiplistNode

zskiplistNode是对应跳跃表节点的数据结构。节点除了包含目标的key之外，还包含分值、前后指针、跨度等信息。 /* 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;

2.2 跳跃表zskiplist

zskiplist是对应跳跃表的数据结构。包含一个跳跃表的头尾节点指针、节点数量和最大层数。 /* * 跳跃表 */ typedef struct zskiplist { // 表头节点和表尾节点 struct zskiplistNode *header, *tail; // 表中节点的数量 unsigned long length; // 表中层数最大的节点的层数 int level; } zskiplist;

2.3 有序集合zset

zset是对应有序集合的数据结构。zset内部维护一个字典来保证按照成员取出分值，提示维护一个跳跃表来支持按照分值操作成员，比如排序等。 /* * 有序集合 */ typedef struct zset { // 字典，键为成员，值为分值 // 用于支持 O(1) 复杂度的按成员取分值操作 dict *dict; // 跳跃表，按分值排序成员 // 用于支持平均复杂度为 O(log N) 的按分值定位成员操作 // 以及范围操作 zskiplist *zsl; } zset;

2.4 跳跃表操作

跳表的查找，插入等操作，可以阅读参考文章[4]

2.5 小结

跳跃表也是一种加速查找的数据结构，内部通过多层指针和双向指针来实现加速查找，在排序和范围操作时性能较好，并基于它实现了Redis中的有序集合。相比于红黑树这样的查找结构，有下面优点，为什么Redis中不使用红黑树呢？后面给了一个表格 A.插入快。因为不需要进行旋转等操作来维护平衡性； B.更容易实现。实现比红黑树简单许多； C.支持无锁操作。 对比项红黑树复杂度跳表复杂度插入元素O(log n)O(log n)删除元素O(log n)O(log n)查找元素O(log n)O(log n)有序输出元素O(log n)O(log n)区间操作元素不如跳表性能很好 区间操作时，红黑树定位到端点后，再从首位置开始每次都要查找后继节点，相对来说是比较耗时的。跳表的区间操作，定位到2端的元素之后，顺序遍历即可，显然性能更好

三、参考

[1] CS-Notes/Redis[2] Redis源码-带注释[3] Redis 设计与实现-黄健宏[4] 拜托，面试别再问我跳表了！