当一个列表键包含了数量比较多的元素,又或者列表中包含的元素都是比较长的字符串时,Redis 就会使用链表作为列表键的底层实现
除了链表键外,发布与订阅、慢查询、监视器等功能也用到了链表,Redis 本身还使用链表来保存多个客户端的状态信息,以及使用链表来构建客户端输出缓冲区
每个链表节点用一个 listNode 结构来表示:
多个 listNode 可以通过 prev 和 next 指针组成双端链表:
链表结构:
Redis 链表特性总结如下:
- 双端
- 无环
- 带表头指针和表尾指针
- 带链表长度计数器:使得程序获取链表中节点数量的复杂度为 O(1)
- 多态:链表节点使用 void* 指针来保存节点值,并且可以通过 list 结构的 dup、free、match 三个属性为节点值设置类型特定函数