1.由来《100亿数据1万属性数据架构设计》文章发表后，很多朋友对58自研的搜索引擎E-search更感兴趣，于是写了一篇系统的聊搜索引擎，从宏观到细节，希望把逻辑关系讲清楚，内容很多，分为两个阶段。主要内容如下。本文（上篇）将重点介绍前三章：（1）全网搜索引擎的架构及流程（2）站内搜索引擎的架构及流程（3）搜索原理、流程和核心数据结构（4）Traffic数据量从小到大，搜索方案和架构变化（5）数据量，并发，策略扩展和架构方案（6）实时搜索引擎核心技术可能99%的同学都不知道实现搜索引擎，不过这篇文章一定对你有所帮助。2.全网搜索引擎的结构和流程。全网搜索的宏观结构是什么样的？全网搜索的宏观过程是怎样的？整个网络搜索引擎的宏观结构如上图所示。核心子系统主要分为三个部分（粉色部分）：（1）蜘蛛爬虫系统（2）search&index索引构建和查询索引系统，本系统主要分为两部分：一部分用于生成索引数据build_index，另一部分用于查询索引数据search_index(3)排名评分排序系统核心数据主要分为两部分（紫色部分）：网页数据库索引索引数据全网搜索引擎的业务特性决定了这是一个“写”和“取”完全分离的系统：[写]系统组成：输入由蜘蛛和搜索两个系统完成&索引：站长生成的互联网网页输出：正向和反向索引数据流：如架构图中的1、2、3、4（1）蜘蛛抓取互联网网页（2）蜘蛛将互联网网页存储在网页库中（这个对存储要求高，需要存储ore几乎整个“万维网”图像）（3）build_index从网页库中读取数据并完成分词（4）build_index生成倒排Ranking索引【检索】系统组成：search&index和rank两个系统完成输入：用户的搜索词输出：排序首页搜索结果过程：如a,b,c,d（架构图中a）search_index获取用户的搜索词，完成分词（b）search_index查询倒排索引，得到“字符”matching”网页，这是初筛的结果(c)rank对初筛的结果进行评分和排序(d)rank对结果进行排序最终返回的是***页的结果3.In-站点搜索引擎的结构和流程只有少数公司进行全网搜索。大多数公司想要实现的实际上是站内搜索。站内搜索引擎的宏观架构与整个网络搜索引擎的宏观架构有何异同？以搜索58同城100亿帖为例，站内搜索系统架构是什么样的？现场搜索流程是什么？与宏架构相比，区别仅在于写的地方：（1）全网搜索需要蜘蛛被动抓取数据（2）站内搜索是内部系统产生的数据，例如，“发布系统”会主动推送生成的帖子build_data系统好像是“小”的rdquo;，架构实现难度大不相同：在全网搜索中“实时”找到“全量”网页非常困难，而在在网站上的搜索。对于spider、search&index和rank这三个系统：（1）spider和search&index是相对工程化的系统（2）rank是与业务和策略、算法密切相关的系统。搜索体验的主要区别就在于此，业务和策略的优化需要时间积累。这里的灵感是：a)Google的体验比百度好，因为前者的排名牛逼b)国内的互联网公司（比如360）很难在短时间内打造出超越百度体验的搜索引擎的时间，真的需要时间去积累。、搜索原理及核心数据结构什么是正向索引？什么是倒排索引？搜索过程是怎样的？将使用什么算法和数据结构？前面的内容过于宏观，大部分没有做过搜索引擎的同学，数据结构和算法部分从正向索引和倒排索引开始一点点。问题：什么是远期指数？答：通过key查询实体的过程就是一个正向索引。user表：t_user(uid,name,passwd,age,sex)，通过uid查询整行的过程就是正向索引查询。网页库：t_web_page(url,page_content)，通过url查询整个网页的过程，也是一个正向索引查询。网页内容切分后，page_content会对应一个分词列表。简单来说，正向索引可以理解为一道Map题：什么是倒排索引？答：逐项查询key的过程就是倒排索引。对于网页搜索，倒排索引可以理解为一个Map。例如假设有3个网页：url1->“我爱北京”url2->“我爱家”url3->“家很美”这是一个正向索引Map分词后：url1->{I,love,Beijing}url2->{I,love,home}url3->{Arrival,beautiful}这是分词后的正向索引Map分词后的倒排索引：I->{url1,url2}love->{url1,url2}北京->{url1}首页->{url2,url3}美女->{url3}通过搜索词项快速找到包含查询词的网页映射正向索引索引和倒排索引都是数据结构由spider和build_index系统预先建立。之所以使用这两种数据结构，是为了能够快速实现“用户网页检索”的需求（业务需求决定架构的实现）。问：搜索过程是怎样的？假设搜索词是“我爱”，用户会得到什么网页？(1)分词，将“我爱”分割成{I，love}，时间复杂度为O(1)(2)对于每一个分词项，从中查询包含该项的网页列表倒排索引，时间复杂度也是O(1)：I->{url1,url2}Love->{url1,url2}(3)求列表的交集，即匹配所有query的结果网页字。对于这个例子，{url1,url2}是最终的查询结果。好像到这里就结束了。事实上，并非如此。分词和倒排查询的时间复杂度都是O(1)，而整个查找的时间复杂度依赖于“求列表的交集”，问题转化为求两个集合的交集。字符类型的url不利于存储和计算。一般来说，每个url将由一个数字url_id标识。为了描述方便，将列表替换为列表。问题：如何找到list1和list2的交集？方案一：for*for，native方法，时间复杂度O(n*n)有很多网页每个搜索词都是***，O(n*n)的复杂度显然无法接受。倒排索引可以在创建之初进行排序和预处理。将问题转化为两个有序列表来寻找交集就方便多了。解法二：求有序列表的交集，zipper方法有序集1{1,3,5,7,8,9}有序集2{2,3,4,5,6,7}两个指针指向第一个元素，比较元素的大小：(1)如果相同，则放入结果集中，并随意移动一个指针(2)否则，移动一个值较小的指针，直到队列尾部。这种方法的好处是：(1)集合中的元素最多比较一次，时间复杂度为O(n)(2)。可以同时进行多个有序集合，适用于多个分词项。求url_id的交集这种方法就像拉链上的两个齿轮，一个一个比较就像一个拉链，所以称为拉链法。方案三：bucket并行优化当数据量很大时，url_idbucket水平切分+并行操作是一种常见的优化方式。如果list1和list2可以分成若干个bucketIntervals，每个interval使用多线程并行相交，将每个线程的结果集并集，作为最终的结果集，可以大大减少执行时间。示例：有序集1{1,3,5,7,8,9,10,30,50,70,80,90}有序集2{2,3,4,5,6,7,20,30,40,50,60,70}求交集，先进行分桶：桶1的范围为[1,9]桶2的范围为[10,100]桶3的范围为[101,max_int]所以：集合1被分成集合a{1,3,5,7,8,9}集合b{10,30,50,70,80,90}集合c{}集合2被分成集合d{2,3,4,5,6,7}collectione{20,30,40,50,60,70}collectione{}每个桶的数据量大大减少，每个桶没有重复可以使用多线程并行计算元素：存储桶1中的集合a和集合d的交集是x{3,5,7}存储桶2中的集合b和集合e的交集是y{30,50,70}bucket集合c和集合d在3中的交集是z{}最后集合1和集合2的交集是x,y,z的并集，即集合{3,5,7,30,50,70}方案四：位图重新优化数据。经过水平分桶和拆分后，每个桶中的数据必须在一定范围内。如果集合满足这个特性，可以用位图来表示集合：如上图所示，假设set1{1,3,5,7,8,9的所有元素}和set2{2,3,4,5,6,7}都在bucket值[1,16]的范围内，可以用16位来描述两个集合，原集合中的元素x，这个16bitmap中的第x位为1，此时的两个位图相交，只需要对两个位图进行“与”运算，结果集位图第3、5、7位为1，表示原集合的交集为{3,5,7}水平分桶。位图经过优化后，找交点的效率可以大大提高，但是时间复杂度还是O(n)位图需要大量的连续空间，占用大量内存。方案5：Skiplistskiplist是最常用的数据结构，它可以将有序集合交集的复杂度从O(n)降低到O(log(n))Set1{1,2,3,4,20,21,22,23,50,60,70}Set2{50,70}需要交集，如果用zipper方法，会发现1,2,3,4,20,21,22,23一定是遍历一次，每个元素都要进行比较，时间复杂度为O(n)，你能不能每次都比较“跳过一些元素”？跳转表出现：set1{1,2,3,4,20,21,22,23,50,60,70}建立跳转表中，只有三个元素{1,20,50}第一层，第二层和普通链表一样。set2{50,70}由于元素数量少，只有一级普通链表。"在找交集的过程中，set1的指针可以从1跳到20再跳到50，中间可以跳过很多元素，没有一对一的比较。跳表的时间复杂度findtheintersectionisapproximatelyO(log(n)),这是搜索引擎中常用的算法。Spider,search&index,rank由三个子系统组成(2)站内搜索引擎与站内搜索引擎的区别整个网络就是少了一个spider子系统(3)spider和search&index系统是两个工程系统，但是rank系统的优化需要很长时间时间优化和积累(4)Forwardindex(前向索引)是通过网页url_id快速找到分词后网页内容列表的过程（5）倒排索引（invertedindex）就是通过分词项快速找到包含分词的网页的过程列表的（6）用户检索的过程是先分词，然后找到每一项对应的列表，最后进行集合交集的过程（7）有序集合交集的方法有doublefor循环的方法，时间复杂度O(n*n)拉链方式，时间复杂度O(n)水平分桶，多线程并行位图，大大提高运算的并行性，时间复杂度O(n)跳表，时间复杂度O(log(n))6.下一章预测a)流量数据量由小变大，搜索方案和结构发生变化->这个应该很有用。许多处于不同发展阶段的互联网公司都在研究搜索系统。58同城经历了流量从0到10亿，数据量从0到100亿，搜索架构也在不断演进b)数据量、并发、策略扩展和架构方案c)实时搜索引擎核心技术->站长发布新网页，15分钟后Google如何检索【本文为专栏作者“58深鉴”原创稿件，转载请联系原作者】点此阅读这个作者的更多好文章
