# Skip List

**跳表**（Skip List）可以支持快速的插入、删除、查找，Redis 中的有序集合（Sorted Set）实现用到了跳表。

**描述**：单链表查找时间复杂度为 O(n)，把单链表每两个结点提取一个到上一级，作为一级索引，抽出来的叫做索引层。索引层的结点有 down 指针，指向下一级的结点；有 next 指针，指向当前索引层的下一结点，有数据，值为排序的值。在一级索引上，每两个结点抽一个到上一级，作为二级索引。依此类推，增加多级索引。

![](/files/-Lz7Cxb6_nWPKj0JStFi)

**查找时间复杂度**：假设有 n 个数据，一级索引 `n / 2` 个结点，k 级索引 `n / (2 ^ k)`个结点。假设 h 级，最高级索引有 2 个结点，`h = log2(n) - 1`。加上原始层，跳表高度为 log2(n)。**每一级最多遍历 3 个结点**，时间复杂度为`O(3 * log2(n)) = O(logn)`。

**空间复杂度**：`n + n / 2 + n / 4 + n / 8 +... = n - 2`，为 O(n)。实际上不用太在意空间，因为原始链表结点一般对象比较大，而索引层的结点只需存储关键值和指针，不需要存储整个对象。

**插入时间复杂度**：单链表单纯的插入时间复杂度 O(1)，但是找到插入位置需要 O(n)，总 O(n)。跳表找到位置 O(logn)，单纯插入 O(1)，**总 O(logn)**。

**删除操作**：除了删除原始链表中的结点，若在索引中，还需删除索引中的结点。

**动态更新**：当不停插入时，可能出现两个索引节点之间数据非常多的情况，会降低查询效率。跳表通过随机函数保持平衡，比如当插入一个结点时，随机函数生成 K，则将这个结点添加到第一级到第 K 级索引中。随机函数的选择很有讲究，从概率上来讲，能够保证跳表的索引大小和数据大小平衡性，不至于性能过度退化。

**Redis 有序集合为什么选择跳表而不是红黑树：**

1. redis有序集合 API 有插入、删除、查找、按照区间查找、迭代输出有序序列，除了按照区间查找，其它操作红黑树也可完成，时间复杂度也一样，但是**按照区间查找，跳表效率更高**。
2. 跳表代码**实现较简单**。

{% hint style="info" %}
跳表不能完全替代红黑树，因为红黑树出现早，很多编程语言的 Map 通过红黑树实现的，可直接用。而跳表需要自己实现。
{% endhint %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://yunzhao.gitbook.io/notes/computer-science/algorithm/skip-list.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.