The difference between searching forward index and inverted index

One 、 What is a forward index? （forward index）？

in short , from key The process of querying entities , Using forward index .

for example , User table ：

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

from uid The process of querying the whole line , Is the forward index query .

Voice over ： Time complexity can be thought of as O(1).

Two 、 What is inverted index （inverted index）？

Contrary to forward index , from item Inquire about key The process of , Use inverted index .

For web search , Inverted index can be understood as ：

Map<item, list<url>>

It can quickly find the data structure of the web page containing the query word by the query word .

Voice over ： Time complexity is also O(1).

for instance , Suppose there is 3 Pages ：

url1 -> “ I love Beijing ”

url2 -> “ I love going home ”

url3 -> “ Home is beautiful ”

This is a Forward index ：

Map<url, page_content>.

After the participle ：

url1 -> { I , Love , Beijing }

url2 -> { I , Love , home }

url3 -> { home , happy }

This is a Forward index after segmentation ：

Map<url, list<item>>.

Inverted index after word segmentation ：

I -> {url1, url2}

Love -> {url1, url2}

Beijing -> {url1}

home -> {url2, url3}

happy -> {url3}

By key words item Quickly find the web page containing the query word Map<item, list<url>> Namely Inverted index .

Voice over ： I see! , Word to url The process of , It's inverted index .

Forward index and inverted index are spider and build_index The system establishes a good data structure in advance , Why use these two data structures , Because it can be implemented quickly “ User web search ” demand .

Voice over , Business requirements determine architecture implementation , It's quick to find out .

Per second 10W Sub word segmentation search , The product manager raised another demand ！！！（ Collection ）