本文主要是介绍算法：倒排表/倒排索引（Inverted index），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
搜索引擎最核心的技术， 倒排索引技术，倒排索引可能需要分成几篇文章才说得完，我们先会说说倒排索引的技术原理，然后会讲讲怎么用一些数据结构和算法来实现一个倒排索引，然后会说一个 索引器怎么通过 文档来生成一个倒排索引。
什么是倒排索引呢？索引我们都知道，就是为了能更快的找到文档的数据结构，比如给文档编个号，那么通过这个号就可以很快的找到某一篇文档，而倒排索引不是根据文档编号，而是通过文档中的某些个词而找到文档的索引结构。
倒排索引技术简单，高效，简直是为搜索引擎这种东西量身定做的，就是靠这个技术，实现一个搜索引擎才成为可能，我们也才能在海量的文章中通过一个关键词找到我们想要的内容。
我们看个例子，有下面的几个文档：
| 文档编号 | 文档内容 |
|---|---|
| 1 | 这是一个Go语言实现的引擎 |
| 2 | PHP是世界上最好的语言 |
| 3 | Linux是C语言和汇编语言实现的 |
| 4 | 谷歌是一个世界上最好的搜索公司 |
直观的看，我们通过编号1,2,3,4可以很快的找到文档，但是我们需要通过关键词找文档，那么把上面那个表格稍微变化一下，就是倒排索引了
倒排表（倒排索引）【只列出了部分关键词】
| 关键词 | 文档编号 |
|---|---|
| Go | 1 |
| 语言 | 1，2，3 |
| 实现 | 1，3 |
| 搜索 | 4 |
| 引擎 | 1 |
| PHP | 2 |
| 世界 | 2，4 |
| 最好 | 2，4 |
| 汇编 | 3 |
| 公司 | 4 |
| 这样就非常好理解了吧，实际上倒排索引就是把文档的内容切词以后重新生成了一个表格，通过这个表格，我们可以很快的找到每个关键词对应的文档，好了，没有了，到这里，就是倒排索引的核心原理，也是搜索引擎最基础的基石，不管是谷歌还是某度，最核心的东西就是这两个表格，没这两表格，啥都干不了。 |
看上去很简单吧，好吧，我们现在来模拟搜索引擎进行一次搜索，比如，我们键入关键词：搜索引擎
- 首先将 “搜索引擎” 这个词进行分词：搜索/引擎；
- 我们在表格2中查到 “搜索” 这个词出现在第4行， “引擎” 这个词出现在第5行；
- 找到第4行的第2列、第5行的第2列，把文档编号找出来，是1和4
- 去第一个表格通过文档编号把每个文档的实际内容找出来
- 将1和4的结果显示出来
- 搜索完成
上面就是搜索引擎的最基础的技术了，如果来设计一个数据结构和算法来实现表2就成了搜索引擎技术的关键。
在实现数据结构和算法之前，我们需要知道搜索引擎搜索的是海量的数据，一般的中型电商的数据都是几十上百G的数据了，所以这个数据结构应该是存储在本地磁盘的而不是在内存中的，基于以上的考虑，为了快速搜索，要么自己实现cache来缓存热数据，要么考虑使用操作系统的底层技术MMAP，鉴于我自己实现的cache不见得（基本上是不太可能）比操作系统做得好，所以我使用的是MMAP。
参考资料：
搜索之倒排索引
这篇关于算法：倒排表/倒排索引（Inverted index）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
