“搜索”的原理，架构，实现，实践，面试不用再怕了（值得收藏）！！！(3)

有序链表集合求交集，跳表是最常用的数据结构，它可以将有序集合求交集的复杂度由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)有序集合求交集的方法有：

• 二重for循环法，时间复杂度O(n*n)
• 拉链法，时间复杂度O(n)
• 水平分桶，多线程并行
• bitmap，大大提高运算并行度，时间复杂度O(n)
• 跳表，时间复杂度为O(log(n))

画外音：面试应该够用了。

大部分工程师未必接触过“搜索内核”，但互联网业务，基本会涉及“检索”功能。还是以58同城的帖子业务场景为例，帖子的标题，帖子的内容有很强的用户检索需求，在业务、流量、并发量逐步递增的各个阶段，应该如何实现检索需求呢?

原始阶段-LIKE

创业阶段，常常用这种方法来快速实现。

数据在数据库中可能是这么存储的：

t_tiezi(tid, title, content) 

满足标题、内容的检索需求可以通过LIKE实现：

select tid from t_tiezi where content like ‘%天通苑%’ 

这种方式确实能够快速满足业务需求，存在的问题也显而易见：

• 效率低，每次需要全表扫描，计算量大，并发高时cpu容易100%;
• 不支持分词;

初级阶段-全文索引

如何快速提高效率，支持分词，并对原有系统架构影响尽可能小呢，第一时间想到的是建立全文索引：

alter table t_tiezi add fulltext(title,content) 

使用match和against实现索引字段上的查询需求。

全文索引能够快速实现业务上分词的需求，并且快速提升性能(分词后倒排，至少不要全表扫描了)，但也存在一些问题：

• 只适用于MyISAM;
• 由于全文索引利用的是数据库特性，搜索需求和普通CURD需求耦合在数据库中：检索需求并发大时，可能影响CURD的请求;CURD并发大时，检索会非常的慢;
• 数据量达到百万级别，性能还是会显著降低，查询返回时间很长，业务难以接受;
• 比较难水平扩展;

中级阶段-开源外置索引

为了解决全文索的局限性，当数据量增加到大几百万，千万级别时，就要考虑外置索引了。外置索引的核心思路是：索引数据与原始数据分离，前者满足搜索需求，后者满足CURD需求，通过一定的机制(双写，通知，定期重建)来保证数据的一致性。

原始数据可以继续使用Mysql来存储，外置索引如何实施?Solr，Lucene，ES都是常见的开源方案。其中，ES(ElasticSearch)是目前最为流行的。

Lucene虽好，潜在的不足是：

• Lucene只是一个库，需要自己做服务，自己实现高可用/可扩展/负载均衡等复杂特性;
• Lucene只支持Java，如果要支持其他语言，必须得自己做服务;
• Lucene不友好，这是很致命的，非常复杂，使用者往往需要深入了解搜索的知识来理解它的工作原理，为了屏蔽其复杂性，还是得自己做服务;

为了改善Lucene的各项不足，解决方案都是“封装一个接口友好的服务，屏蔽底层复杂性”，于是有了ES：

• ES是一个以Lucene为内核来实现搜索功能，提供REStful接口的服务;
• ES能够支持很大数据量的信息存储，支持很高并发的搜索请求;
• ES支持集群，向使用者屏蔽高可用/可扩展/负载均衡等复杂特性;

目前，快狗打车使用ES作为核心的搜索服务，实现业务上的各类搜索需求，其中：

• 数据量最大的“接口耗时数据收集”需求，数据量大概在10亿左右;
• 并发量最大的“经纬度，地理位置搜索”需求，线上平均并发量大概在2000左右，压测数据并发量在8000左右;

所以，ES完全能满足10亿数据量，5k吞吐量的常见搜索业务需求。

高级阶段-自研搜索引擎

当数据量进一步增加，达到10亿、100亿数据量;并发量也进一步增加，达到每秒10万吞吐量;业务个性也逐步增加的时候，就需要自研搜索引擎了，定制化实现搜索内核了。

到了定制化自研搜索引擎的阶段，超大数据量、超高并发量为设计重点，为了达到“无限容量、无限并发”的需求，架构设计需要重点考虑“扩展性”，力争做到：增加机器就能扩容(数据量+并发量)。

（编辑：ASP站长网）