062 | Google如何在一毫秒内找到你想要的上百万份文档

​昨天讲了人和计算机在查找同一个目标时的一些共同之处，既会使用顺序查找，也会使用类似字典查找那样的二分查找。当然，使用后者需要对所有的数据先排序。无论是哪一种方法，在处理非常大量的数据时，都会显得力不从心。比如，我们要把北京市所有叫“李强”的人找出来，这件事就有点难办。为什么呢？因为叫李强的人太多了。我的合伙人就叫这个名字，他每次进出海关时都比我们花的时间要长，因为海关的人要一一核对所有细节才能确认他确实是某个特定的李强（也就是护照上写的那个）。后来他专门做了研究，发现全中国有两百多万个叫李强的人，超过人口的千分之一。按照这个比例，在北京市会有3000~4000个李强，把这么多李强都找到，上面两种方法就不太灵光了。

顺序查找显然不可取，毕竟北京市有2000多万具有当地户籍的人。如果我们将所有的人按照姓名排一个序，进行二分查找，是否可行呢？我们假定一个理想状况，北京市的人口没有变动，是静态的，所有的人也都排好了序。这样通过二分查找，找到某一个李强只需要25次查找。这看上去不算太多，至少和2000万人口对比是如此。但是，这只是找到一个，未必是护照上的那一个。由于北京市的人口都排好了次序，因此我们知道其他的李强要么排在他前面，要么排在他后面，接下里我们只能用排序查找的方法，往前找一遍，直到把前面的李强都找到，然后再往后找一遍，这样大约要查3000~4000个户籍记录，才可以把所有李强都找全了。讲到这里你可能会觉得这种办法太机械了，不够灵巧，做了很多无用功。

上述方法还有一个问题。因为数据库是按照姓名排序的，如果要找到北京市里面所有从清华大学毕业的人，按照姓名排的序就没有任何帮助。当然，你可以再把2000万人的数据库复制一份，再按照毕业的学校排一次序，然后进行二分查找。不过，如果又有人提出，需要找到北京市所有在腾讯公司工作的人，难不成还需要再有第三个数据库是按照就职单位排序的？如果Google的搜索引擎是这么做的，不要说一毫秒内找到上百万个相关文档，一个恐怕也找不到，这还不算复制数据库所浪费的时间。

然而，上述的需求是信息管理中经常遇到的，那么计算机对这个问题会怎么处理呢？最简单的办法就是建立索引。

什么是索引呢？其实计算机里的索引和很多图书最后附带的关键词非常类似。在图书的关键词索引中，会列举出主要关键词在书中的位置，比如索引写清楚了“计算机”这个词出现在书中的第2~5页，8~10页和33页。计算机里面的索引也是类似地。比如我们先把北京市户籍数据中每一个人名的记录编号好，相当于书的页码。它的人名索引是这样的，索引的每一行是一个名字，后面是叫这个名字的所有人的信息记录编号。比如，在索引中，叫李强这个名字的人，是数据库中第2,013,210到第2,016,902的人。这样，要找出北京市所有的李强，只要现在索引中找到李强这一行，然后根据索引的指示，到数据库中，直接调出第2,013,210到2,016,902个记录即可。建索引比直接进到数据库中查找的好处非常多，我们至少可以列举出下面这些好处:

• 第一，如果一个数据库有了索引，其实不需要进行排序，也可以快速查找到所需要的信息。我们还用李强这个例子，并不需要所有的李强在数据库中都放在一起，只要在索引中一一列举出李强在档案库中的记录号就可以了。比如，李强的记录号是35、783、3499，…，等等
• 第二，由于不需要对数据进行排序，当数据库不断变动时，维护数据库的成本就非常低。我们昨天讲，要维持一个数据库有序，成本是很高的，因为每一次增加一些数据，或者删除一些数据，都要重新对它进行排序，而排序是件话时间的事情。不要要排序，就省了很多事情。
• 第三，前面提到的要找到在某个单位工作的人，从给某个大学毕业的人，都很容易解决，因为再按照工作单位建一个索引，按照毕业的学校建一个索引就可以了。每当遇到新的需求，就建立新的索引就好了。（怎么想起了pivot table）
• 第四，如果做一些复杂的操作，比如要找到清华大学也的李强，只要在人名索引中把李强的记录编号找到，再从毕业学校索引中，把清华大学对应人员的记录号找到，重合的号码，就是那些从清华毕业的李强。（根据我的合伙人讲，他当学生时，清华有超过10个叫李强的。）

介绍完索引，就可以解释Google的搜索为什么那么快了。

首先，Google把在网络上所有能找到的文档（以及图片、视频等等内容）下载以后，会对每一个词建立索引，记录下来每一次词都出现在哪一篇文档（网页）中的哪一些具体的位置。比如“得到”这个词出现在第105页个网页的第4、9、37个位置，第403个网页的第9、40、77个位置，第588个网页的第73、203个位置，等等。这样，但一个互联网的用户搜索“得到”这个词的时候，只要在索引中找到这个词，就能通过一个操作，把互联网上所有的包含“得到”的文本找出来了。网页搜索的这种做法和你在Word中打字时，用Ctrl + F查找时不一样的。在Word中是不会对每一个词建索引的，因此查找时是顺序查找，一个个来，查找完一遍，计算机实际上是把你输入的文章也浏览了一遍。在网页搜索中，因为这个数据量是在太大，全世界大约有1000亿个有意义的网页，即使每个网页平均只有500个词，那也是50万亿个词，是不可能用顺序搜索的。在使用Word写作时，一篇文章最多不过几万字，顺序浏览一遍还是可以忍受的。

其次，当你要搜索一组关键词时，比如搜索同时包含，“得到”“方法论”这两个词，如果没有索引，可就麻烦了。即使找到了包含“得到”这个词的网页额，还要想办法看看里面是否有“方法论”这个词，这非常花时间。如果有了索引，我们知道“得到”这个词出现在第105、403、1032等网页中，那么只要找到这两个索引的交集，也就是403等等，就可以了，这个操作就简单很多。如果你要搜索一个长句子，搜索引擎会先把它分割成一个个独立的词，然后根据每一个词的索引，找到这个句子（噢噢！拿撸霍多。我记得会被“+”分隔）

最后，需要说的是，Google在建立索引时，是对所有的词建立索引的，而不仅仅是对于一些重要的词建立索引的。（这得多大的工程量？）。因此Google搜索出来的结果非常全，不会漏掉很多。而大部分其他的搜索引擎，为了节省成本，常常把一些他们认为不重要的词忽略掉，因此用户会发现找到的网页没有Google找到的多。（比如用360，搜狗，百度，雅虎时确实是这种体验）

此外，Google是对所有的语言，所有的文字建一个统一的索引，而国内的搜索引擎，会把文本分为中文的，英文的，或者其他什么文字的，单独建立索引。这在仅仅做一个市场生意时，起步可能会工作量小一点，运营成本会高点，但是，要想做全球化的生意，就几乎不可能了。不仅如此，你如果在国内用这些搜索引擎查找外文的东西，几乎找不到。（扶不上墙的烂泥，赚了钱就倒下了）

了解了索引，你就清楚为什么搜索引擎非常快。事实上，今天你在网络上找一篇文章，甚至比你在自己的计算机内找一篇文章更快。这个现象不仅大家都发现了，而且十多年前Bill Gates也因此批评微软的操作系统做得不好。你可以想象，一个公司里老大发了狠，下面自然会有人响应，这就导致了微软第一款强调个人电脑本机搜索的OS Windows Vista的诞生。不过遗憾的是，Vista是一款非常失败的产品，其中的原因我们明天具体分析。

总结下今天的内容：

• 第一，为了方便地查找信息，一个简单有效的方法就是根据信息的内容，建立索引。从原理上讲，计算机的索引和图书后面的关键词索引很相似，它们都保存着所要找的信息的位置。如果所要找的信息不止一条，它会保留所有的位置。但是所不同的是，书后面关键词的索引只有一种，而计算机的索引常常需要根据应用场景建立很多种。
• 第二，索引有很多好处，不仅带来搜索的效率，而且带来灵活性，对于同一个数据库，可以建立各种索引，以便按照不同门类的信息进行查找。一般索引只会根据一个维度的信息进行建立，而不会用几个维度的组合信息建立，比如，不会建立“人名 + 毕业学校”这样的索引。
• 第三，善于建索引，不仅是Google查找信息非常快的根本原因，也是保证Google的产品在信息爆炸的时代能体现出高质量的原因。事实上在Google内，使用索引几乎成了所有软件开发的标准。今天一些公司做出来的软件产品质量不高，一个很重要的原因是开发者对索引的重要性缺乏认识，（不光是索引，一个产品经理或者创业着，对某些关键概念、技术、产业缺乏足够的理解，对其重要性缺乏认识，是没办法让自己的产品在竞争中最终胜出的。），思路还停留在小数据时代(对的，小数据时代的思维方式），以至于很多功能的速度奇慢无比。
• 第四，从索引中你可以看出，为什么计算机需要里面的一切东西进行编号，因为没有编号，就无从建立索引。
• 第五，索引这件事，不是我们人平时工作会用到的，因为我们人接触的信息不多。但是，在工作中，把东西整理好，有条不紊，一定是提高效率的好办法。我经常讲烂笔头永远比最好的头脑可靠，其实也是这个道理。我们的头脑就相当于一个大数据库，里面什么东西都有，你真要找一个东西，其实很困难。（哇擦，这不就是我搞MCL的一个重要原因么？？把无数的dot写下，不停的思考和organzie，一点点的连城线，滑动线构成知识框架体，然后需要某个信息时，从中取出）在纸上或者笔记本上写下今天要做的事情，做完一项划掉一项，是提高效率很好的办法。

Q：你如何把计算机算法应用到你的生活和工作中呢？

A1: 所有的数据库底层表都是单一维度，比方说，用户基础信息表，订单明细表，交易流水表。它们之间会通过【主键】关键，这个主键，可以是用户id（给用户赋予的编号）（这不是SQL么？），也可以是订单id，这样就可以在此基础上将各种基础表串起来，建立各种具体业务场景的统计数据表。遇到问题先别急，尽量抓住本质，所以在生活中应该多总结多归纳，抽象出浅显易懂的道理。

A2：1. 索引 = 快速查找。由于公司内部有上千件固定资产，以前每年年底的审计都是最头痛的问题，财务清单出来的后，东西找不到或者至少需要一周的时间，极大地浪费了人力资源。某一天学习了兄弟公司的做法，为每个设备建立Inventory（固定资产清单），里面包含：索引号、设备所在的座位号、设备归类、设备名称、具体配置、使用人、何时购买、保修时长等等。现在年底时资产清点，根据审计部门给出的清单能用最少的时间（从之前的一周缩短到了一个小时）来完成任务，节约了人力成本的同时增强了工作效率。2. 索引 = 快速分析。每年都有预算需要采购一部分的IT设备以替换旧款或补充新款，作为一位中层管理者，需要站在老板的视角审视问题，当提出需要购买某一项设备时，可以通过原先建立的Inventory来快速分析需要采购设备的数量、正在使用的数量和库存数量以及故障情况，然后做出购买决策，一切以数据先行的原则，能够让老板直观的看出你的需求，这个也是索引带来的好处，能够快速集合数据，然后根据这些数据达到分析的目的。以上是我工作当中使用索引为日常的工作带来的一部分好处。

A3：“要把基因技术与最新的IT技术相结合”与“建立索引”的启发。目前人和动物身上发现的可能导致肿瘤的基因错误大约有5000种，而癌症的种类不过一百来种，也就是说，即使考虑到导致癌变的基因复制错误和各种癌症的全部组合，不过是几百万种。上百万这个数量级在医学领域近乎无穷大，而在IT领域是非常小的。如果能利用大数据技术，在这上百万中组合中找到相应的药物，那么对于所有人可能的病变都能够治疗。







​