搜索

吴军

我们昨天讲了人和计算机在查找一个目标时的一些共同之处，既会使用顺序查找，也会使用类似字典查找那样的二分查找。当然，使用后者需要对所有的数据先排序。无论是哪一种方法，在处理非常大量的数据时，都会显得力不从心。

比如，我们要把北京市所有叫“李强”的人找出来，这件事就有点难办。为什么呢？因为叫李强的人太多了。我的合伙人就叫这个名字，他每次进出海关时都比我们花的时间要长，因为海关的人要一一核对所有细节才能确认他确实是某个特定的李强（也就是护照上写的那个）。后来他专门做了个研究，发现全中国有两百多万个叫李强的人，超过人口的千分之一。按照这个比例，在北京市会有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个记录即可。

建索引比直接进到数据库中查找的好处非常多，我们至少可以列举出下面这些好处：

1. 如果一个数据库有了索引后，其实不需要进行排序，也可以快速查找到所需要的信息。我们还用找李强这个例子，并不需要所有的李强在数据库中都放在一起，只要在索引中一一列举出李强在档案库中的记录号就可以了。比如，李强的记录号是35、783、3499，……，等等。

2. 由于不需要对数据库进行排序，当数据库不断变动时，维护数据库的成本就非常低。我们昨天讲，要维持一个数据库有序，成本是很高的，因为每一次增加一些数据，或者删除了一些数据，都要重新对它进行排序，而排序是件花时间的事情。不需要排序，就省了很多事情。

3. 有了索引，前面提到的要找到在某个单位工作的人，从某个大学毕业的人，都很容易解决，因为再按照工作单位建一个索引，按照毕业的学校建一个索引就可以了。每当遇到新的需求，就建立新的索引好了。

4. 如果做一些复杂的操作，比如要找到清华大学毕业的李强，只要在人名索引中把李强的记录编号找到，再从毕业学校索引中，把清华大学对应人员的记录号找到，重合的号码，就是那些从清华毕业的李强。（据我的合伙人讲，他当学生时，清华有超过10个叫李强的。）

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

首先，Google把在网络上所有能找到的文档（以及图片、视频等等内容）下载以后，会对每一个词建立索引，记录下来每一个词都出现在哪一篇文档（网页）中的哪一些具体的位置。比如“得到”这个词出现在第105个网页的第4、9、37个位置，第403个网页的第9、40、77个位置，第588个网页的第73、203个位置，等等。这样，当一个互联网的用户搜索“得到”这个词的时候，只要在索引中找到这个词，就能通过一个操作，把互联网上所有的包含“得到”的文本找出来了。

网页搜索的这种做法和你在Word中打字时，用Ctrl+F查找是不一样的。在Word中是不会对每一个词建索引的，因此查找时是顺序查找，一个个来，查找完一遍，计算机实际上是把你输入的文章也浏览了一遍。在网页搜索中，因为这个数据量实在太大，全世界大约有1000亿个有意义的网页，即使每个网页平均只有500个词，也是50万亿个词，是不可能用顺序搜索的。在使用Word写作时，一篇文章最多不过几万字，顺序浏览一遍还是可以忍受的。

其次，当你要搜索一组关键词时，比如搜索同时包含，“得到”“方法论”这两个词，如果没有索引，可就麻烦了，即使找到了包含“得到”这个词的网页，还要想办法看看里面是否有“方法论”这个词，这非常花时间。如果有了索引，我们知道“得到”这个词出现在第105、403、588等网页中，类似地，我们还知道“方法论”这个词出现在403、545、1032等网页中，那么只要找到这两个索引的交集，也就是403等等，就可以了，这个操作就简单很多。

如果你要搜索一个长句子，搜索引擎会先把它分割成一个个独立的词，然后根据每一个词的索引，找到这个句子。

最后，需要说的是，Google在建索引时，是对所有的词建索引的，而不仅仅是对于一些重要的词建立索引。因此，Google搜索出来的结果非常全，不会漏掉很多。而大部分其他的搜索引擎，为了节省成本，常常把一些他们认为不重要的词忽略掉，因此用户会发现找到的网页没有Google找到的多。

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

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

1. 为了方便地查找信息，一个简单有效的方法就是根据信息的内容，建立索引。从原理上讲，计算机的索引和图书后面的关键词索引很相似，它们都保存着所要找的信息的位置。如果所要找的信息不止一条，它会保留所有的位置。但是所不同的是，书后面关键词的索引只有一种，而计算机里的索引常常需要根据应用场景建立很多种。

2. 索引有很多好处，不仅带来搜索的效率，而且带来灵活性，对于同一个数据库，可以建立各种索引，以便按照不同门类的信息进行查找。一般索引只会根据一个维度的信息建立，而不会用几个维度的组合信息建立，比如，不会建立“人名＋毕业学校”这样的索引。

3. 善于建索引，不仅是Google搜索引擎查找信息非常快的根本原因，也是保证Google的产品在信息爆炸时代能体现出高质量的原因。事实上在Google内，使用索引几乎成了所有软件开发的标准。今天一些公司做出来的软件产品质量不高，一个很重要的原因是开发者对索引的重要性缺乏认识，思路还停留在小数据时代，以至于很多功能的速度奇慢无比。

4. 从索引你可以看出，为什么计算机需要对里面的一切东西进行编号，因为没有编号，就无从建立索引。

5. 索引这件事，不是我们人平时工作会用到的，因为我们人接触的信息不多。但是，在工作中，把东西整理好，有条不紊，一定是提高效率的好方法。我经常讲烂笔头永远比最好的头脑可靠，其实也是这个道理。我们的头脑就相当于是一个大数据库，里面什么东西都有，你真要找一个东西，其实很困难。在纸上或者笔记本上写下今天要做的事情，做完一项划掉一项，是提高效率很好的办法。

明天我们会通过Vista的案例来说明索引的成本问题，以及为什么商业的成功不能光靠技术。

祝近安