Redis设计与实现——链表

2015-8-18 diaba Nosql

    Redis链表介绍    


    链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度。


    链表结构

    redis中每个链表(通过prev和next指针组成双向链表)节点使用一个adlist.c/listNode结构来表示：

        typedef struct listNode {

            struct listNode *prev;

            struct listNode *next;

            void *value;

        }listNode;


    使用adlist.h/list来持有链表，操作起来会更方便：

    typedef struct list{

        listNode *head;


        listNode *tail;


        //链表所包含的节点数

        unsigned long len;


        //节点值复制函数

        void *(*dup)(void *ptr);


        //节点释放函数

        void (*free)(void *ptr);


        //节点值对比函数

        int (*match)(void *ptr,void *key);

    }list;


    Redis链表实现的特性总结如下：

    1）双端：链表节点带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度都是O(1)。

    2）无环：表头节点的prev指针和表尾节点的next指针都指向NULL，对链表的访问以NULL为终结。

    3）带表头指针和表尾指针：通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾结点的复杂度为O(1)。

    4）带链表长度计数器：程序使用list结构的len属性来对list持有的链表节点进行计数，程序获取链表中节点数量的复杂度是O(1)。

    5）多态：链表节点使用void*指针来保存节点值，并可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以保存各种不同类型的值。


    重点回顾：

            1）链表被广泛用于实现redis的各种功能，比如列表键、发布与订阅、慢查询、监视器等。

            2）每个链表节点由一个listNode结构来表示，每个节点都有一个指向前置节点和后置节点的指针，所以redis的链表实现是双向链表。

            3）每个链表使用list结构来表示，这个结构带有头节点指针和表尾结点指针，以及链表长度等信息。

            4）因为链表的表头节点的前置节点和表尾结点的后置节点都指向NULL，所以redis的链表是个无环链表。

            5）通过为链表设置不同的类型特定函数，redis的链表可以用来保存各种不同类型的值。




« Binary Tree Paths | Redis设计与实现——简单动态字符串»

发表评论：

Powered by emlog 京ICP备15045175号-1 Copyright © 2022