Redis数据结构3:REDIS_LISTNODE

REDIS_LISTNODE

REDIS_LISTNODE本质上与Java的LinkedList一致，NodeList即为链表，是基本的线性结构。C语言原生没有对链表的支持，Redis对链表进行了实现。

listNode

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

listNode的结构较为简单，本质上只有三部分：prev(前节点)，nex(后节点)，value(值)。

其中前后节点分别为一个新的listNode。

list

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;

list是对listNode的一个封装。提供了链表头指针head、链表尾节点tail、链表节点数量len、以及可以自定义实现的 dup、free、match 函数。

REDIS_LISTNODE的优势与缺陷

优势

• listNode中有两个指向前后节点的指针，这意味着listNode不需要连续的内存空间。
• listNode中用len存储了链表长度，这样获取链表长度的时间复杂度为O(1)。
• listNode 链表节使用void*指针保存节点值，并且可以通过 list 结构的dup、free和match函数指针为节点设置该节点类型特定的函数，因此链表节点可以保存各种不同类型的值。

缺点

• 链表每个节点之间的内存都是不连续的，导致其无法很好利用 CPU 缓存。能很好利用 CPU 缓存的数据结构就是数组，因为数组的内存是连续的，这样就可以充分利用 CPU 缓存来加速访问。
• 保存一个链表节点的值都需要一个链表节点结构头的分配，内存开销较大。数组只需要下标访问即可。

正因如此，Redis 3.0 的 List 对象在数据量比较少的情况下，会采用「zipList」作为底层数据结构的实现，它的优势是节省内存空间，并且是内存紧凑型的数据结构。

Redis 5.0 设计了新的数据结构 listpack，沿用了压缩列表紧凑型的内存布局。在最新的 Redis 版本，将 Hash 对象和 Zset 对象的底层数据结构替换成由 listpack 实现。