Redis中的链表

链表提供了高效的节点重排能力,以及顺序性的节点访问方式,并且可以通过增删节点来灵活地调整链表的长度。作为一种常用数据结构,链表内置在很多高级的编程语言里面, 因为Redis使用的C语言并没有内置这种数据结构,所以Redis构建了自己的链表实现。

References:

链表在Redis中的应用非常广泛,比如list的底层实现之一就是链表: 当一个list包含了数量比较多的元素, 又或者list中包含的元素都是比较长的字符串时,Redis就会使用链表作为list的底层实现。
以下展示的 integers 列表键包含了从 1 到 1024 共一千零二十四个整数:

redis> LLEN integers
(integer) 1024

redis> LRANGE integers 0 10
1) "1"
2) "2"
3) "3"
4) "4"
5) "5"
6) "6"
7) "7"
8) "8"
9) "9"
10) "10"
11) "11"

integers 列表键的底层实现就是一个链表, 链表中的每个节点都保存了一个整数值。除了链表键之外, 发布与订阅、慢查询、监视器等功能也用到了链表。

每个链表节点使用一个 adlist.h/listNode 结构来表示:

typedef struct listNode {
    struct listNode *prev; // 前一个节点
    struct listNode *next; // 下一个节点
    void *value;           // 当前节点的值
} listNode;

多个listNode可以通过prev和next指针组成双端链表:
graphviz-167adfc2e52e078d4c0e3c8a9eddec54551602fb.png

虽然仅仅使用多个listNode结构就可以组成链表, 但使用adlist.h/list 来持有链表的话, 操作起来会更方便:

typedef struct list {
    listNode *head;                      // 链表头
    listNode *tail;                      // 链表尾
    void *(*dup)(void *ptr);             // 节点值复制函数
    void (*free)(void *ptr);             // 节点值释放函数
    int (*match)(void *ptr, void *key);  // 节点值对比函数
    unsigned int len;                    // 链表长度
} list;

list结构为链表提供了表头指针head、表尾指针tail,以及链表长度计数器len,这些数据可以作为list的元数据,让list的操作更为方便。
graphviz-5f4d8b6177061ac52d0ae05ef357fceb52e9cb90.png

redis/adlist.c的第一句很好的描述了Redis的list结构:A generic doubly linked list implementation
Redis的链表和一般的双向链表差不多,节点带有prev和next指针,获取某个节点的前置节点和后置节点的复杂度都是O(1)。
表头节点的prev指针和表尾节点的next指针都指向NULL,对链表的访问以 NULL为终点。
由于有len属性对list持有的链表节点进行计数,程序获取链表中节点数量的复杂度为O(1)。

再给出Java中的LinkedList作为对比:


public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first; // 链表头

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last; // 链表尾

    ...

    // 链表的节点
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

    ...

怎么样,是不是一摸一样:)

标签: none

添加新评论

ali-01.gifali-58.gifali-09.gifali-23.gifali-04.gifali-46.gifali-57.gifali-22.gifali-38.gifali-13.gifali-10.gifali-34.gifali-06.gifali-37.gifali-42.gifali-35.gifali-12.gifali-30.gifali-16.gifali-54.gifali-55.gifali-59.gif

加载中……