Chinaunix首页 | 论坛 | 博客
  • 博客访问: 22970
  • 博文数量: 1
  • 博客积分: 76
  • 博客等级: 民兵
  • 技术积分: 41
  • 用 户 组: 普通用户
  • 注册时间: 2010-12-15 12:40
文章分类
文章存档

2012年(1)

我的朋友

分类: 系统运维

2012-08-03 17:58:45

这一节我们来看看搜索引擎中最重要的几个数据结构。

前面我们说过索引包含正向索引和反向索引两部分,首先我们看看正向索引的结构。

正向索引用来存储文档的各种属性,从逻辑上讲,正向索引其实就是一个大数组,数组中每个元素就是一个文档的属性集合。
如果正向索引是有Schema的,那么它其实就类似一个关系表或者说二维数组,纵轴是文档,横轴是属性;如果正向索引是Schema Free的,那么它就类似一个Map的数组,每个文档都是一个Map,key是属性名,value是属性值。
文档在正向索引这个大数组中的下标也是有用的,在很多搜索引擎的实现中,这个下标被称为文档的逻辑ID,叫它ID是因为它唯一的标示了某个特定的文档,叫它“逻辑”是因这个ID只在这个索引中有意义,而且文档也许有自己的类似于ID的属性,要避免混淆。
创建正向索引的过程极其简单,只需要在这个大数组后面追加新的文档即可,每次追加一个文档就会给这个文档产生一个新的逻辑ID。
在搜索引擎中,一般不会从正向索引中删除任何文档,如果需要进行删除操作,则在每个文档中设立一个是否删除的标志,已删除的文档置1。

正向索引其实就这么点东西,下面我们来看看反向索引,这个稍微复杂点。

要实现关键字查询,就必须有一个可以用关键字找到文档的数据结构,所以反向索引逻辑上来说就是一个字典,key是关键字,value就是一个文档集。
在这里刚好用上我们之前在正向索引里产生的逻辑ID,因为逻辑ID唯一的标示一个文档,所以反向索引中的文档集就变成了一个逻辑ID的集合,实现中当然没这么简单,我们等下再说复杂的。
当然,如果仅仅使用这样一个结构,我们一次只能查询一个关键字,即便是作为一个玩具来说功能也太弱了点,下面我们来看看多关键字联合查询怎么做。
两个关键字的“联合”,最简单的有AND和OR两种关系,对于AND关系,我们需要将两个关键字对应的结果集取交集;对于OR则需要取并集;多个关键字只需照此办理即可。现在我们有一个实际的问题,那就是每个关键字对应的结果集可能超大,对它们求交集并集可能是一个昂贵的操作,昂贵到无法消受。
从前面说过的逻辑ID的产生规则可以知道,逻辑ID是由小到大顺序产生的,没有重复,利用这一点我们可以做一些有效的优化。
首先,由于文档是顺序进入正向索引的,所以逻辑ID在加入反向索引时保持升序,如果我们能保持这个顺序,反向索引中每个关键字对应的文档集就变成了一个有序的线性结构,AND和OR操作也就变成了两个有序ID链的交和并。
回顾一下学校中关于算法和数据结构的教材,如果我没记错的话应该有这样的作业题,我就不帮大家做作业了。

很多搜素引擎还支持过滤条件,例如日期、价格等,最简单的方法就是,拿到反向索引匹配的结果集后,对其中的每个文档,在正向索引中检查它们的属性是否满足过滤条件,如果满足则保留,否则丢弃,最后剩下来的就是即匹配了关键字又满足过滤条件的文档。

到目前为止,我们已经实现了一个最基本的全文搜索引擎,它可以支持多关键字的AND/OR查询,还可以支持过滤条件,从功能上来说基本相当于一个玩具版Lucene :D:D

从下一节开始,我们来说说如何把目前的这个“玩具”一步步变成一个功能比较完备的产品。

阅读(2911) | 评论(0) | 转发(2) |
0

上一篇:没有了

下一篇:没有了

给主人留下些什么吧!~~