Redis面经：跳表中节点的数据结构？新节点的层数如何确认？

1. 简单说一下zset底层数据结构

答：压缩列表、跳表

1.1 简单说一下压缩列表的数据结构

答：压缩列表本质上是数组，增加了列表长度、尾部偏移量、列表元素个数、结束标识，这些标识有利于寻找首尾元素

2 跳表是什么？

答：跳表是在多级链表的基础上增加了多级索引的结构。

2.1 跳表的节点的数据结构是怎么样的？

答：直接看Redis源码

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

2.2 新节点的层数是如何确定的？

答：zslRandomLevell()返回一个随机级别，返回值介于1和ZSKIPLIST_MAXLEVEL之间

level = zslRandomLevel();
    ...
x = zslCreateNode(level,score,ele);
	...
int zslRandomLevel(void) {
    static const int threshold = ZSKIPLIST_P*RAND_MAX;
    int level = 1;
    while (random() < threshold)
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

2.3 最多多少层？

答：32

#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^64 elements */

3. 为什么不用红黑树，平衡树，要用跳表？

答：相比两种树结构（需补充）

1. 跳表在范围查找时操作简单
2. 跳表插入和删除操作简单快速
3. 代码实现难度简单