倒排索引优化 - 跳表

在前面一篇介绍 倒排索引 的文章中我们知道, 两个关键字的合并操作的时候复杂度是 θ(N), 如果在合并操作时遇到最极端的情况, 所扫描和比较的次数是两个列表集合的所有元素个数之和, 即是线性增长的, 这在数据量特别大的时候是很低效的. 我们还是看一下两个集合的合并操作代码示例:

a = [1, 2, 3, 6, 9, 11, 45, 67]
b = [4, 6, 13, 45, 69, 98]

i = j = 0
result = []
while i < len(a) and j < len(b):
    if a[i] == b[j]:
        result.append(a[i])
        i = i + 1
        j = j + 1
    elif a[i] < b[j]:
        i = i + 1
    else:
        j = j + 1

print result

# 输出
[6, 45]

如果待合并的两个倒排表数据量很大, 但是交集很少时, 会是什么情况呢?

[1, 2, 3, 4, 5, ... 10001, 10005]
[1, 10001, 10008]

如果对这两个做合并操作, 最后的交集结果只有  [1, 10001] 2个元素, 但是却要做10001次移动和比较操作, 所以肯定有什么办法来优化这一点. 可能你已经想到了, 我们做了这么多无用比较, 是因为我们每次指针向前移动的步子太小了点, 如果我们在每次比较后向前多移动一点, 可以忽略很比无用的操作. 这就是跳表的思想.

我们看第一个倒排表, 如果它以5000为步长前进, 进我们只需要向前查找两个即可找到我们需要的元素: 10001 . 这里写一个跳表功能的合并算法代码:

a = range(10008)
b = [1, 10001, 10008]

i = j = 0
result = []
step = 100
count = 0
while i < len(a) and j < len(b):
    if a[i] == b[j]:
        result.append(a[i])
        i = i +1
        j = j + 1
        count = count + 1
    elif a[i] < b[j]:
        while (i + step < len(a)) and a[i+step] <= b[j]:
            i = i + step
            count = count + 1
        else:
            i = i + 1
            count = count + 1
    else:
        while (j + step < len(b)) and b[j+step] <= a[i]:
            j = j + 5000
            count = count + 1
        else:
            j = j + 1
            count = count + 1

print result
print count

a = range(10008)
b = [1, 10001, 10008]
count = 0

i = j = 0
result = []
while i < len(a) and j < len(b):
    if a[i] == b[j]:
        result.append(a[i])
        i = i + 1
        j = j + 1
        count = count + 1
    elif a[i] < b[j]:
        i = i + 1
        count = count + 1
    else:
        j = j + 1
        count = count + 1

print result
print count

上面代码中故意构造了一个很大的集合 [0 ... 10007], 然后用变量count作为计数器来分析两个算法分别执行的操作次数, 可以看到采用跳表算法时(我们模拟了step=100)的计算次数是207, 而用之前的方式计算次数是10008, 可见性能提升了很多倍.

这里有几点说明下:

1. 这里为了简单说明跳表的思路, 全部用了数组表示倒排表, 其实真实的数据结构应该是链表结构(linked list). 这才符合磁盘存储结构.

2. 跳表的原始结构算法比这个复杂, 而且根据场景的不同, 跳表有不同的实现. 这里因为不是利用跳表的快速查询功能, 所以没有多级指针索引概念, 详细跳表实现查考: skip list

时间: 09-22

倒排索引优化 - 跳表的相关文章

【搜索引擎(二)】索引、倒排索引、哈希表、跳表

索引 其实在计算机中我们早已接触过跟索引有关的东西,比如数据库里的索引(index),还有硬盘文件系统中其实也有类似的东西,简而言之,索引是一种为了方便找到自己需要的东西而设计出来的条目,你可以通过找索引找到自己想要内容的位置.索引过程是: 关键字->索引->文档.在图书馆内的书分门别类,就是一种按类别来分的索引.当然索引还有很多其他的实现. 仅仅有索引的概念是不够的.虽然分门别类是一种方法,但是我们在拥有一堆文档的时候必须要有从文档到索引的规范过程,并且索引的结构要满足能够让人(或者计算机)

我是怎么用跳表优化搜索引擎的?

前言 对于跳表,我想大家都不陌生吧,这里不多解释,感兴趣的小伙伴可以看我的这篇文章:http://www.cnblogs.com/haolujun/archive/2012/12/24/2830683.html. 这段时间在做我们拍搜的优化,今天我就讲讲我是如何用跳表优化检索系统的. 搜索引擎的夹角余弦计算 都知道,搜索引擎利用夹角余弦计算query与文档的相似度,感兴趣的小伙伴可以看我的这篇文章:http://www.cnblogs.com/haolujun/archive/2013/01/0

SkipList 跳表

为什么选择跳表 目前经常使用的平衡数据结构有:B树,红黑树,AVL树,Splay Tree, Treep等. 想象一下,给你一张草稿纸,一只笔,一个编辑器,你能立即实现一颗红黑树,或者AVL树 出来吗? 很难吧,这需要时间,要考虑很多细节,要参考一堆算法与数据结构之类的树, 还要参考网上的代码,相当麻烦. 用跳表吧,跳表是一种随机化的数据结构,目前开源软件 Redis 和 LevelDB 都有用到它, 它的效率和红黑树以及 AVL 树不相上下,但跳表的原理相当简单,只要你能熟练操作链表, 就能轻

C语言跳表(skiplist)实现

一.简介 跳表(skiplist)是一个非常优秀的数据结构,实现简单,插入.删除.查找的复杂度均为O(logN).LevelDB的核心数据结构是用跳表实现的,redis的sorted set数据结构也是有跳表实现的.代码在这里:http://flyingsnail.blog.51cto.com/5341669/1020034 二.跳表图解 考虑一个有序表: 从该有序表中搜索元素 < 23, 43, 59 > ,需要比较的次数分别为 < 2, 4, 6 >,总共比较的次数 为 2 +

HBase内存结构之跳表数据结构浅析

最近学习HBase源码时发现HRegion在sotre管理上用到了跳表数据结构ConcurrentSkipListMap: ConcurrentSkipListMap有几个ConcurrentHashMap不能比拟优点: 1.ConcurrentSkipListMap的key是有序的. 2.ConcurrentSkipListMap支持更高的并发. ConcurrentSkipListMap的存取时间是log(N),和线程数几乎无关. 也就是说在数据量一定的情况下,并发的线程越多,Concurr

K:跳表

??跳表(SkipList)是一种随机化的数据结构,目前在redis和leveldb中都有用到它,它的效率和红黑树以及 AVL 树不相上下,但跳表的原理相当简单,只要你能熟练操作链表, 就能轻松实现一个 SkipList. 考虑一个有序表: 从该有序表中搜索元素 < 23, 43, 59 >,需要比较的次数分别为 < 2, 4, 6 >,总共比较的次数为 2 + 4 + 6 = 12 次. 有没有优化的算法吗?链表是有序的,但不能使用二分查找.类似二叉搜索树,我们把一些节点提取出来

SkipList跳表基本原理

为什么选择跳表 目前经常使用的平衡数据结构有:B树,红黑树,AVL树,Splay Tree, Treep等. 想象一下,给你一张草稿纸,一只笔,一个编辑器,你能立即实现一颗红黑树,或者AVL树 出来吗? 很难吧,这需要时间,要考虑很多细节,要参考一堆算法与数据结构之类的树, 还要参考网上的代码,相当麻烦. 用跳表吧,跳表是一种随机化的数据结构,目前开源软件 Redis 和 LevelDB 都有用到它, 它的效率和红黑树以及 AVL 树不相上下,但跳表的原理相当简单,只要你能熟练操作链表, 就能轻

skiplist(跳表)的原理及JAVA实现

前记 最近在看Redis,之间就尝试用sortedSet用在实现排行榜的项目,那么sortedSet底层是什么结构呢? "Redis sorted set的内部使用HashMap和跳跃表(SkipList)来保证数据的存储和有序,HashMap里放的是成员到score的映射,而跳跃表里存放的是所有的成员,排序依据是HashMap里存的score,使用跳跃表的结构可以获得比较高的查找效率,并且在实现上比较简单.”   那么什么是SkipList跳表呢?下面我们从理解它的思想到实现及应用去做一个大致

程序员,你应该知道的数据结构之跳表

跳表的原理 跳表也叫跳跃表,是一种动态的数据结构.如果我们需要在有序链表中进行查找某个值,需要遍历整个链表,二分查找对链表不支持,二分查找的底层要求为数组,遍历整个链表的时间复杂度为O(n).我们可以把链表改造成B树.红黑树.AVL树等数据结构来提升查询效率,但是B树.红黑树.AVL树这些数据结构实现起来非常复杂,里面的细节也比较多.跳表就是为了提升有序链表的查询速度产生的一种动态数据结构,跳表相对B树.红黑树.AVL树这些数据结构实现起来比较简单,但时间复杂度与B树.红黑树.AVL树这些数据结