devbox
盐析白兔
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

深入理解Redis数据结构：跳跃表（Skiplist）_跳跃表skiplist

作者：盐析白兔 | 2024-07-24 22:21:56

赞

踩

跳跃表skiplist

目录

  1. 引言
  2. 跳跃表简介
  3. 跳跃表的结构
  4. 跳跃表的操作
  5. 跳跃表的应用场景
  6. 跳跃表的优缺点
  7. 跳跃表与其他数据结构的对比
  8. 跳跃表的实现
  9. 总结

引言

在现代数据库和缓存系统中，高效的数据结构对于保证性能至关重要。Redis作为一种高性能的key-value存储系统，采用了多种数据结构来满足不同的需求。跳跃表（Skiplist）就是其中一种重要的数据结构，它在Redis中用于实现有序集合（Sorted Set）。本文将详细介绍跳跃表的结构、操作、应用场景、优缺点，并通过代码实例演示其实现方式。

跳跃表简介

跳跃表是一种基于多级链表的数据结构，用于高效地实现有序数据的查找、插入和删除操作。它在1989年由William Pugh提出，旨在提供一种简单但性能接近于平衡树的替代方案。跳跃表的核心思想是通过增加多级索引，使得查找操作可以跳过大部分元素，从而提高效率。

跳跃表的结构

节点结构

跳跃表的基本组成单位是节点，每个节点包含以下部分：

  • 值：节点存储的数据值。
  • 前向指针数组：每个节点包含多个前向指针，这些指针指向该节点在不同层级上的下一个节点。
  • 后向指针：指向前一个节点（可选）。
  • 跨度数组：每个前向指针对应一个跨度，表示当前节点到下一个节点的距离。

层级结构

跳跃表由多层链表组成，每层链表的节点都是按照一定概率从下一层链表的节点中抽取出来的。最底层的链表包含所有节点，每一层的链表是其下一层链表的子集。这样的结构使得跳跃表在查找操作时能够跳过大部分节点。

跳跃表的操作

插入操作

插入操作的步骤如下：

  1. 确定新节点的层级：通过随机函数确定新节点的层级。
  2. 找到插入位置：从最高层开始，逐层向下找到新节点在每一层的插入位置。
  3. 插入节点：在确定的位置插入新节点，并更新相关指针和跨度。

删除操作

删除操作的步骤如下：

  1. 找到待删除节点：从最高层开始，逐层向下找到待删除节点在每一层的位置。
  2. 更新指针：逐层更新相关指针和跨度，移除待删除节点。
  3. 释放节点：释放节点占用的内存。

查找操作

查找操作的步骤如下：

  1. 从最高层开始：从跳跃表的最高层开始查找目标节点。
  2. 逐层向下：在当前层查找到不大于目标节点的最大节点，然后向下一层继续查找，直到找到目标节点或确认目标节点不存在。

跳跃表的应用场景

Redis中的应用

在Redis中，跳跃表主要用于实现有序集合（Sorted Set）。Redis的有序集合支持范围查询和有序迭代，这些操作在跳跃表上可以高效实现。此外，Redis还使用跳跃表来实现某些内部数据结构，如持久化文件的索引。

其他应用场景

跳跃表除了在Redis中使用外，还可以用于以下场景：

  • 内存数据库：跳跃表适用于内存数据库中的有序数据存储和检索。
  • 缓存系统：在缓存系统中，跳跃表可以用来管理有序缓存条目，实现高效的范围查询和淘汰策略。
  • 文本处理：跳跃表可以用于实现文本处理中的有序集合操作，如词频统计和关键词索引。

跳跃表的优缺点

优点

  1. 简单易实现：跳跃表的实现相对简单，不需要复杂的旋转操作。
  2. 动态平衡：跳跃表通过随机化保持动态平衡，无需手动调整。
  3. 高效的范围查询：跳跃表支持高效的范围查询和迭代操作。

缺点

  1. 随机性：跳跃表的性能依赖于随机数生成器的质量，可能出现性能波动。
  2. 空间开销大：跳跃表需要额外的层级和指针，空间开销较大。
  3. 最坏情况复杂度：在极端情况下，跳跃表的时间复杂度可能退化为O(n)。

跳跃表与其他数据结构的对比

与链表对比

  • 性能：跳跃表在查找、插入和删除操作上的性能远优于单纯的链表。
  • 复杂度：链表实现简单，而跳跃表相对复杂，但提供更好的性能。

与平衡树对比

  • 实现复杂度：跳跃表的实现比平衡树简单，不需要复杂的旋转操作。
  • 性能：在大多数情况下，跳跃表的性能接近于平衡树，但在最坏情况下可能退化。
  • 空间开销：跳跃表的空间开销较大，而平衡树更为紧凑。

跳跃表的实现

C语言实现

以下是一个简单的C语言实现跳跃表的示例：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_LEVEL 6

typedef struct SkipListNode {
    int value;
    struct SkipListNode *forward[MAX_LEVEL + 1];
} SkipListNode;

typedef struct SkipList {
    int level;
    SkipListNode *header;
} SkipList;

SkipListNode* createNode(int level, int value) {
    SkipListNode *node = (SkipListNode *)malloc(sizeof(SkipListNode));
    node->value = value;
    for (int i = 0; i <= level; i++) {
        node->forward[i] = NULL;
    }
    return node;
}

SkipList* createSkipList() {
    SkipList *list = (SkipList *)malloc(sizeof(SkipList));
    list->level = 0;
    list->header = createNode(MAX_LEVEL, INT_MAX);
    return list;
}

int randomLevel() {
    int level = 0;
    while (rand() % 2 && level < MAX_LEVEL) {
        level++;
    }
    return level;
}

void insert(SkipList *list, int value) {
    SkipListNode *update[MAX_LEVEL + 1];
    SkipListNode *x = list->header;

    for (int i = list->level; i >= 0; i--) {
        while (x->forward[i] && x->forward[i]->value < value) {
            x = x->forward[i];
        }
        update[i] = x;
    }

    int level = randomLevel();
    if (level > list->level) {
        for (int i = list->level + 1; i <= level; i++) {
            update[i] = list->header;
        }
        list->level = level;
    }

    x = createNode(level, value);
    for (int i = 0; i <= level; i++) {
        x->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = x;
    }
}

void delete(SkipList *list, int value) {
    SkipListNode *update[MAX_LEVEL + 1];
    SkipListNode *x = list->header;

    for (int i = list->level; i >= 0; i--) {
        while (x->forward[i] && x->forward[i]->value < value) {
            x = x->forward[i];
        }
        update[i] = x;
    }

    x =



 x->forward[0];
    if (x && x->value == value) {
        for (int i = 0; i <= list->level; i++) {
            if (update[i]->forward[i] != x) {
                break;
            }
            update[i]->forward[i] = x->forward[i];
        }
        free(x);

        while (list->level > 0 && list->header->forward[list->level] == NULL) {
            list->level--;
        }
    }
}

SkipListNode* search(SkipList *list, int value) {
    SkipListNode *x = list->header;
    for (int i = list->level; i >= 0; i--) {
        while (x->forward[i] && x->forward[i]->value < value) {
            x = x->forward[i];
        }
```c
    }
    x = x->forward[0];
    if (x && x->value == value) {
        return x;
    } else {
        return NULL;
    }
}

void printSkipList(SkipList *list) {
    for (int i = list->level; i >= 0; i--) {
        SkipListNode *node = list->header->forward[i];
        printf("Level %d: ", i);
        while (node != NULL) {
            printf("%d ", node->value);
            node = node->forward[i];
        }
        printf("\n");
    }
}

int main() {
    SkipList *list = createSkipList();
    insert(list, 3);
    insert(list, 6);
    insert(list, 7);
    insert(list, 9);
    insert(list, 12);
    insert(list, 19);
    insert(list, 17);
    insert(list, 26);
    insert(list, 21);
    insert(list, 25);

    printf("SkipList:\n");
    printSkipList(list);

    printf("\nSearching for 19:\n");
    SkipListNode *node = search(list, 19);
    if (node != NULL) {
        printf("Found %d\n", node->value);
    } else {
        printf("Not found\n");
    }

    printf("\nDeleting 19:\n");
    delete(list, 19);
    printSkipList(list);

    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155

Python实现

以下是一个简单的Python实现跳跃表的示例：

import random

class SkipListNode:
    def __init__(self, value, level):
        self.value = value
        self.forward = [None] * (level + 1)

class SkipList:
    MAX_LEVEL = 6

    def __init__(self):
        self.level = 0
        self.header = SkipListNode(float('-inf'), self.MAX_LEVEL)

    def random_level(self):
        level = 0
        while random.random() < 0.5 and level < self.MAX_LEVEL:
            level += 1
        return level

    def insert(self, value):
        update = [None] * (self.MAX_LEVEL + 1)
        x = self.header

        for i in range(self.level, -1, -1):
            while x.forward[i] and x.forward[i].value < value:
                x = x.forward[i]
            update[i] = x

        level = self.random_level()
        if level > self.level:
            for i in range(self.level + 1, level + 1):
                update[i] = self.header
            self.level = level

        x = SkipListNode(value, level)
        for i in range(level + 1):
            x.forward[i] = update[i].forward[i]
            update[i].forward[i] = x

    def delete(self, value):
        update = [None] * (self.MAX_LEVEL + 1)
        x = self.header

        for i in range(self.level, -1, -1):
            while x.forward[i] and x.forward[i].value < value:
                x = x.forward[i]
            update[i] = x

        x = x.forward[0]
        if x and x.value == value:
            for i in range(self.level + 1):
                if update[i].forward[i] != x:
                    break
                update[i].forward[i] = x.forward[i]

            while self.level > 0 and self.header.forward[self.level] is None:
                self.level -= 1

    def search(self, value):
        x = self.header
        for i in range(self.level, -1, -1):
            while x.forward[i] and x.forward[i].value < value:
                x = x.forward[i]
        x = x.forward[0]
        if x and x.value == value:
            return x
        else:
            return None

    def print_list(self):
        for i in range(self.level, -1, -1):
            print(f"Level {i}: ", end="")
            node = self.header.forward[i]
            while node:
                print(node.value, end=" ")
                node = node.forward[i]
            print("")

if __name__ == "__main__":
    sl = SkipList()
    sl.insert(3)
    sl.insert(6)
    sl.insert(7)
    sl.insert(9)
    sl.insert(12)
    sl.insert(19)
    sl.insert(17)
    sl.insert(26)
    sl.insert(21)
    sl.insert(25)

    print("SkipList:")
    sl.print_list()

    print("\nSearching for 19:")
    node = sl.search(19)
    if node:
        print(f"Found {node.value}")
    else:
        print("Not found")

    print("\nDeleting 19:")
    sl.delete(19)
    sl.print_list()

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105

总结

跳跃表是一种高效且易于实现的数据结构，它通过多级链表的方式实现了接近于平衡树的性能。跳跃表的随机化特性使其无需复杂的旋转操作即可保持动态平衡，适用于需要频繁进行查找、插入和删除操作的场景。虽然跳跃表在最坏情况下的时间复杂度可能退化，但在实际应用中表现稳定，是一种非常实用的数据结构。通过本文的详细介绍和代码示例，相信读者对跳跃表的原理和实现有了深入的了解，可以在实际项目中灵活应用。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/876985
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号