用Golang写一个搜索引擎（0x0A）--- 数据检索，败者树，K路求交

终于把序号写到了第十篇（其实已经是第13篇了），前面写了几个外篇，我看上篇机器学习的那篇看的人很多，后面会再找一两个点再写写，后面可能会算法部分和架构部分穿插着写了，想到哪里就写哪里了，今天我们继续我们的搜索引擎架构部分，主要来说说数据的检索。

之前我们说完了数据的增，删，改，还剩下一个查没有写，今天来写写查。

搜索引擎最核心的东西就是查了，在查上面，也有很多好玩的数据结构和算法，我们一个一个来说说。

之前说了搜索引擎的核心底层数据结构包括两个：倒排索引和正排索引，倒排索引主要用来检索，正排索引主要用来过滤，我们就以一个搜索请求来说说搜索引擎的检索。

比如我们有最近3个月新浪微博的数据在搜索引擎中，数据有发布者昵称，微博内容，微博发布时间，要搜索的关键词是长沙雅礼中学，而且只要看最近10天的数据，那么这么一个典型的搜索场景是怎么来进行的呢？我们先假设我们数据是这样的4条数据

"nickname" : "长沙天气预报" "content":"今天天气真好" "datetime":"2016-05-06"
"nickname" : "路人甲" "content":"长沙天气真好，我现在在雅礼中学" "datetime":"2016-01-21"
"nikename" : "雅礼中学官微" "content":"长沙天气真好" "datetime":"2016-05–05"

Query分析

首先关键词来了以后要进行的第一步是query分析，query分析相当复杂，也直接影响到搜索效果，有很多算法上的东西，这个需要单独说，呵呵。

当然，最简单的query分析就是切词了，我们这里不讲算法，所以query分析直接就是切词了，切词完了以后变成了长沙/雅礼/中学，后面的10天这个约束条件就变成了range(2016-05-01，2016-05-10)，好了，query分析就完了。

数据检索

1.获取倒排链

query分析完了以后，就开始进行倒排检索了，倒排检索就是按照切词的结果，一个term一个term的从倒排文件中拉取倒排链，简单来说是这样的

//从B+树中获取关键字倒排链的文件偏移offset
ok,offset := this.btree.Search(this.fieldName,keystr)
if !ok {
  return nil,false
}
//文件偏移的第一个位置保存的倒排链的长度
lens := this.idxMmap.ReadInt64(int64(offset))
//通过offset和倒排链的长度获取整个倒排链
res := this.idxMmap.ReadDocIdsArry(uint64(offset+8),uint64(lens))
return res,true

这样，通过三次调用就得到3个倒排链了，然后开始检索的第二步。

上面的数据中，我们要检索长沙/雅礼/中学，我们发现，三条数据都满足这个条件，不一样的是第一条和第二条是单个字段就满足，第三条是跨字段了，需要两个字段合起来才满足匹配条件，所以，我们的检索过程并不是简单的求倒排链的交集，而是一个求并求交的组合过程。

先单个的term在多个字段求并集，然后再多个term之间求交集，这样能满足找到所有符合条件的结果。

2.单term多字段间求并

多路求并也叫K路并归，比如长沙这个term，在检索nickname的时候，找到docid为[1]，检索content的时候，找到docid为[2,3]，两个docid链求并集，得到[1,2,3]，就是我们最后要求的结果。

这里只是一个两路的求并集，比较简单，如果是更多的字段检索，那么就会有超过两个的多路求并，一般我们使用胜者树或者败者树来进行K路求并的操作。

胜者树，败者树

所谓胜者树，是一种外部归并排序经常使用的数据结构，我们这里用他来做多路的求并集操作，因为我们的倒排链是以mmap的形式进行存储的，其实也是一种外部存储。

简单的说，胜者树就是以K路的数据作为叶子节点，建立一棵完全二叉树，然后叶子节点两两比较，胜利者进入上一层节点中，指导最后得到一个最后的胜利者输出，输出以后将对应的数据更新，光这么说太抽象了，我们看个图就明白了，比如我们目前有4路求并集，4路的数据分别是[0,3]，[1,2]，[0,3]，[3,4]，那么整个胜者树的过程就是下面的这个图，从左到右表示胜者树的求并过程。

上面那个图中

首先，有4个数组，那么建立一个有四个叶子节点的平衡完全二叉树，每个叶子节点存储一个倒排链，把每个倒排链的第一个元素拿出来准备进行比较
两两比较，较小的那个进入上一层节点，然后上一层节点继续两两比较，较小的那个进入上一层节点，直到最后到达根节点，图中的红色部分
把最后战斗到根节点的元素输出到最终结果中（如果最终结果中最后一个元素和这个根节点元素一样，丢弃这个元素）
将最后获胜的元素的倒排链指针后移一位，将该链的后一个元素拿出来进行比较

这样的话，在时间复杂度为O(nlogk)的情况下，我们就把并集求好了。

求并集的方法也有很多，我们这里只举出了比较常见的，胜者树这种结构比较好理解，但在实现的时候，一般采用胜者树的变体败者树，败者数的原理和胜者树一样，有区别的地方是，两两比较的时候败者树保存的是败者的信息，而胜者接着往上层进行战斗，直到根节点位置，最后输出的还是胜者。

败者树的过程我也画了个图，在下面

败者树的优势在于新进来的元素，只需要跟他的父节点进行比较就行了（只需要一次指针操作就可以找到父节点），胜者树的话还需要找临近节点比较（需要两次指针操作才能找到临近节点），然后更新父节点信息，所以败者树效率更优一点。

3.多term之间求交

上一步中拿到了各个term的倒排链以后，为了保证每个document中都含有所有词，就要对他们求交集了，因为倒排链是按照docid从小到大排列的，所以求交集实际上是对多个有序数组求交集。

如果是两个倒排链的话比较容易，拿两个指针分别指向两个倒排链的首部，然后比较大小，哪个小，那么把这个指针后移一位，如果两个相等，那么把这个docid取出来，直到某一条倒排链遍历完，时间复杂度O(n+m)，最好的情况是O(min(n,m))，代码也很简单，核心的就这么几行：

ia,ib:=0,0
for ia < lena && ib < lenb {
    if a[ia].Docid == b[ib].Docid {
        c[lenc] = a[ia]
        lenc++
        ia++
        ib++
        continue
    }
    if a[ia].Docid < b[ib].Docid {
        ia++
    } else {
        ib++
    }
}
return c

这是两个倒排链求交集，如果是多个倒排链求交集的话，可以两两求交，最后就完成了。

这样效率比较低，这里我们再介绍一种方法

因为求交集最后的结果长度肯定不会超过最短的倒排链的长度，所以我们首先找到长度最短的倒排链，作为标称数组。
从标称数组中依次取出每个元素，查看元素是不是在其他的每一个倒排链中
如果这个元素在其他所有倒排链中都存在，那么就把这个元素放入最终结果集中。

上面的第二步又可以从以下几个方面优化一下

如果发现某个元素不在某个倒排链中，那么他肯定不在最终结果中，直接跳出，不用继续比较了。
如果某个倒排链被查找完了，那么也可以跳出了。
查找元素是否在某个倒排链中，可以使用下面几个方式来优化
- 一是可以使用二分查找来找，这样复杂度可以降低一个数量级。
- 因为我们的docid是连续的，所以可以设定一个哨兵指针，然后从哨兵指针往后遍历，遍历到倒排链中的元素大于当前元素就停止，然后把哨兵移动到这个元素位置就行，这样的话只是给每个倒排链表加了个哨兵，复杂度上却降低了一个数量级了。

如果用二分查找的话，假如每个倒排链长度为N，一共有K个倒排链，那么整体最坏情况下复杂度是O(N*K*logN)，如果用哨兵的方法的话，一般比这个还要快一点。

下面这个图是优化后的多路求交，绿色的是标称数组中的元素，红色的是哨兵，黄色的是命中的元素。

4.正排过滤

到这一步，通过倒排文件能找到的元素就都找到了，像上面那个例子，我们找到了2和3两条记录，然后就要用第二个条件最近10天的数据来进行过滤操作了。

过滤操作比较简单，需要遍历一边结果集，然后用正排文件的值判断是否满足条件，这么遍历一下，就只剩下记录3了，这也是我们最后得到的结果。

在这里再说一下，之前我们说数据的增删改的时候说了，删除数据或者修改数据的时候实际上只是在bitmap上做了一个标记，表示这个数据删除了，所以最后检索的时候需要把已经删除的数据去掉，这一步也是在这里做，在遍历整个结果集做正排过滤的时候可以一起判断这个文档是否被删除了，只有满足过滤条件并且没有被删除的文档才能留下来。

由于正排文件的保存是按照docid来做数组下表保存的，所以查找的复杂度是O(1)，时间基本上就是遍历一边结果集加上条件判断的时间。

统计汇总

上面这些都做完了以后，就得到了最终的完整结果集，这时候在对结果集进行统计汇总之类的操作就简单了，这个可以根据业务的要求，做任何形式的统计汇总需求了，文本相关性的打分一般在求交集和求并集的时候就做完了，之前说的精细化的排序也在这一步来进行。

结束

好了，上面就是一次完整的检索过程中所涉及到的各种东西，关于query分析部分需要单独说，这一篇就不展开了。希望大家看得开心。

欢迎关注我的公众号，文章会在这里首先发出来：）扫描或者搜索微信号XJJ267或者搜索中文西加加语言就行