
Redis 核心数据结构(二)
在上一篇文章: Redis 核心数据结构(1) 中,介绍了链表、ziplist、quicklist 数据结构。这篇文章,来介绍一下 skiplist、dict。
skiplist 跳跃表是一种有序数据结构,支持平均 O(logN)、最坏 O(N) 复杂度的节点查找;大部分情况效率可以和平衡树相媲美,实现却比平衡树简单。
跳跃表就是 Redis 中有序集合键的底层实现之一。
server.h typedef struct zskiplistNode { sds ele; double score; struct zskiplistNode backward; struct zskiplistLevel { struct zskiplistNode forward; unsigned long span; } level[]; } zskiplistNode; typedef struct zskiplist { struct zskiplistNode header, tail; unsigned long length; int level; } zskiplist; typedef struct zset { dict dict; zskiplist zsl; } zset; skiplist,顾名思义,首先它是一个list。实际上,它是在有序链表的基础上发展起来的。