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