sphinx 源码阅读之分词,压缩索引,倒排——单词对应的文档ID列表本质和lucene无异 也是外部排序再压缩 解压的时候需要全部扫描doc_ids列表偏移量相加获得最终的文档ID

转自:http://github.tiankonguse.com/blog/2014/12/03/sphinx-token-inverted-sort.html

外部排序

现在我们的背景是有16个已经排序的数据存在磁盘上。
由于数据量很大,我们不能一次性全部读进来。

我们的目标是依次挑出最小的hit,然后交给索引引擎处理。

sphinx 使用了 CSphHitQueue 这个数据结构。

CSphHitQueue 你猜是什么? 队列? 恭喜你,猜错了。
CSphHitQueue 是一个最小堆。
且堆的最大个数是 iRawBlocks。

由于 iRawBlocks 个 hits 数组已经排序,所以我们只需要得到 已排序的hits数组的第一个元素,就可以用堆得到最小的那个元素了。
然后我们把最小的这个元素建索引压缩储存,删除最小元素,并取出最小元素所在 hits数组中下一个元素,扔到堆中。
这样就可以从小到大取出所有的元素,并逐个建立索引压缩储存了。

这段话看不懂的话,可以看下面的图。

sphinx 源码阅读之分词,压缩索引,倒排——单词对应的文档ID列表本质和lucene无异 也是外部排序再压缩 解压的时候需要全部扫描doc_ids列表偏移量相加获得最终的文档ID

创建索引压缩储存

其中创建索引压缩储存主要依靠这个函数

  1. cidxHit ( tQueue.m_pData );

其中 tQueue.m_pData 的数据结构如下

  1. /// fat hit, which is actually stored in VLN index
  2. struct CSphFatHit{
  3. DWORD m_iDocID; ///< document ID
  4. DWORD m_iGroupID; ///< documents group ID
  5. DWORD m_iTimestamp; ///< document timestamp
  6. DWORD m_iWordID; ///< word ID in current dictionary
  7. DWORD m_iWordPos; ///< word position in current document
  8. };

hit 是先按 m_iWordID 排序, 相等了再按 m_iDocID 排序, 最后才按 m_iWordPos 排序的。

现在我们先不考虑上面的堆,我们假设所有的 hit 已经在一个数组中了,且按上面的规则排序了。
现在我们想做的是对这个 hit 数组创建索引,并压缩储存。

主要做了这个几件事。

第一,根据 m_iWordID 将分词分为 2014 块。
并使用 cidxPagesDir 记录块的偏移量(还记得索引文件第二个写入的数据吗)。

第二,对于每一块,我们按分词分组,并在索引文件 spi 中储存每个词组的信息。
具体储存的信息如下

  • 和上一个分词(wordID)的偏差
  • 这个分词组在 spd 文件内的长度
  • 这个分词记录的变化次数
  • 这个分词的 hit 数量

第三,对于每个hit,我们存两部分信息。

  • 位置(pos)偏移量信息
  • 文档(docId)偏移量的信息

上面的三部分信息都储存后,我们就可以快速的解析出来。

推理 - 搜索信息

假设我们又上面的压缩的信息了。
我们要搜索一个词时,会如何工作呢?
假设我们已经得到这个词的 wordId 了,只需要二分一下,就可以再 O(log(1024)) 的时间内得到 wordId 在那个块内。

找到一个块内,出现一个问题,我们不能再次二分查找来找到对应的分词列表。 因为这个 index 储存的是和上一个分词的相对偏移量,那只好全部读入内存,扫描一遍对偏移量求和,然后才能找到对应的词。

这个过程中我们进行了两次 IO 操作。
第一次读取块列表信息 cidxPagesDir。
第二次读取选中的那一块的所有数据。

虽然储存偏移量节省了一些磁盘储存,但是却是用扫描整块数据为代价的。我们本来可以直接二分整块数据的。

不管怎样,我们在索引中找到了需要查找的那个分词的位置。
然后我们可以在数据文件内读取对应的信息,然后得到对应记录的id了。

当然,上面这个只是我的推理,下面我们来看看 sphinx 是怎么搜索的吧。

sphinx 搜索方法

看 sphinx 的搜索方法,只需要看 CSphIndex_VLN 的 QueryEx 函数即可。
首先对查询的语句进行分词,然后读取索引头 m_tHeader, 读取分块信息 cidxPagesDir。
然后就对分词进行搜索了。
为了防止相同的分词重复查找,这里采用二层循环,先来判断这个分词之前是否搜索过,搜索过就记下搜索过的那个词的位置。
没搜索过,就搜索。

xxx代码略!

 

看了这个代码,和我想的有点出入,但是总体思路还是一样的。
它是把所有的 cidxPagesDir 全储存起来了,这样直接定位到指定的位置了。少了一个二分搜索。
定位到某个块之后, 果然采用暴力循环来一个一个的增加偏移,然后查找对应的分词。
找到了记录对应的位置的四大元信息。

再然后由于数据量已经很小了,就把匹配的数据取出来即可。
当然,取数据的时候会进行布尔操作,而且会加上权值计算,这样就搜索满足条件的前若干条了。












本文转自张昺华-sky博客园博客,原文链接:http://www.cnblogs.com/bonelee/p/6249396.html,如需转载请自行联系原作者


上一篇:oracle分区技术


下一篇:解读阿里云内容协作平台-增值服务