AI 助理
备案控制台
开发者社区 数据库 文章 正文

跳表介绍

2021-09-15 250
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 详细介绍了跳表的原理及应用

  跳跃表（英文名：Skip List），于 1990 年 William Pugh 发明，是一个可以在有序元素中实现快速查询的数据结构，其插入，查找，删除操作的平均效率都为 $O(logn)$。
  跳跃表的整体性能可以和二叉查找树（AVL 树，红黑树等）相媲美，其在 Redis 和 LevelDB 中都有广泛的应用。
blockchain
  每个结点除了数据域，还有若干个指针指向下一个结点。
  整体上看，Skip List 就是带有层级结构的链表（结点都是排好序的），最下面一层（level 0）是所有结点组成的一个链表，依次往上，每一层也都是一个链表。不同的是，它们只包含一部分结点，并且越往上结点越少。仔细观察你会发现，通过增加层数，从当前结点可以直接访问更远的结点（这也就是 Skip List 的精髓所在），就像跳过去一样，所以取名叫 Skip List（跳跃表）。

过程分析

先来看下跳跃表的整体代码结构：

#define P 0.25
#define MAX_LEVEL 32

struct Node
{
    int key;
    Node ** forward;
    Node(int key = 0, int level = MAX_LEVEL)
    {
        this->key = key;
        forward = new Node*[level];
        memset(forward, 0, level * sizeof(Node*));
    }
};

class SkipList
{
private:
    Node * header;
    int level;
private:
    int random_level();
public:
    SkipList();
    ~SkipList();
    bool insert(int key);
    bool find(int key);
    bool erase(int key);
    void print();
};

2.1、插入

blockchain
首先，我们要找到 10 在每一层应该被插入的位置，因此需要一个临时数组 update[] 来记录位置信息。
其次，我们要确定结点 10 的层数（结点 9 的层数为 2，结点 12 的层数为 1）。

  理想的跳跃表结构是：第一层有全部的结点，第二层有 1 2 的结点，且是均匀间隔的，第三层有 1 4 的结点，且也是均匀间隔的...，那么整个表的层数就是 $logn$。每一次插入一个新结点时，最好的做法就是根据当前表的结构得到一个合适的层数，插入后可以让跳跃表尽量接近理想的结构，但这在实现上会非常困难。Pugh 的论文中提出的方法是根据概率随机为新结点生成一个层数，具体的算法如下：

  1. 给定一个概率 p（p 小于 1），产生一个 [0,1) 之间的随机数；
  2. 如果这个随机数小于 p，则层数加 1；
  3. 重复以上动作，直到随机数大于概率 p（或层数大于程序给定的最大层数限制）。

  虽然随机生成的层数会打破理想结构，但这种结构的期望复杂度依旧是 $O(logn)$，稍后文尾会给出证明。

最后，把结点 10 和它的前后结点连起来就行了。

int SkipList::random_level()
{
    int level = 1;

    while ((rand() & 0xffff) < (P * 0xffff) && level < MAX_LEVEL)
        level++;

    return level;
}

bool SkipList::insert(int key)
{
    Node * node = header;
    Node * update[MAX_LEVEL];
    memset(update, 0, MAX_LEVEL * sizeof(Node*));

    // 找到该结点在每一层应该被插入的位置
    for (int i = level - 1; i >= 0; i--)
    {
        while (node->forward[i] && node->forward[i]->key < key)
            node = node->forward[i];

        update[i] = node;
    }

    node = node->forward[0];

    if (node == nullptr || node->key != key)
    {
        int new_level = random_level();

        // 若新生成的层数比之前的大，那么高出的部分需特殊处理
        if (new_level > level)
        {
            for (int i = level; i < new_level; i++)
                update[i] = header;

            level = new_level;
        }

        Node * new_node = new Node(key, new_level);

        // 前后结点连接起来
        for (int i = 0; i < new_level; i++)
        {
            new_node->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = new_node;
        }

        return true;
    }

    return false;
}

2.2 查找
blockchain
查找操作很简单，例如上图，现要查找 20，

  1. 从最高层开始找，17 < 20，继续往后，发现是 NULL，则往下一层继续查找；
  2. 25 > 20，则往下一层继续查找；
  3. 找到 20。
bool SkipList::find(int key)
{
    Node * node = header;

    for (int i = level - 1; i >= 0; i--)
    {
        while (node->forward[i] && node->forward[i]->key <= key)
            node = node->forward[i];

        if (node->key == key)
            return true;
    }

    return false;
}

2.3、删除

blockchain
  删除操作跟插入操作类似。 首先找到我们要删除结点的位置，在查找时使用临时空间来记录结点在每一层的位置，接着就是逐层的链表删除操作。 最后记住要释放空间。 删除结点之后，如果最高层没有结点存在，那么相应的，跳跃表的层数就应该降低。

bool SkipList::erase(int key)
{
    Node * node = header;
    Node * update[MAX_LEVEL];
    memset(update, 0, MAX_LEVEL * sizeof(Node*));

    // 找到要删除结点的位置
    for (int i = level - 1; i >= 0; i--)
    {
        while (node->forward[i] && node->forward[i]->key < key)
            node = node->forward[i];
        update[i] = node;
    }

    node = node->forward[0];

    if (node && node->key == key)
    {
        // 把待删除结点的前后结点连接起来
        for (int i = 0; i < level; i++)
            if (update[i]->forward[i] == node)
                update[i]->forward[i] = node->forward[i];

        delete node;

        // 如果最高层没有结点存在，那么相应的，跳跃表的层数就应该降低
        for (int i = level - 1; i >= 0; i--)
        {
            if (header->forward[i] == nullptr)
                level--;
            else
                break;
        }
    }

    return false;
}

完整代码

#include <iostream>
#include <cstdlib>
#include <cstring>

#define P 0.25
#define MAX_LEVEL 32

using namespace std;

struct Node
{
    int key;
    Node ** forward;
    Node(int key = 0, int level = MAX_LEVEL)
    {
        this->key = key;
        forward = new Node*[level];
        memset(forward, 0, level * sizeof(Node*));
    }
};

class SkipList
{
private:
    Node * header;
    int level;
private:
    int random_level();
public:
    SkipList();
    ~SkipList();
    bool insert(int key);
    bool find(int key);
    bool erase(int key);
    void print();
};

int SkipList::random_level()
{
    int level = 1;

    while ((rand() & 0xffff) < (P * 0xffff) && level < MAX_LEVEL)
        level++;

    return level;
}

SkipList::SkipList()
{
    header = new Node;
    level = 0;
}

SkipList::~SkipList()
{
    Node * cur = header;
    Node * next = nullptr;

    while (cur)
    {
        next = cur->forward[0];
        delete cur;
        cur = next;
    }

    header = nullptr;
}

bool SkipList::insert(int key)
{
    Node * node = header;
    Node * update[MAX_LEVEL];
    memset(update, 0, MAX_LEVEL * sizeof(Node*));

    // 找到该结点在每一层应该被插入的位置
    for (int i = level - 1; i >= 0; i--)
    {
        while (node->forward[i] && node->forward[i]->key < key)
            node = node->forward[i];

        update[i] = node;
    }

    node = node->forward[0];

    if (node == nullptr || node->key != key)
    {
        int new_level = random_level();

        // 若新生成的层数比之前的大，那么高出的部分需特殊处理
        if (new_level > level)
        {
            for (int i = level; i < new_level; i++)
                update[i] = header;

            level = new_level;
        }

        Node * new_node = new Node(key, new_level);

        // 前后结点连接起来
        for (int i = 0; i < new_level; i++)
        {
            new_node->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = new_node;
        }

        return true;
    }

    return false;
}

bool SkipList::find(int key)
{
    Node * node = header;

    for (int i = level - 1; i >= 0; i--)
    {
        while (node->forward[i] && node->forward[i]->key <= key)
            node = node->forward[i];

        if (node->key == key)
            return true;
    }

    return false;
}

bool SkipList::erase(int key)
{
    Node * node = header;
    Node * update[MAX_LEVEL];
    memset(update, 0, MAX_LEVEL * sizeof(Node*));

    // 找到要删除结点的位置
    for (int i = level - 1; i >= 0; i--)
    {
        while (node->forward[i] && node->forward[i]->key < key)
            node = node->forward[i];
        update[i] = node;
    }

    node = node->forward[0];

    if (node && node->key == key)
    {
        // 把待删除结点的前后结点连接起来
        for (int i = 0; i < level; i++)
            if (update[i]->forward[i] == node)
                update[i]->forward[i] = node->forward[i];

        delete node;

        // 如果最高层没有结点存在，那么相应的，跳跃表的层数就应该降低
        for (int i = level - 1; i >= 0; i--)
        {
            if (header->forward[i] == nullptr)
                level--;
            else
                break;
        }
    }

    return false;
}

void SkipList::print()
{
    Node * node = nullptr;

    for (int i = 0; i < level; i++)
    {
        node = header->forward[i];
        cout << "Level " << i << " : ";
        while (node)
        {
            cout << node->key << " ";
            node = node->forward[i];
        }
        cout << endl;
    }

    cout << endl;
}

int main()
{
    SkipList sl;

    // test "insert"
    sl.insert(3);
    sl.insert(9);
    sl.insert(1); sl.insert(1);
    sl.insert(4);
    sl.insert(2); sl.insert(2);
    sl.insert(5);
    sl.insert(6);
    sl.insert(7);
    sl.insert(8);
    sl.insert(10);
    sl.insert(11);
    sl.insert(12);
    sl.print();

    // test "find"
    cout << sl.find(50) << endl;
    cout << sl.find(2) << endl;
    cout << sl.find(7) << endl << endl;

    // test "erase"
    sl.erase(1);
    sl.print();
    sl.erase(10);
    sl.print();
    sl.erase(11);
    sl.print();

    return 0;
}

运行如下（注意：结点层数采用的是随机值，故不同电脑可能会有不同的运行结果）：

Level 0 : 1 2 3 4 5 6 7 8 9 10 11 12
Level 1 : 3 4 6 9 10 11
Level 2 : 4 10 11
Level 3 : 10 11
Level 4 : 10 11
Level 5 : 10 11
Level 6 : 10

0
1
1

Level 0 : 2 3 4 5 6 7 8 9 10 11 12
Level 1 : 3 4 6 9 10 11
Level 2 : 4 10 11
Level 3 : 10 11
Level 4 : 10 11
Level 5 : 10 11
Level 6 : 10

Level 0 : 2 3 4 5 6 7 8 9 11 12
Level 1 : 3 4 6 9 11
Level 2 : 4 11
Level 3 : 11
Level 4 : 11
Level 5 : 11

Level 0 : 2 3 4 5 6 7 8 9 12
Level 1 : 3 4 6 9
Level 2 : 4

效率分析与证明

首先回顾下插入操作中随机生成层数的函数：

#define P 0.25
#define MAX_LEVEL 32

int SkipList::random_level()
{
    int level = 1;

    while ((rand() & 0xffff) < (P * 0xffff) && level < MAX_LEVEL)
        level++;

    return level;
}

参考文献:
https://segmentfault.com/a/1190000022545575
https://www.qtmuniao.com/2020/07/03/leveldb-data-structures-skip-list/
https://segmentfault.com/a/1190000023927761
https://syt-honey.github.io/2019/03/23/17-%E8%B7%B3%E8%A1%A8%EF%BC%9A%E4%B8%BA%E4%BB%80%E4%B9%88Redis%E4%B8%80%E5%AE%9A%E8%A6%81%E7%94%A8%E8%B7%B3%E8%A1%A8%E6%9D%A5%E5%AE%9E%E7%8E%B0%E6%9C%89%E5%BA%8F%E9%9B%86%E5%90%88%EF%BC%9F/
https://www.jianshu.com/p/d4c2accd30fc
https://qimok.cn/787.html
https://segmentfault.com/a/1190000021618668 Redis系列(七)底层数据结构之跳跃表
https://www.jianshu.com/p/9d8296562806

文章标签：
NoSQL
Redis
算法
游客k2zukogmgsnyq
目录
相关文章
游客2xksyu44sqbag
|
Linux 编译器 开发者
Linux设备树解析：桥接硬件与操作系统的关键架构
在探索Linux的庞大和复杂世界时🌌，我们经常会遇到许多关键概念和工具🛠️，它们使得Linux成为了一个强大和灵活的操作系统💪。其中，"设备树"（Device Tree）是一个不可或缺的部分🌲，尤其是在嵌入式系统🖥️和多平台硬件支持方面🔌。让我们深入了解Linux设备树是什么，它的起源，以及为什么Linux需要它🌳。
游客2xksyu44sqbag
445 0
Linux设备树解析：桥接硬件与操作系统的关键架构
元乙
|
存储 监控 算法
ClickHouse源码分析-压缩算法大揭秘
ClickHouse在近年来增加了很多压缩算法，最主要的改进还是为了更好的适应时序场景，提高压缩率，节省存储空间。本期就给大家带来ClickHouse的压缩算法介绍。
元乙
5655 0
ClickHouse源码分析-压缩算法大揭秘
奔跑的数据
|
Web App开发 数据采集 存储
WebDriver与Chrome DevTools Protocol：如何在浏览器自动化中提升效率
本文探讨了如何利用Chrome DevTools Protocol (CDP) 与 Selenium WebDriver 提升浏览器自动化效率，结合代理IP技术高效采集微博数据。通过CDP，开发者可直接操作浏览器底层功能，如网络拦截、性能分析等，增强控制精度。示例代码展示了如何设置代理IP、cookie及user-agent来模拟真实用户行为，提高数据抓取成功率与稳定性。适用于需要频繁抓取互联网数据的应用场景。
奔跑的数据
1108 3
WebDriver与Chrome DevTools Protocol：如何在浏览器自动化中提升效率
北京宏哥
|
6月前
|
运维 负载均衡 数据可视化
零门槛、低成本或无成本、轻松部署您的专属DeepSeek-R1 满血版4种解决方案
宏哥在仔细阅读了所有评测报告后，发现视频演示较少，因此决定制作一个涵盖四种部署方案的视频教程及评测。视频更加直观，便于用户理解。
北京宏哥
373 2
1100237741946300
|
SQL 数据库 UED
SQL查询功能的全面解析与实用技巧
SQL（Structured Query Language）作为数据库管理的核心语言，其查询功能是实现数据检索、分析和报告的关键
1100237741946300
601 0
讓丄帝愛伱
|
JavaScript
Proxy error: Could not proxy request错误解决
Proxy error: Could not proxy request错误解决
讓丄帝愛伱
992 0
xdijjasdcvwta
|
Python
Python中的try-except异常处理机制
Python中的try-except异常处理机制
xdijjasdcvwta
227 0
编程千纸鹤
|
数据可视化 数据挖掘 关系型数据库
招聘信息数据分析及可视化|以51JOB为例进行
招聘信息数据分析及可视化|以51JOB为例进行
编程千纸鹤
655 0
技术小达人
|
数据采集 监控 搜索推荐
附方法论｜数禾科技X瓴羊：3000字干货分享数据资产建设实践
附方法论｜数禾科技X瓴羊：3000字干货分享数据资产建设实践
技术小达人
237 0
理想七旬
|
缓存 Ubuntu Linux
docker的安装和常用命令
最近学习了docker做了一些笔记，跟朋友们分享一下
理想七旬
855 0

热门文章

最新文章

  • 1
    【资料合集】红包在线技术峰会回顾集锦：讲义PDF+活动视频！
  • 2
    什么是WPA3？与WPA2有啥区别？
  • 3
    超简单：mac导出微信聊天记录（附上粉丝群全部聊天记录）
  • 4
    C基础——使用printf打印各种数据类型的方式（示例）
  • 5
    注意：线程的执行顺序与你想的并不一样！！
  • 6
    linux下的swap分区
  • 7
    sPower加州339MW光伏项目获7.86亿美元融资
  • 8
    精典的正则表达式
  • 9
    简单的zip压缩和解压缩
  • 10
    Lvs+keepalived+mysql 双主。
  • 1
    基于C#实现的支持文件传输的Socket聊天室
    91
  • 2
    Gateway 网关坑我！ 被这个404 问题折腾了一年？
    226
  • 3
    Service Mesh：原则、挑战和演变
    61
  • 4
    DDD领域驱动设计：实践中的聚合
    79
  • 5
    【详细教程】如何在Ubuntu上本地部署Dify？
    156
  • 6
    Dapr：用于构建分布式应用程序的便携式事件驱动运行时
    58
  • 7
    阿里云gpu云服务器收费价格，热门实例简介和最新按量、1个月、1年收费标准参考
    123
  • 8
    游戏显卡驱动，NVIDIA App ，0xc000007b，amd显卡驱动下载，解决游戏慢，游戏卡等问题
    89
  • 9
    基于python大数据的天气可视化分析预测系统
    88
  • 10
    AIRS/Aqua L1B 可见光/近红外 (VIS/NIR) 地理定位和校准辐射 V005 (AIRVBRAD) 在 GES DISC
    73

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    蛋白质语言模型 ProGen：在实验室合成由 AI 预测的蛋白质