存储

在上一篇文章： 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。实际上，它是在有序链表的基础上发展起来的。

Redis 目前是使用最广泛的缓存中间件。其突出特点就是支持多种常见的数据结构。对比 JDK 集合类的实现，Redis 的实现表现出很多独到之处，很多地方设计得别具匠心。下面就来简要介绍一下。 linkedlist Redis 底层也有很多地方使用到 linkedlist，并且也是双向链表。 adlist.h typedef struct listNode { struct listNode *prev; struct listNode *next; void *value; } listNode; typedef struct listIter { listNode *next; int direction; } listIter; typedef struct list { listNode *head; listNode *tail; void *(*dup)(void *ptr); void (*free)(void *ptr); int (*match)(void *ptr, void *key); unsigned long len; } list; Redis 的 linkedlist 实现特点是： 双向：节点带有前后指针； 无环：首尾没有相连，所以没有构成环状；