倒排索引(Inverted index)
文章写的有点粗糙，都是只描述了思想，没有去抠具体的细节部分，对这些项目的作者刚到敬仰，把一个理论上的技术用在工程上会遇到很多问题。如果文章中有不妥之处，欢迎去我的github提交 issues.
倒排索引这个数据结构最先是用于搜索引擎的，搜索引擎就通过分析爬虫回来的页面，提取出关键字，记录下关键字对应网页的链接地址，做成一个哈希表，通过搜索关键字即可得到结果。这是理论定义上的倒排索引，工程上实现起来需要考虑很多问题，每个场景下实现的倒排索引都不太一样。
整个倒排索引分两部分，左边是Term Dictionary(索引表，可简称为Dictionary)，是由一系列的Terms组成的；右边为Postings List(倒排表)，由所有的Term对应的Postings组成。
理论上的倒排索引
实现一个简单的倒排索引，通过读取一个文件内容，构造好索引内容，此处用一个
map来存储这个对应关系，通过关键字搜索时打印出对应的行数据。
package main
import (
"fmt"
"strings"
)
const (
// 这段内容复制自es的网站
Content = "The QUICK brown foxes jumped over the lazy dog!\n" +
"An analyzer specified in the query itself.\n"+
"The search_analyzer mapping parameter.\n"+
"The analyzer mapping parameter.\n"+
"An analyzer in the index settings called default_search.\n"+
"An analyzer in the index settings called default.\n"+
"The standard analyzer"
)
var invertedIndex map[string][]string
func main() {
invertedIndex = make(map[string][]string)
contents := strings.Split(Content, "\n")
for i := range contents {
s := contents[i]
s = strings.Trim(s,".!")
fields := strings.Fields(s)
for j := range fields {
field := strings.ToLower(fields[j])
if _,ok := invertedIndex[field] ; ok {
invertedIndex[field] = append(invertedIndex[field],s)
}else {
ss := make([]string,1,2)
ss[0] = s
invertedIndex[field] = ss
}
}
}
var word string
for {
fmt.Print("search word: ")
n, err := fmt.Scanln(&word)
if n == 0 || err != nil {
return
}
doc,ok := invertedIndex[word]
if !ok {
fmt.Println("no match")
continue
}
for i := range doc {
fmt.Println(doc[i])
}
}
}如上就实现了一个简单的倒排索引，通过解析文本内容进行全文搜索，上面只是一个简单版本的搜索，工程中的需要考虑的就比较多了，首先分词器，不同的语言分词规则都不一样，中文、英文都不一样，还有是索引结构，有的用哈希表实现有的用树结构实现，文档内容存储和索引也是一个工程中难处理的问题。
Lucene 中的倒排索引
Lucene把用于存储Term的索引文件叫Terms Index，它的后缀是.tip；把Postings信息分别存储在.doc、.pay、.pox，分别记录Postings的DocId信息和Term的词频、Payload信息、pox是记录位置信息。Terms Dictionary的文件后缀称为.tim，它是Term与Postings的关系纽带，存储了Term和其对应的Postings文件指针。
总体来说，通过Terms Index(.tip)能够快速地在Terms Dictionary(.tim)中找到你的想要的Term，以及它对应的Postings文件指针与Term在Segment作用域上的统计信息。
在Lucene中索引和搜索是不一样的，索引是指把Document进行分析，存入索引文件中，搜索是从索引文件中进行读取。
Lucene中的索引操作比较复杂，因为操作的数据量非常大，所以进行了多部索引处理，文件索引到文件就是一个小型的文件系统，倒排索引再映射到文件索引上。为了查找快速。
文件索引应该是记录了整个文档的开始位置和结束为止，比如下：
-
数据文件：test.data
1:the man is like dog2:this is a man3:this is a dog -
文件索引文件
1:[2-19] 2:[22-32] 3:[35-48] # 记录的就是数据文件中的具体偏移量 -
倒排索引记录
[the](1,1) [man](1,2)(2,4) [is](1,3),(2,2),(3,2) # stopwords [like](1,4) [dog](1,5),(3,4)
上面大概的描述了Lucene的存储结构，真实的有很多改进，比如数据文件有压缩，文件索引也有压缩。
Lucene对于删除操作，不直接删除索引，而是通过标记为一删除操作。
Lucene中还有一个正向索引，用于存储DocId和文档全部的内容。
参考
Mysql Full index 全文索引中的倒排索引
InnoDB全文索引是基于倒排索引设计的，倒排索引存储了一个单词对应的列表(倒排列表)，还存储了每个字在文档中的位置信息，作为偏移量。这就是一个用空间换时间的办法。
InnoDB 全文索引表
创建InnoDB FullText索引时，会创建一组索引表：
mysql> CREATE TABLE opening_lines (
id INT UNSIGNED AUTO_INCREMENT NOT NULL PRIMARY KEY,
opening_line TEXT(500),
author VARCHAR(200),
title VARCHAR(200),
FULLTEXT idx (opening_line)
) ENGINE=InnoDB;
# 查看本地的辅助索引文件
mysql> SELECT table_id, name, space from INFORMATION_SCHEMA.INNODB_SYS_TABLES
WHERE name LIKE 'test/%';
4128 test/FTS_000000000000101a_0000000000002049_INDEX_1 4112
4129 test/FTS_000000000000101a_0000000000002049_INDEX_2 4113
4130 test/FTS_000000000000101a_0000000000002049_INDEX_3 4114
4131 test/FTS_000000000000101a_0000000000002049_INDEX_4 4115
4132 test/FTS_000000000000101a_0000000000002049_INDEX_5 4116
4133 test/FTS_000000000000101a_0000000000002049_INDEX_6 4117InnoDB使用实现的是Full inverted index，存储了单词对应的位置信息和DocId。这就是Mysql实现倒排索引的数据结构。
把上图进行索引之后存储的结构就是如下图，比如单词days，值为(3:2),(6:2)意思是DocId为3中的第二个单词和DocId为6中的第二个单词。
InnoDB在内存中维护了一个FTS Index Cache全文检索缓存系统，在提交事务或者时超过32m时就进行合并到Auxiliary Table辅助索引表中；
在插入或者删除时都是对缓存系统进行操作，删除也是知识记录，不直接进行删除操作。
参考
Prometheus 中的倒排索引
Prometheus2.0 版本中也使用了倒排索引来做搜索，架构和Lucene很相似，都是按时间分割，然后再合并，都是小文件合并为大文件，小索引合并为大索引，索引使用的不是hashmap结构，而是使用LSM数据结构。未完全看完，后面看完了之后再补上。
总结
基于B+tree实现的倒排索引会有性能问题，在写入时非常消耗IO,因为要进行排序并移动其他节点，Lucene的这种方式可以实现更高的并发性。
- Mysql 的倒排是基于红黑树实现的
- Lucene 是通过不断的创建小的索引文件，然后定期的把小的索引文件合并为一个大的索引文件。