文|唐常杰（四川大学，计算机学院，教授）
映射-归约（Map-Reduce）是谷歌多年前推出的建立海量数据索引的方法，有人说它是里程碑性的技术。而理解“映射-归约”，又是理解更时髦的Hadoop和Spark等大数据技术的基础。一位作管理的朋友说，虽看过一些大数据相关文章，但对“映射-归约”的体验很不踏实，最先在网上，也曾在云里, 而今却在雾中；鼓励我写一篇科普文章，以便能让非计算机专业朋友了解梗概。
其实，在谷歌之前，人们就不知不觉地用了映射-归约技术，如机场分发登机牌，银行取号排队，流水作业阅卷，不过，要说清楚“映射向何方，归约在何处”，还有一点挑战，Let me try。
1、搜索引擎有多快
本文将三次用到飞机航班相关的实例，在百度（或谷歌）查询栏中输入”CA1209”，不到一秒钟，百度给出200个结果，分成20多页呈现,其中前几页是比较靠谱的，为后面叙述方便，不妨把这200个结果页面记为p1,p2,…,p200。
2 为什么快？养兵千日的倒排索引
搜索网站服务器中有这样一个索引，类似于规范的科技书籍之书末索引，其特点是一关键字对多个标号（或页码），又称为倒排表,其中航班“CA1209”这一项关键字，对应了百度列出的200条信息p1,p2,…,p200.
百度在回答查询时，一秒钟送出这些现成的p1,p2,…..,p200。不过是小菜一碟的用兵一时。
而这个倒排索引是由若干万台电脑（或CPU）以365×24方式,夜以继日做出来的结果，真是养兵千日。
3、大数据环境下，倒排索引有多难
设某搜索引擎每天新增1亿篇网文，考虑到网文中有些太平凡的字词（停用词，Stop Word）不适合做关键字，如 “的”、“地”、“得”、“不但”、“而且”，等等，每个网页平均有效关键字按100估算，要做完一天新增网页的倒排表，用笨方法，需要读扫描1亿网页，写处理100亿词汇，然后记录下所有如下的对子：
<关键字，所在页面>
再加以整理，去重、合并、压缩，这需要用多少个CPU小时！需要多大的空间！
谷歌在创业之初，提出了一个从海量文档中做倒排索引的聪明方法–Map-Reduce（映射-归约），正是它，协调若干万台电脑，并行计算，完成了倒排表的构建与维护，使谷歌在求多求快的竞争中立于不败之地。
下面用机场办理登机牌的例子来说明。
4 机场登机牌分发中的映射-归约
乘客在首都机场办理登机手续时，会经过三次映射（三次映射的复合还是映射）和一次归约。
4.1 第一次映射，分而治之，进入首都机场候机大厅，乘客会看到如下的液晶屏：
这屏信息，提示乘客按航班分流，例如航班CA1209是在K0—K14号的15个值机台办理登机牌；分而治之，缩小了数据规模，这是古代政治家治理国家的经典策略，也是如今处理大数据朴素方法。
4.2 第二次映射，把乘客分到值机台
下图展示了首都机场K0–K14值机台办理登机牌的情况。为保护隐私，故意把图片做了模糊化处理。
右边是乘客队列（相当于第3段例子中的每天新增的1亿个网页）。在中间，一位机场人员把乘客分成组（例如15人一组），一次进入一组，分到15个值机柜台，引导加上乘客趋短避长的心态，保证了各个小队列长度大致平衡。