我旁边的同时一直在捣鼓redis的分页功能，详细的分析了list和sorted set的两个结构. 我自己也对sorted set的数据结构很是感兴趣… 我这边的有个微信抓取的任务就是用python rq做的，里面的选用的redis数据类型就是sorted set… 这里不是重点，有时间专门写一篇关于redis实现时序任务队列的方式。
开始先是介绍skip list :
Skip List是一种随机化的数据结构，基于并联的链表，其效率可比拟于二叉查找树（对于大多数操作需要O(log n)平均时间）。基本上，跳跃列表是对有序的链表增加上附加的前进链接，增加是以随机化的方式进行的，所以在列表中的查找可以快速的跳过部分列表(因此得名)。所有操作都以对数随机化的时间进行。Skip List可以很好解决有序链表查找特定值的困难。
Skip List定义
一个skip list 跳表，应该具有以下特征：
一个跳表应该有几个层（level）组成；
跳表的第一层包含所有的元素；
每一层都是一个有序的链表；
如果元素x出现在第i层，则所有比i小的层都包含x；
第i层的元素通过一个down指针指向下一层拥有相同值的元素；
在每一层中，-1和1两个元素都出现(分别表示INT_MIN和INT_MAX)；
Top指针指向最高层的第一个元素。
大家看下面的图片，一共构造了三层，根据上面的一些个特性，估计你也能理解一二了。 举个例子，你如果想查找14，那么先从第三层开始搞起，因为是有序的，所以14可以确定是在第二层的7和21之间，然后呢，再到第三层就能找到了。 他的一些算法是含有一些随机性的。
那么我们再来查找117和118
例子：查找元素 117
(1) 比较 21， 比 21 大，往后面找
(2) 比较 37, 比 37大，比链表最大值小，从 37 的下面一层开始找
(3) 比较 71, 比 71 大，比链表最大值小，从 71 的下面一层开始找
(4) 比较 85， 比 85 大，从后面找
(5) 比较 117， 等于 117， 找到了节点。
下面是我在wiki找到的一个流程动画，方便大家理解
跳表的插入方式
有人也用python实现了skip list的功能，有兴趣的朋友可以看看。 代码还算干练，对于理解skip list 也是很有帮助的。
from math import log
from random import random, seed
class Node( object ):
def __init__( self,
value = None,
next = [] ):
self.value = value
self.next = next
class End( object ):
def __cmp__( self, other ):
return 1 # always greater than any other object
END = Node( End(), [] )
class SkipList:
def __init__( self, expected_size = 100, p = 0.5 ):
self.size = 0
self.maxlevels = int( log(expected_size, 2) + 1 )
self.head = Node( 'HEAD', [END] * self.maxlevels )
self.p = p
def random_level( self ):
lev = 1
while ((random() < self.p) and (lev < self.maxlevels)):
lev = lev + 1
return lev
def insert( self, value ):
saveprev = [None] * self.maxlevels
node = self.head
for lev in reversed( range(self.maxlevels) ):
while (node.next[lev].value <= value):
node = node.next[lev]
saveprev[lev] = node
new = Node( value = value,
next = [ None ] * self.random_level() )
for lev in range( len(new.next) ):
# saveprev[lev] points to new[lev]
tmp = saveprev[lev].next[lev]
saveprev[lev].next[lev] = new
new.next[lev] = tmp
self.size = self.size + 1
def delete( self, value ):
node = self.head
saveprev = [None] * self.maxlevels
for lev in reversed( range(self.maxlevels) ):
while (node.next[lev].value < value):
node = node.next[lev]
saveprev[lev] = node
node = saveprev[0].next[0]
if node.value == value:
# saveprev[0] points to the node to be deleted
for lev in range( self.maxlevels ):
if saveprev[lev].next[lev] != node:
break
saveprev[lev].next[lev] = node.next[lev]
node.next[lev] = None
self.size = self.size - 1
def printme( self ):
print "Size = ", self.size
print "Maxlevels = ", self.maxlevels
node = self.head
node = node.next[0]
while (node != END):
print "->", node.value,
node = node.next[0]
print
if __name__ == "__main__":
# Simple test
# TODO: This should be put in a test suite.
from random import randint
seed( 8 )
l = [ randint(0, 90000) for x in xrange(800000) ]
seed( 31 )
print "Running myskiplist test:"
mylist = SkipList( expected_size = 800000, p = 0.25 )
for x in l:
mylist.insert( x )
print "Initial list:"
print "Size:", mylist.size
# mylist.printme()
# delete some keys
d = [ randint(0, 90000) for x in xrange(2000000) ]
# d = [510, 507]
for x in d:
# print "Deleting key:", x
mylist.delete(x)
print "After deletes:"
print "Size:", mylist.size
# mylist.printme()
print "Done."
这个不错！
学习了