倒排索引常用于搜索引擎,文档搜索. ElasticSearch就使用了倒排索引来检索数据.
正向索引
要理解倒排索引,可以先看看正向索引是怎样的.
举个例子,文章里包含了许多的文字,你想找某个文字出现在哪些文章里. 那么按照遍历每个文章,查看文章中是否出现过关键字的查找就是正向索引.这个查找顺序是文章->文字的. 这就是正向索引(forward index)
缺点: 按照文字来搜索文章需要遍历所有的文章才能得到正确结果.效率较慢
倒排索引
与正向索引相反,倒排索引是文字->文章. 也就是说,存储是按某个文字出现在了哪些文章里来保存数据. 你可以简单想象一个字典,正向索引里的key是文章,value是文字, 倒排索引里key是文字, value是文章.
优点: 按照文字来搜索文章的效率很高.
这就是倒排本身的核心思路了.
Q&A
Q: 为什么ES的搜索效率快? A: ES除了使用倒排索引,还做了许多优化,例如对文字在建立一个索引.比如”hello”,”world”,可以提取出”h”和”w”来再建立一层索引,这样索引的大小更小,使其能够放入内存.内存的效率自然是吊打磁盘, 除此之外,还使用到了FST数据结构来优化操作等等.
