搜索引擎原理：搜索引擎原理构架介绍？( 三 ) _生活百科

水平分桶， bitmap优化之后，能极大提高求交集的效率，但时间复杂度仍旧是O(n)
bitmap需要大量连续空间，占用内存较大
方案五：跳表skiplist
有序链表集合求交集，跳表是最常用的数据结构，它可以将有序集合求交集的复杂度由O(n)降至O(log(n))

文章插图
集合1{1,2,3,4,20,21,22,23,50,60,70}
集合2{50,70}
要求交集，如果用拉链法，会发现1,2,3,4,20,21,22,23都要被无效遍历一次，每个元素都要被比对，时间复杂度为O(n) ，能不能每次比对“跳过一些元素”呢？
跳表就出现了：

文章插图
集合1{1,2,3,4,20,21,22,23,50,60,70}建立跳表时，一级只有{1,20,50}三个元素，二级与普通链表相同
集合2{50,70}由于元素较少，只建立了一级普通链表
如此这般，在实施“拉链”求交集的过程中， set1的指针能够由1跳到20再跳到50 ，中间能够跳过很多元素，无需进行一一比对，跳表求交集的时间复杂度近似O(log(n)) ，这是搜索引擎中常见的算法。
五、总结
文字很多，有宏观，有细节，对于大部分不是专门研究搜索引擎的同学，记住以下几点即可：
（1）全网搜索引擎系统由spider ， search&index ， rank三个子系统构成
（2）站内搜索引擎与全网搜索引擎的差异在于，少了一个spider子系统
（3）spider和search&index系统是两个工程系统， rank系统的优化却需要长时间的调优和积累
（4）正排索引（forward index）是由网页url_id快速找到分词后网页内容list的过程
（5）倒排索引（inverted index）是由分词item快速寻找包含这个分词的网页list的过程
（6）用户检索的过程，是先分词，再找到每个item对应的list ，最后进行集合求交集的过程
（7）有序集合求交集的方法有
a）二重for循环法，时间复杂度O(n*n)
b）拉链法，时间复杂度O(n)
c）水平分桶，多线程并行
d）bitmap ，大大提高运算并行度，时间复杂度O(n)
e）跳表，时间复杂度为O(log(n))
【搜索引擎原理：搜索引擎原理构架介绍？】 好了，这篇文章的内容金华号就和大家分享到这里！