Question

解密sphinx索引速度为什么是lucene索引速度的10倍这么大的差距

Answer 1

LUCENE索引结构是以2叉树为基础的B树倒排结构，这决定了索引数据时要维护2叉树为基础的B树倒排结构，例如查找并增量，将耗费一定的时间消耗，其时间复杂度为O（LOGN），而sphinx是以HASH哈希树为基础的倒排结构，其时间复杂度为O（1），所以随着数据的增多，LUCENE索引树的维护将超过sphinx索引树的维护。导致sphinx索引速度是LUCENE索引速度的10倍这么大的差距。
附： Lucene 倒排序索引 原理
Lucene 倒排序索引 原理
Lucene 是apache软件基金会[4] jakarta项目组的一个子项目，是一个高性能的java全文检索框架。 lucene 索引 结构 中最核心的部分是 倒排序索引 。
用一个例子描述一下倒排序。
假设有两篇文章：
文章1的内容是：共和国。
文章2的内容是：中国。
1、 Lucene 在建立索引前先通过 分词 器找出文章中的关键词。我们采用一元分词举例。那么文章1的关键词是[共][和][国]，文章二的关键词是[中][国]。
2、倒排序索引
通过分词器找出的对应关系是文章到关键词映射，这样处理后的结果不利于检索，几乎是全扫描。 lucene 再用倒排序建立索引，把这种关系转换成关键词到文章的映射，并对关键词做字符串排序。当然 lucene 还补充了关键词在文章中出现的频度和位置等信息，这里不做描述。到排序后的结果见下表：
关键词
文章号
共
国
1,2
和
中
简单的说 lucene倒排序 就是把分词词元映射到文章位置并对这些记录按分词词元做字符串排序。
对于这样的存储 结构 ， lucene 采用了二元搜索算法来做检索。这也是 lucene 高效的原因之一。
对二元搜索算法做一下简单介绍 ：即二分查找或折半查找算法，对于有n个元素的数组来说,二元搜索算法进行最多1+log2(n)次比较. 即有2的n次方个元素,最多比较n+1次。那么1024*1024*1024个元素，也就比较31次而已。
违禁词分词过滤思路
违禁词分词思路：建立违禁词词典，词元是一个违禁词（包括特殊符号，并且不考虑正向和逆向最大匹配）。那么用违禁词分词器分词后的倒排序就是把 违禁词 映射到文章位置并对这些记录按违禁词做字符串排序。
例如：共和国是违禁词
对文章1和文章2的倒排序索引就是：
关键词
文章号
共和国
明显地，索引记录数等于违禁词数。这样，通过一次建倒排序索引的过程就直接找出目标记录，可大大提高计算效率。