redis中zset有序集合的底层实现

跳跃表

Zset 是一个有序的链表结构，其底层的数据结构是跳跃表 skiplist，其结构如下：

typedef struct zskiplistNode {
    //成员对象
   robj *obj;
    //分值
    //后退指针
   struct zskiplistNode *backward;
    //层
   struct zskiplistLevel {
        struct zskiplistNode *forward;//前进指针
        unsigned int span;//跨度
   } level[];
 } zskiplistNode;
 
typedef struct zskiplist {
    //表头节点和表尾节点
   struct zskiplistNode *header, *tail;
    //表中节点的的数量
   unsigned long length;
    //表中层数最大的节点层数
   int level;
 } zskiplist;

在查询过程中跳跃着前进。由于存在后退指针，如果查询时超出了范围，通过后退指针回退到上一个节点后仍可以继续向前遍历。

作者：admin

PHP面试网 站点 QQ交谈