倒排索引的概念

倒排索引（inverted index），是一种数据库索引，用于存储从内容到文档的映射。使用倒排索引可以很好的支持全文搜索，被广泛应用于信息检索（搜索引擎、数据库）中。

wiki中定义如下：

In computer science, an inverted index (also referred to as a postings file or inverted file) is a database index storing a mapping from content, such as words or numbers, to its locations in a table, or in a document or a set of documents (named in contrast to a forward index, which maps from documents to content). The purpose of an inverted index is to allow fast full-text searches, at a cost of increased processing when a document is added to the database. The inverted file may be the database file itself, rather than its index. It is the most popular data structure used in document retrieval systems,used on a large scale for example in search engines.

索引的目的？索引的目的都是为了加速查询速度。普通索引、倒排索引主要在使用场景（使用需求）上有所区别。

正向索引就如同书的目录，要找第3章第2节的内容，在目录中查找页码即可。

倒排索引则是应用于查找Hash这个词在书中何处出现过。

如下图所示：

倒排索引的结构

倒排索引主要由单词词典（Dictionary）和倒排文件（Posting List）组成。

单词词典存放在内存中，是组成所有文档的单词的集合，单词词典内的每条索引项记载了单词本身的一些信息和指向倒排列表的指针，通过这个指针就可以找到对应的倒排列表。对于一个给定的查询（例如：abc），由单词字典确定该查询中的词在单词词典（Dictionary）中存不存在。实现该结构有Hash table和搜索树两种解决办法。

倒排列表记载了出现过某个单词的所有文档的文档列表和单词在文档中出现的位置信息，每条记录称为倒排向项。因为倒排文件较大，因此需要将倒排列表存储在磁盘上。

倒排索引也可以用如下图形象的表示：Filtering and Tokenization为去停用词，即去除（类似于还是、的、接着这种经常出现但没有明确含义的词汇）

对上面的倒排索引结构进行查询，以apple为目标词汇(terms)，可以得出3、5、6文档中出现了apple词汇；以australia为目标词汇，可以得出文档1，8出现了australia词汇。

单词词典实现

单词词典支持的操作

1. 在单词词典中插入一个新条目（insert，增）
2. 删除一个条目（delete，删）
3. 更改一个条目（update，改）
4. 进行搜索/查询操作（select，查）
   • 查找指定key
   • 查找以给定前缀开头的单词

基于的Trie树的单词字典

Trie树又称为字典树/前缀树，从根节点到结束标记的遍历即使一个单词。Trie树结构如下所示（有压缩情况）：

基于的哈希表的单词字典

哈希表通过一个Hash函数将key映射到不同的桶上，处理hash碰撞是十分重要的话题（哈希表碰撞达到一定程度会进行rehash操作）。

对比

1. 如果哈希表大小选择得当，用于搜索特定术语的哈希表实现通常比基于排序的字典更快（不需要进行树的遍历）。
2. 查找以给定前缀开头的单词（例如搜索“Jef*”），Trie树通常比哈希表要快，因为哈希表方法要扫描整个词典。

总结：类似于数据库索引使用时，点查询使用哈希表更佳，范围查询使用B+ Tree更佳。

reference

[1] https://en.wikipedia.org/wiki/Inverted_index

[2] https://dev.to/im_bhatman/introduction-to-inverted-indexes-l04

[3] https://dev.to/im_bhatman/components-of-inverted-index-the-dictionary-1gf5

[4] https://stackoverflow.com/questions/4363539/how-does-hashing-have-an-o1-search-time/4363602#4363602