Redis跳跃表实现高效查找的精妙之树（redis 跳跃表 树）

Redis跳跃表属于常用的非关系型数据库数据结构，作为一种索引结构，其事件复杂度达到O(logn)，性能比红黑树要高数倍，是实现高效查找的精妙之树。

Redis跳跃表（Skiplist）是一种内存数据结构，将数据组织为多级索引，以概率的方式实现了O(logN)复杂度的查找算法，性能比红黑树要高数倍。

Redis跳跃表由节点Node组成，每个Node有几个字段：score，value，level，backward和forward，以及一个指针数组forward。score和value字段用于存储用户数据，level字段表示节点所在的层级，backward和forward字段分别表示节点的前驱和后继节点，forward指针数组用来实现跳跃表跳跃查找机制。

Redis跳跃表节点存储结构示意图如下：


利用Redis跳跃表实现高效查找有2种方法：

（1）普通查询：

普通查询根据score进行查询，从跳跃表头节点开始遍历，比较当前节点的score，若score满足条件则找到正确结果，若score不满足条件则向下移动查找。

下面的代码演示了Redis跳跃表的普通查询方法：

// redis skip list common query 
node *curnode;
for (curnode = head; curnode != NULL && curnode->level[0].forward != NULL; )
{
    if (curnode->level[0].forward->score >= score)
        curnode = curnode->level[0].forward;
    else
        break;
}
if (curnode->score == score) {
    // get score node
}
``` 
（2）范围查询：

范围查询根据score的范围进行查询，从跳跃表头节点开始遍历。先从最底层level[0]节点开始向后遍历，找到第一个score大于等于min_score的节点node；接着从最高层level[n]找到最后一个score小于等于max_score的节点node'。之后使用node和node'进行范围遍历level[0]节点，得到所有满足条件的节点。

下面的代码演示了Redis跳跃表的范围查询方法：

// redis skip list range query

node *min_node, *max_node;

for (int i = SKIP_LIST_MAX_LEVEL-1; i >= 0; i–)

{

for (min_node = head->level[i].forward; min_node != NULL && min_node->score level[i].forward);

for (max_node = head->level[i].forward; max_node != NULL && max_node->score level[i].forward);

if (min_node && max_node) {

break;

}

}

for (node *curnode=min_node; curnode && curnode->scorelevel[0].forward)

{

// get range node

}

“`

以上是Redis跳跃表实现高效查找的实现原理，它的优势在于可以用一种简单的非线性结构获得接近于线性的查找性能，节省大量的时间资源，

实现了高效查找的精妙之树。未来Redis跳跃表的发展前景广阔，期待更多的应用场景出现。

香港服务器首选树叶云，2H2G首月10元开通。
树叶云（www.IDC.Net）提供简单好用，价格厚道的香港/美国云服务器和独立服务器。IDC+ISP+ICP资质。ARIN和APNIC会员。成熟技术团队15年行业经验。