倒排索引是什么,Elasticsearch 又是什么

02 · 两种索引,方向正好相反

正排索引 vs 倒排索引

下面用 6 篇一句话文档做例子,后面的演示都基于这几篇:

1: the quick brown fox jumps over the lazy dog
2: the lazy dog sleeps all day
3: quick fox is a clever animal
4: my dog loves to play in the park
5: the cat sat on the mat
6: quick brown fox and lazy dog are common in stories

03 · 建倒排索引的三步

分词 / 归一化 / 倒排表

04 · 现场直播

亲手建一个索引,再亲手查一次

下面的演示分两部分:先看着索引一步步被建起来,再看一次真正的查询——两个词的倒排表都排好了序,查询时用两根指针从头往后扫,这个算法叫归并(merge),和归并排序合并两个有序数组是同一个技巧。整个过程用代码真跑过,并且和"笨办法"(挨篇文档暴力扫描)的结果逐条核对一致,不是随手画的动画。

05 · 为什么这么快

把"暴力扫描"和"倒排索引"放在一起比一比

假设有 100 万篇文档,平均每篇 300 个词。要找出所有包含"倒排索引"这个词的文档:

• 暴力扫描:每篇文档都要读一遍、逐词比较,最坏情况约 100万 × 300 = 3 亿次比较。文档越多、越长,这个数字线性往上涨,没有任何捷径。
• 倒排索引:直接去词典里找"倒排索引"这一项,拿到它的倒排表——如果这个词只在 8000 篇文档里出现过,你面对的就是一份 8000 个数字的列表,而不是 3 亿次比较。建索引的成本在写入数据的时候就已经付过了,查询的时候直接享受现成的结果。

多个词一起查(比如 AND)呢?两份倒排表都已经排好序,用上面演示里那种"两根指针从头往后走"的归并算法,只需要把两份表各扫一遍——时间只跟"两份表加起来多长"成正比,而不是"表 A 的每一项都去表 B 里找一遍"(那样是长度相乘,慢得多)。伪代码大概是这样:

i, j = 0, 0
result = []
while i < len(listA) and j < len(listB):
    if listA[i] == listB[j]:
        result.append(listA[i])   # 两边都有,命中
        i += 1; j += 1
    elif listA[i] < listB[j]:
        i += 1                    # A 这边小,A 往前走一步
    else:
        j += 1                    # B 这边小,B 往前走一步
return result

为什么必须先排序:如果两份列表是乱序的,指针没法"哪边小就走哪边"这样简单地往前挪,只能退化成挨个去另一边里找,速度立刻打回"暴力"的水平。这也是为什么倒排表建好之后,文档编号必须保持有序——排序不是为了好看,是为了让归并算法能生效。

06 · 光找到还不够,得排出好坏

相关性打分:TF-IDF 与 BM25

倒排索引解决的是"哪些文档包含这个词",但真实搜索还要回答"这些文档里,哪篇跟我最相关"。经典做法叫 TF-IDF,拆开看很好懂:

• TF(词频,term frequency):一个词在某篇文档里出现得越多次,这篇文档大概率跟这个词关系越大。
• IDF(逆文档频率,inverse document frequency):如果一个词几乎所有文档都有(比如"的"“是"),它就没有区分度,权重应该低;反过来,一个词越稀有,能在某篇文档里出现就越说明这篇文档专门讲这件事,权重应该高。

把 TF 和 IDF 相乘,就是一篇文档对这个词的分数,分数越高排名越靠前。Elasticsearch(以及背后的 Lucene)默认用的是 TF-IDF 的改进版 BM25,主要改进了两点:词频不是越高越好(出现 10 次和出现 100 次,相关性差别不该那么大,需要"边际递减"处理);要考虑文档长度(长文档天然词多,原始词频会占便宜,需要按长度打折)。你不需要记住公式,只要知道:搜索结果的排序,依据的是"词有多稀有"和"词在这篇文档里有多突出",而不是随便排的。

07 · Elasticsearch 到底是什么

Lucene 加上"分布式"这层壳

上面讲的分词、倒排表、归并查询、打分排序,全部是一个叫 Lucene 的开源库真正实现的东西(Java 写的,Apache 协议开源)。但 Lucene 只是一个库——你得写 Java 代码调用它的 API,而且它天生是单机的,一台机器的硬盘和内存放不下的数据,它管不了。

Elasticsearch 就是在 Lucene 外面包了一层,补上了三件事:

• 网络接口:不用写 Java 调 API,发一个 HTTP 请求、传一段 JSON 就能存数据、查数据,任何语言都能用。
• 分片(shard):数据量大到一台机器放不下(或者想让查询更快),就把索引拆成好几份,分别交给不同的机器。想象一本百科全书太厚了,一个人抱不动、翻页也慢——拆成好几卷,交给不同的人保管,查的时候几个人同时在自己那一卷里找,再把结果汇总,比一个人从头翻到尾快得多。
• 副本(replica):每一卷再复印一份,交给另一个人也保管一份——原本那个人请假了(机器宕机),复印本立刻能顶上,数据不会丢、服务不会断。

再加上聚合(aggregation)能力——不只是"找到包含某个词的文档",还能做"按小时统计出现错误关键词的日志条数"这类统计分析,这也是为什么 Elasticsearch 常常不只被当搜索引擎用,还被当分析引擎用。

08 · 什么时候该用

真实场景

• 站内全文搜索:电商网站的商品搜索、文档站/博客的搜索框、App 里的搜索功能——只要用户会输入关键词、你需要"模糊匹配 + 按相关性排序",这就是 Elasticsearch 的核心场景。
• 日志与可观测性(经典的 ELK/Elastic Stack):把服务器日志、应用日志统一收集进 Elasticsearch,能几秒钟内搜出"过去一小时所有带 error 的日志",这是目前最常见的生产用法之一,Kibana(配套的可视化工具)负责把这些数据画成仪表盘。
• 准实时的数据分析/报表:靠聚合能力做统计看板,数据写进去几秒后就能被查询和统计到。

不适合的场景:需要强一致性的交易型数据(比如银行转账、订单主记录)不该把 Elasticsearch 当成唯一的数据源——它更适合当"专门用来搜索的镜像副本"。常见做法是主数据放在关系型数据库(或者其它专门的存储)里,再同步一份到 Elasticsearch 用来搜索,而不是反过来。

09 · 参考与说明

这篇文章做了哪些简化

• 示例里的分词只是按空格拆分英文单词、转小写、过滤一份很小的停用词表——真实的 Lucene 分词器(analyzer)要处理标点、大小写、词干提取(stemming,比如把 "jumps" "jumping" 都归一到 "jump")、多语言(尤其中文分词)等复杂得多的情况。这篇为了让每一步都能被肉眼看懂,刻意跳过了这些。
• 真实的倒排表除了文档编号,通常还会记录词频、词在文档里的具体位置(用于短语搜索,比如精确匹配"quick fox"这个词组)——这篇的演示只保留了"出现在哪些文档"这一层,没有展开位置信息。
• Lucene 是开源项目,想深入可以看 github.com/apache/lucene;Elasticsearch 的官方文档在 elastic.co/guide。这篇没有像之前讲 Go 运行时那样逐行引用它们的源码——面向的读者不同,这里更注重把"倒排索引是什么、为什么快"这个核心概念讲清楚。
• 本文里"6 篇文档建索引、3 条查询"的完整过程和结果,是用 Python 脚本真实跑出来的,并且和暴力扫描的结果逐项核对过,不是手算的示例。