赞
踩
链表提供了高效的节点重排能力,以及顺序性节点的访问方式,并且可以通过增删节点来灵活的调整链表的长度。
作为一种常用的数据结构,链表内置在很多高级的编程语言里面,因为Redis使用的C语言并没有内置这种数据结构,所以Redis自己构建了自己的链表实现。
链表在Redis中的应用十分广泛,比如列表键的底层实现之一就是链表,当一个列表键包含了数量比较多的元素时,又或者列表中包含的元素都是比较长的字符串时,Redis就会使用链表作为列表键的底层实现,除了列表键的底层是链表外,发布与订阅,慢查询,监视器等功能也用到了链表,Redis服务器本身还使用来保存多个客户端的状态信息,以及使用链表来保存多个客户端的状态信息,以及使用链表来构建客户端输出缓冲区。
每个链表节点用一个adlist.h/listNode结构来表示:
typedef struct listNode {
//前置节点
struct listNode *prev;
//后置节点
struct listNode *next;
//节点的值
void *value;
}listNode;
多个listNode可以通过prev和next指针组成双端链表,如图2-1所示:
虽然仅仅用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 结构为链表提供了head,表尾指针tail,以及链表的长度计数器len,而dup,free,和match成员则是用于实现多态链表所需的类型特定函数:
图2-2是由一个list结构和三个listNode 结构组成的链表。
Redis链表实现的特性可以总结如下
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。