搜索 正排索引 和 倒排索引 区别

一、什么是正排索引（forward index）？

简言之，由key查询实体的过程，使用正排索引。

例如，用户表：

t_user(uid, name, passwd, age, sex)

由uid查询整行的过程，就是正排索引查询。

画外音：时间复杂度可以认为是O(1)。

二、什么是倒排索引（inverted index）？

与正排索引相反，由item查询key的过程，使用倒排索引。

对于网页搜索，倒排索引可以理解为：

Map<item, list<url>>

能够由查询词快速找到包含这个查询词的网页的数据结构。

画外音：时间复杂度也是O(1)。

举个例子，假设有3个网页：

url1 -> “我爱北京”

url2 -> “我爱到家”

url3 -> “到家美好”

这是一个正排索引：

Map<url, page_content>。

分词之后：

url1 -> {我，爱，北京}

url2 -> {我，爱，到家}

url3 -> {到家，美好}

这是一个分词后的正排索引：

Map<url, list<item>>。

分词后倒排索引：

我 -> {url1, url2}

爱 -> {url1, url2}

北京 -> {url1}

到家 -> {url2, url3}

美好 -> {url3}

由检索词item快速找到包含这个查询词的网页Map<item, list<url>>就是倒排索引。

画外音：明白了吧，词到url的过程，是倒排索引。

正排索引和倒排索引是spider和build_index系统提前建立好的数据结构，为什么要使用这两种数据结构，是因为它能够快速的实现“用户网页检索”需求。

画外音，业务需求决定架构实现，查询起来都很快。

每秒10W次分词搜索，产品经理又提了一个需求！！！（收藏）