关于倒排索引,反向索引-Inverted　index--梦飞翔的地方(梦翔天空)

倒排索引（英语：Inverted index），也常被称为反向索引、置入档案或反向档案，是一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构。

有两种不同的反向索引形式：

一条记录的水平反向索引（或者反向档案索引）包含每个引用单词的文档的列表。
一个单词的水平反向索引（或者完全反向索引）又包含每个单词在一个文档中的位置。^[1]

后者的形式提供了更多的兼容性（比如短语搜索），但是需要更多的时间和空间来创建。

例子

以英文为例，下面是要被索引的文本：

$T 0 =$ "it is what it is"
$T 1 =$ "what is it"
$T 2 =$ "it is a banana"

我们就能得到下面的反向文件索引：

 "a":      {2}
 "banana": {2}
 "is":     {0, 1, 2}
 "it":     {0, 1, 2}
 "what":   {0, 1}

检索的条件"what", "is" 和 "it" 将对应这个集合：。

对相同的文字，我们得到后面这些完全反向索引，有文档数量和当前查询的单词结果组成的的成对数据。同样，文档数量和当前查询的单词结果都从零开始。所以，"banana": {(2, 3)} 就是说 "banana"在第三个文档里 ( $T 2$ )，而且在第三个文档的位置是第四个单词(地址为 3)。

"a":      {(2, 2)}
"banana": {(2, 3)}
"is":     {(0, 1), (0, 4), (1, 1), (2, 1)}
"it":     {(0, 0), (0, 3), (1, 2), (2, 0)} 
"what":   {(0, 2), (1, 0)}

如果我们执行短语搜索"what is it" 我们得到这个短语的全部单词各自的结果所在文档为文档0和文档1。但是这个短语检索的连续的条件仅仅在文档1得到。

http://seraph115.javaeye.com/blog/378879

＝＝＝＝＝＝＝

反向索引是B*Tree索引的一个分支，它的设计是为了运用在某些特定的环境下的。Oracle推出它的主要目的就是为了降低在并行服务器（Oracle Parallel Server）环境下索引叶块的争用。当B*Tree索引中有一列是由递增的序列号产生的话，那么这些索引信息基本上分布在同一个叶块，当用户修改或访问相似的列时，索引块很容易产生争用。反向索引中的索引码将会被分布到各个索引块中，减少了争用。

反向索引反转了索引码中每列的字节，通过dump（）函数我们可以清楚得看见它做了什么。举个例子：1，2，3三个连续的数，用dump()函数看它们在Oracle内部的表示方法。

SQL> select 'number',dump(1,16) from dual
2 union all select 'number',dump(2,16) from dual
3 union all select 'number',dump(3,16) from dual;

'NUMBE DUMP(1,16)
------ -----------------
number Typ=2 Len=2: c1,2 （1）
number Typ=2 Len=2: c1,3 （2）
number Typ=2 Len=2: c1,4 （3）

　　再对比一下反向以后的情况：

SQL> select 'number',dump(reverse(1),16) from dual
2 union all select 'number',dump(reverse(2),16) from dual
3 union all select 'number',dump(reverse(3),16) from dual;

'NUMBE DUMP(REVERSE(1),1
------ -----------------
number Typ=2 Len=2: 2,c1 （1）
number Typ=2 Len=2

: 3,c1 （2）
number Typ=2 Len=2: 4,c1 （3）

　　我们发现索引码的结构整个颠倒过来了，这样1，2，3个索引码基本上不会出现在同一个叶块里，所以减少了争用。不过反向索引又一个缺点就是不能在所有使用常规索引的地方使用。在范围搜索中其不能被使用，例如，where column>value,因为在索引的叶块中索引码没有分类，所以不能通过搜索相邻叶块完成区域扫描。

http://it.china-b.com/olpz/472598.html