redis原理之底层数据结构-跳表

1.什么是跳表

1.1 链表及其不足

链表是在程序设计中最常见的数据结构之一，它通过指针将多个链表节点连接起来，这样就可以将逻辑上同一类的数据存储到不连续的内存空间上。链表结构如下：

但是链表有一个问题，就是当链表需要查询一个元素的时候，需要从链表头部开始遍历，时间复杂度为o(n)。

2.1 跳表的诞生

针对查询链表的时间复杂度为o(n)的问题，我们可以学习B+树，给链表加上索引，采用二分查找的思想查找元素。但是二分查找是有一个前提，就是要求元素是有序的，所以我们在插入元素的时候，维护好节点的顺序。

如果元素过多，我们还可以给目录增加目录:

所以跳表由如下几部分组成。

头节点

层级：每个节点可以增加多个节点，这个曾经在跳表中一般是随机增加的，主要是为了增加搜索的速度，最多可以有32个层级。

尾节点:一般是空

所以跳表在查找元素target的时候，首先从最高层目录开始遍历，找到第一个大于target的元素e，证明target元素一定在e的左边。

2.redis对跳表的实现

redis中跳表定义的结构如下:

typedef struct zskiplistNode {
    //跳表存储的元素
    sds ele;
    //跳表存储的分数
    double score;
    //指向上一个节点的前向指针，方便从后向前遍历
    struct zskiplistNode *backward;
    //后向指针，是一个包含0-32的指针数组
    struct zskiplistLevel {
        //后向指针
        struct zskiplistNode *forward;
        //跨度
        unsigned long span;
    } level[];
} zskiplistNode;
 
typedef struct zskiplist {
    //跳表头节点
    struct zskiplistNode *header, *tail;
    //跳表的节点个数
    unsigned long length;
    //跳表的最大等级为多少
    int level;
} zskiplist;

可以看出redis为了结局自身结构的问题，增加了以下两个特性：

1.redis为了解决从尾部遍历元素的需求，所以在调表的节点之间加上了一个后向指针。
2.为了解决查询某个元素rank的需求，在不同层级节点之间维护了跨度。

所以redis的跳表结构如下

3.红黑树、跳表、B+树的区别以及使用场景

3.1 红黑树

红黑树，查询时间为o(logn)在插入元素的时候，需要通过自旋或者染色等操作来维持树结构的平衡，所以插入的时候相对耗时，并且插入元素可能影响的节点比较多。java中Map的为了解决hash冲突以及linux中对epoll的实现采用了红黑树。

3.2 B+树

B+树，紧凑，适合磁盘存储。b+树相当于一个节点拥有多个子节点，每个节点能够存储多个键值对。在查询数据的时候，能够减少磁盘随机IO的次数。但是b+树插入数据的时候，
需要进行页分裂等操作，所以插入相对耗时。mysql的底层就采用B+树存储。

3.3 跳表

跳表，适合内存存储。跳表的目录层级可能很高，但是查询也是o(log(n))的时间复杂度，而且跳表插入速度快，适合内存存储。这也是为什么redis选择跳表存储的原因。