为什么redis使用跳表而不是红黑树实现sortedset?

跳表（Skip List）是一种高效数据结构，基于随机化原理，加速查找操作，平均时间复杂度为O(log n)，操作如插入、删除、查找简单。其结构类似链表，每层节点包含多个指针，指向对应层的下一个节点，可快速搜索多个节点，同时保证高效和简洁。

跳表的每一层是一个有序链表，从底层向上递增，每一层是下一层的子集。例如，第一层链表中的元素是底层链表中元素的间隔，第二层元素则是第一层的间隔，以此类推。跳表最高层只有一个元素，用于快速定位。支持范围查询、插入、删除、查找和合并等高级操作，适用于高效搜索引擎、缓存、排序等场景。

Redis中的有序集合（Sorted Set）基于跳表实现。每个有序集合内部包含一个跳表，节点存储成员值、score值和指向其他节点的指针。集合中元素按score值从小到大排序，跳表节点同样按照score值排序。节点通过随机生成多级索引，层级概率分布通常在2到4之间，平衡查找效率与内存占用。利用跳表特性，Redis能高效实现范围查询、排名和集合操作。

Redis选择跳表而非平衡树，原因在于跳表结构设计简化了操作，同时保持高效查找性能。Redis跳表结构定义在server.h中，具体操作实现于t_zset.c文件。跳表节点创建和释放涉及指定key、score和节点level，初始化分配内存，创建头节点并初始化。插入、删除和更新节点涉及查找节点score和后置节点score、以及根据查找节点key和后置节点key逐层定位元素。排名查询获取key对应排名则通过查找节点score和后置节点score大小及查找节点key和后置节点key逐层确定元素。score范围查询则获取score范围启始（末尾）节点。

您可能感兴趣问答

Collapsible

热门标签

热点问答