Redis中的跳跃表(SkipList)详解

需积分: 10 200 浏览量更新于2024-09-16 收藏 66KB PDF 举报

"Redis 中的跳跃表（Skip List）是一种概率性平衡的数据结构，它提供了一种在平均情况下与平衡二叉树相似的查找、插入和删除操作的时间复杂度，但实现更为简单且效率更高。跳跃表由 William Pugh 提出，作为平衡二叉树的一种替代方案。" 在 Redis 中，跳跃表主要用于实现有序集合（Sorted Set）功能，它能够快速地进行范围查询和排序。跳跃表的核心思想是通过多层索引来加速查找过程，每一层索引都包含一部分元素，且上一层的索引元素是下一层的子集。最底层是完整的元素列表，而上层的元素则是按照一定的概率随机选择的。以下是关于跳跃表的关键知识点： 1. **概率平衡**：不同于平衡二叉树强制执行的严格平衡规则，跳跃表使用概率来保持平衡。每个元素有独立的概率被选入上一层，这使得在大多数情况下，查找、插入和删除操作可以在对数时间内完成。 2. **结构组成**：跳跃表由多个称为“层”的链表构成，每层链表都有自己的节点，最底层称为基础层，包含所有元素。较高层的节点只包含部分元素，这些元素通常是下一层中某个链表的头部元素。 3. **查找算法**：查找一个元素时，从最高层开始，如果当前节点的值小于目标值，则向下一层继续查找，直到找到目标元素或查找到底层结束。 4. **插入和删除**：插入新元素时，首先确定其在各层的位置，然后在相应的层创建新的节点。删除元素时，只需找到该元素并从所有层中移除。 5. **性能分析**：平均情况下，跳跃表的查找、插入和删除操作的时间复杂度都是 O(log n)，其中 n 是元素数量。这是因为虽然层数可能随着元素增加而增加，但通常不会超过元素数量的对数。 6. **空间效率**：相比于平衡二叉树，跳跃表可能会占用更多的空间，因为需要存储额外的指针。但是，由于不需要进行复杂的树结构调整，实际操作中的空间开销往往可以接受。 7. **适用场景**：跳跃表适合于需要高效范围查询和顺序遍历的场景，如 Redis 的有序集合。在内存限制不严的环境下，跳跃表提供了良好的性能与实现复杂度之间的平衡。 Redis 中的跳跃表是一种实用的数据结构，通过概率平衡策略实现了高效的操作性能，尤其适用于需要快速排序和范围查询的场景。

Skip Lists: A Probabilistic Alternative to

Balanced Trees

Skip lists are a data structure that can be used in place of balanced trees.

Skip lists use probabilistic balancing rather than strictly enforced balancing

and as a result the algorithms for insertion and deletion in skip lists are

much simpler and significantly faster than equivalent algorithms for

balanced trees.

William Pugh

Binary trees can be used for representing abstract data types

such as dictionaries and ordered lists. They work well when

the elements are inserted in a random order. Some sequences

of operations, such as inserting the elements in order, produce

degenerate data structures that give very poor performance. If

it were possible to randomly permute the list of items to be in-

serted, trees would work well with high probability for any in-

put sequence. In most cases queries must be answered on-line,

so randomly permuting the input is impractical. Balanced tree

algorithms re-arrange the tree as operations are performed to

maintain certain balance conditions and assure good perfor-

mance.

Skip lists are a probabilistic alternative to balanced trees.

Skip lists are balanced by consulting a random number gen-

erator. Although skip lists have bad worst-case performance,

no input sequence consistently produces the worst-case per-

formance (much like quicksort when the pivot element is cho-

sen randomly). It is very unlikely a skip list data structure will

be significantly unbalanced (e.g., for a dictionary of more

than 250 elements, the chance that a search will take more

than 3 times the expected time is less than one in a million).

Skip lists have balance properties similar to that of search

trees built by random insertions, yet do not require insertions

to be random.

Balancing a data structure probabilistically is easier than

explicitly maintaining the balance. For many applications,

skip lists are a more natural representation than trees, also

leading to simpler algorithms. The simplicity of skip list algo-

rithms makes them easier to implement and provides signifi-

cant constant factor speed improvements over balanced tree

and self-adjusting tree algorithms. Skip lists are also very

space efficient. They can easily be configured to require an

average of 1

pointers per element (or even less) and do not

require balance or priority information to be stored with each

node.

SKIP LISTS

We might need to examine every node of the list when search-

ing a linked list (Figure 1a). If the list is stored in sorted order

and every other node of the list also has a pointer to the node

two ahead it in the list (Figure 1b), we have to examine no

more than n/2 + 1 nodes (where n is the length of the list).

Also giving every fourth node a pointer four ahead (Figure

1c) requires that no more than n/4 + 2 nodes be examined.

If every (2

)

node has a pointer 2

nodes ahead (Figure 1d),

the number of nodes that must be examined can be reduced to

log

n while only doubling the number of pointers. This

data structure could be used for fast searching, but insertion

and deletion would be impractical.

A node that has k forward pointers is called a level k node.

If every (2

)

node has a pointer 2

nodes ahead, then levels

of nodes are distributed in a simple pattern: 50% are level 1,

25% are level 2, 12.5% are level 3 and so on. What would

happen if the levels of nodes were chosen randomly, but in the

same proportions (e.g., as in Figure 1e)? A node’s i

forward

pointer, instead of pointing 2

i–1

nodes ahead, points to the

next node of level i or higher. Insertions or deletions would

require only local modifications; the level of a node, chosen

randomly when the node is inserted, need never change. Some

arrangements of levels would give poor execution times, but

we will see that such arrangements are rare. Because these

data structures are linked lists with extra pointers that skip

over intermediate nodes, I named them skip lists.

SKIP LIST ALGORITHMS

This section gives algorithms to search for, insert and delete

elements in a dictionary or symbol table. The Search opera-

tion returns the contents of the value associated with the de-

sired key or failure if the key is not present. The Insert opera-

tion associates a specified key with a new value (inserting the

key if it had not already been present). The Delete operation

deletes the specified key. It is easy to support additional oper-

ations such as “find the minimum key” or “find the next key”.

Each element is represented by a node, the level of which

is chosen randomly when the node is inserted without regard

for the number of elements in the data structure. A level i

node has i forward pointers, indexed 1 through i. We do not

need to store the level of a node in the node. Levels are

capped at some appropriate constant MaxLevel. The level of a

list is the maximum level currently in the list (or 1 if the list is

empty). The header of a list has forward pointers at levels one

through MaxLevel. The forward pointers of the header at

levels higher than the current maximum level of the list point

to NIL.

下载后可阅读完整内容，剩余7页未读，立即下载

根叔的修行笔记

粉丝: 3213
资源: 15

Redis中的跳跃表(SkipList)详解

显示月份缩名（用跳跃表法使程序能根据不同条件转移到多个程序分支）

spiklist跳跃表

Java实现跳跃表(skiplist)的简单实例

c++实现跳跃表（Skip List）的方法示例

VB.net编写的SkipList 跳跃链表

跳跃表(SkipList)详解与Python实现

Java编程：深入理解跳跃表(SkipList)实现

Redis数据结构解析：高效查询的跳跃表(Skip List)

SkipList_Java.rar_SkipList in Java_skiplist_skiplist java

Go-skiplist-Skiplist在Go中的实现

最新资源