倒排索引 Inverted index

1. 正排索引 index

索引 index 就是一种为了快速查找而建立的数据结构。比如在 Mysql 中采用 b+树,维护索引,从而实现数据的快速查找。

其核心还是根据 key 查找 item

2. 倒排索引 inverted index

当数据量非常大的时候,按照 key 来查找item 的方案就会非常耗时,尤其是在处理搜索引擎这种海量数据的场景。

举一个栗子

url1 --> I am a black animal
url2 --> I am a hero
url3 --> This is a Chinese
这时候如果想要查找 black 这个item,那么就需要完全遍历所有的 key「即URL」,在海量数据的时候,这样的时间消耗是不能接受的。

因此,Inverted Index 应运而出

I --> url1, url2
am --> url1, url2
a --> url1, url2, url3
black --> url1
现在要查找 black 这个词,直接去inverted index 中查找,即可。时间消耗大大降低。

Inverted Index 是 按照item查找key

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容