Redis跳跃表查找技巧及优点简介（redis跳跃表怎么查找）

Redis跳跃表？能实现快速查找的特殊数据结构，与普通的简单链表及二叉树的不同之处在于结构非常严格，一般用于排序和索引功能，比如对对大量rank排名数字，改变排名，快速查找等，有利于程序员快速开发出高效性能的程序。

Redis 跳跃表实际上是一种“即查又排序”的数据结构，它采用索引、搜索树和排序算法而构成。跳跃表的查找有两个难点：一是维护合法的排序树状态，二是有效的查找算法。

在排序树状态中，Redis 跳跃表仅存在唯一的跳跃表条目。每个节点的数据由头节点索引，包括元素值、向前指针、向后指针组成，在查找过程中，需要根据已存在元素值，来建立跳跃表顺序组织，Redis 跳跃表也称作加速搜索算法，它的查找效率比线性查找算法要好很多，只需要O(log（n）)的复杂度即可实现查找。

Redis跳跃表的优点有两个：一是数据查找效率高，算法复杂度只有 O(log（n）)，比线性查找算法要快得多；二是元素特性不变，维护树状态时，只需要简单的指针操作，即可保持原有的数据结构。

以下是 Redis 跳跃表实现中，维护跳跃表状态所需要用到的代码：

void skiplist_insert(struct skiplist *list, skiplist_node_t *node)
{
    skiplist_node_t *update[list->level];
    skiplist_node_t *cursor = list->head;
    int i;
    for(i = list->level - 1; i >= 0; i--) {
        while (cursor->next[i] != NULL && 
            cursor->next[i]->value value) 
            cursor = cursor->next[i];
        update[i] = cursor;
    }
    for (i = 0; i level; i++)
        node->next[i] = update[i]->next[i];
    for (i = 0; i level; i++)
        update[i]->next[i] = node;
}

可见，Redis 跳跃表能够有效地实现快速查找的特性，可以改善一些高效性性能要求较高的应用，像排行榜类应用，ord函数，索引等，但也有其不足之处，比如维护树状态相对复杂，也将增加内存等要求，在应用这种结构时，要根据自己实际应用情况来选择最合适的数据结构。

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