Inverted-index

倒排索引(Inverted index)

文章写的有点粗糙,都是只描述了思想,没有去抠具体的细节部分,对这些项目的作者刚到敬仰,把一个理论上的技术用在工程上会遇到很多问题。如果文章中有不妥之处,欢迎去我的github提交 issues.

倒排索引这个数据结构最先是用于搜索引擎的,搜索引擎就通过分析爬虫回来的页面,提取出关键字,记录下关键字对应网页的链接地址,做成一个哈希表,通过搜索关键字即可得到结果。这是理论定义上的倒排索引,工程上实现起来需要考虑很多问题,每个场景下实现的倒排索引都不太一样。

整个倒排索引分两部分,左边是Term Dictionary(索引表,可简称为Dictionary),是由一系列的Terms组成的;右边为Postings List(倒排表),由所有的Term对应的Postings组成。

理论上的倒排索引

实现一个简单的倒排索引,通过读取一个文件内容,构造好索引内容,此处用一个map来存储这个对应关系,通过关键字搜索时打印出对应的行数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
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进行分析,存入索引文件中,搜索是从索引文件中进行读取。

img

Lucene中的索引操作比较复杂,因为操作的数据量非常大,所以进行了多部索引处理,文件索引到文件就是一个小型的文件系统,倒排索引再映射到文件索引上。为了查找快速。

文件索引应该是记录了整个文档的开始位置和结束为止,比如下:

  • 数据文件:test.data

    1
    1:the man is like dog2:this is a man3:this is a dog
  • 文件索引文件

    1
    2
    3
    1:[2-19]
    2:[22-32]
    3:[35-48] # 记录的就是数据文件中的具体偏移量
  • 倒排索引记录

    1
    2
    3
    4
    5
    [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的存储结构,真实的有很多改进,比如数据文件有压缩,文件索引也有压缩。

image-20190319140311238

Lucene对于删除操作,不直接删除索引,而是通过标记为一删除操作。

Lucene中还有一个正向索引,用于存储DocId和文档全部的内容。

参考

Mysql Full index 全文索引中的倒排索引

InnoDB全文索引是基于倒排索引设计的,倒排索引存储了一个单词对应的列表(倒排列表),还存储了每个字在文档中的位置信息,作为偏移量。这就是一个用空间换时间的办法。

InnoDB 全文索引表

创建InnoDB FullText索引时,会创建一组索引表:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 4117

InnoDB使用实现的是Full inverted index,存储了单词对应的位置信息和DocId。这就是Mysql实现倒排索引的数据结构。

image-20190319134843287

把上图进行索引之后存储的结构就是如下图,比如单词days,值为(3:2),(6:2)意思是DocId3中的第二个单词和DocId6中的第二个单词。

image-20190319134808582

InnoDB在内存中维护了一个FTS Index Cache全文检索缓存系统,在提交事务或者时超过32m时就进行合并到Auxiliary Table辅助索引表中;

在插入或者删除时都是对缓存系统进行操作,删除也是知识记录,不直接进行删除操作。

image-20190319141910280

参考

Prometheus 中的倒排索引

Prometheus2.0 版本中也使用了倒排索引来做搜索,架构和Lucene很相似,都是按时间分割,然后再合并,都是小文件合并为大文件,小索引合并为大索引,索引使用的不是hashmap结构,而是使用LSM数据结构。未完全看完,后面看完了之后再补上。

总结

基于B+tree实现的倒排索引会有性能问题,在写入时非常消耗IO,因为要进行排序并移动其他节点,Lucene的这种方式可以实现更高的并发性。

  • Mysql 的倒排是基于红黑树实现的
  • Lucene 是通过不断的创建小的索引文件,然后定期的把小的索引文件合并为一个大的索引文件。