如果你一定要这样子...那也必须把数据做一定的处理，把信息提炼出来。 比如我之前说的。做一次排序，以后就可以根据"数列有序"这个信息，以少于数据集数目的访问量，拿到某个第n大小的值。 google的搜索引擎也是如此，首先对internet做一次全部的扫描，扫描之后做index。随后的搜索关键字只是在index范围内查询，因此可以做到在0.2秒内对整个internet做一次搜索。
直接搜索肯定是不行的啦，你说整个internet的网页信息有多少数据量... 我们做个夸张的假设吧，假设整个internet的网页信息，用200G硬盘就能存下。 那么每次查询只要检索200G数据就行了。这个又要多少时间呢？ 按照服务器级硬盘IO约是100MB/s的速度，大约是2000秒。 光把这么多数据读取一遍，就要近40分钟的时间。
啥算法？你是指google的索引算法么？ 我不确切的知道google的算法，但是我可以给出一种类似的算法。 本质上，搜索就是对文档的关键字做索引。因此首先需要知道什么叫关键字。 这方面英文比较简单，因为单词都用空格分开了。中文比较麻烦，需要做分词。分词的准确率直接关系到检索率。分词这一节我就不展开讲了，基本还是一样，运用贝叶斯网络做的。 分词以后，一篇文档就变成许多关键字了。比如我这篇帖子，“比如”出现了a次，"算法"出现了b次，“分词”出现了c次等等...一篇很长的文章经过分词之后，会被压缩许多。 因此下一步就是做一个映射，让这些词指向这篇文章。 依次类推，对每个网页都做这样的映射处理，就得到两个大集合，左边是一系列关键字，右边是一系列网页。下面就是搜索问题。 所谓搜索，就是你输入几个关键字，然后从左边的关键字集合中，把这几个关键字指向的文档集合找出来。至于关键字的数据结构和保存方法，一般用hash表，或者红黑树。anyway，适用的算法很多，google用的可能是红黑树，还是分布式的。据我所知google的索引内容是全部存放在内存中的。 以上只是把信息检索出来，并不能保证检索出来的是有效的东西。如何判断检索出来的是用户所需要的，有效的东西，又可以展开讲一篇了...
google对结果的排序和过滤，可是可以专门写篇很长的文章的...综合运用了许多许多的方法... 我现在说的只是google的实现手段，框架模式，连数据结构都没有给出呢... 但是数据库其实真没啥，昨天回这个帖子的时候老婆催我睡觉了，只能草草写两行... 今天可以简单展开说说数据库。 数据库源于大量的对数据处理需求。由于上个世纪大部分业务中，对数据的组织和处理都是类似的。因此就有了数据库这个东西来专门做数据的管理和检索，其地位类似于操作系统，属于一个支撑平台。 数据库的理论，一直发展到关系数据库才较为成熟。关系数据库的数理基础，是集合论。集合这个东西在计算机科学里面有相当重要的地位，可以说是计算机科学的基石。所以关系数据库，在理论上跟集合论扯上了关系，大家就比较的喜欢，再加上关系数据库的基于表，以及表之间的关系这种模式，也比较符合当时大多数应用的模式（主要是银行等大型应用）。所以关系数据库就流行起来，最终成为现在的数据库样子。在这个过程中也发展出许多标准的语言和模型，比如ER模型和SQL查询语法等等。也形成了一个庞大的产业链，比如oracle买套最小配置的也要10W左右...还需要雇佣专门的DBA去设计，管理等等。 在我眼里，数据库就意味着没有必要的麻烦事。其实关系数据库这个东西，在现代已经越来越力不从心了，尤其是在web2.0时代。传统的业务模型，是中央发布式。比如广播，报纸，早期的网站。都是单一信息源，大量的用户只是听众被动接收。到了现在web2.0时代，这种模式已经消亡了，跟多的进入人与人交互，互动的时代。这个时代个人，每个人都是信息的发布者。比如twitter，facebook等。在这个时代，传统的关系数据库已经落伍了，难以支撑现在各种新的应用。 比如难以支撑上亿的并发访问，难以扩展，难以实现无停机迁移维护等等。并且关系数据库的强项，现在也没啥太大的用处，比如事务一致性，数据实时性等。比如我发的贴后面有看过的人的计数，这个计数没必要是实时的，每分钟更新一次也完全可以接受等等。 所以其实现在已经发起了NoSQL运动，提倡不再使用关系数据库。典型的就是twitter要转用Cassandra。不过最新的消息是失败了，还是回到了MySQL上。不过我认为主要是因为cassandra不够成熟稳定，毕竟新生事物嘛。 说了这么多，再回到google的搜索引擎上来。我认为google的搜索引擎肯定是基于自己设计的数据结构做的。但具体要讨论的话，这个帖子就要写很长了....当初我面google的时候，面我的人就让我做过这个事情，首先让我设计数据结构，做一个支撑500个页面的搜索引擎。然后把500提到5000，再提到5W，....一直到5亿...在这个过程中，每上升一个数量级，就会面临许多新的挑战。他就观察我这个过程中思维的变化，折腾了我整整两个半小时才算满意而归...说两个小时的内容如果是发帖的话...你能不能饶了我......
非常感谢！数据库我打个比方，是广义的那种意思。 对于快速检索，可以有一大堆算法实现，找到合适的。 而google根据关键搜索词，一下子出现的有多少个符合的信息，那个东西是怎么出来的呢？而且还那么快？hash的并发搜索？那也不应该那么快啊～～如果真是那样，也就没什么意义了。跟我的问题不太一样。 所以还是回来，有什么算法可以实现不遍历所有像素点就找出搜有的解呢？ 比如说，100*100的图，有5000像素点完全相同，他能够搜索8000甚至6000甚至5500，5000是不敢奢望了，就能确认所有的相同的点都搜索了。
google的搜索方式可能和你问的不一样。并行的。google对于一个搜索请求可以分布到很多台服务器上同时进行，比如每个节点负责搜索100万个页面的索引，这些结果最后合并之后返回给用户。 google的系统里面有多少节点，你去搜一下就知道个大概，非常多。
识别出2个完全相同的图像比较容易和快速，所以在识别2个图像时（如果有局部不同），采用分割的方法可能可以加快整体的识别速度。2图像分割成一系列图像（框选），完全相同部分会被快速识别出来，不同部分保留下来继续分割（当然没比较无限分割下去）比较，达到一定规模后就不用分割来识别了，这样识别出2图像不同点应该比遍历所有像素点要快。 判断完全相同的图像应该有快速识别算法的，不需要采用遍历像素的方法。 而且采用分割的方法也方便并行处理。
你这个图搜索的例子，很难做到你的要求。我考虑了一会儿没想出啥办法。 有个方法可以降低一点搜索量。但是并不是100%可行的。 本质上，100*100=10000个点，如果你想不遍历10000个点就确切的找出相同的点，必须把10000个点的信息压缩到一个更小的空间。考虑到跟LCS算法结合的方便性，对输入图像可以先用游程编码处理下。 这样，两张10000个点的图，占用的空间会小许多（小多少取决于图片的复杂度），然后再对游程编码之后的图像运行LCS算法，就能大大提高算法的运行速度。 但是，做游程编码的过程，一样是需要遍历10000个点的。这样做，只不过可以把算法分成了两部分，而两部分算法总计算量之和，是大于直接运用LCS算法的。但是这样的话，第一部分的时间可以放到后台去完成，从而提高第二部分搜索的响应速度。 google的响应这么快也是类似原理。google后台有无数爬虫下载internet上的信息，并处理之后放到自己的表中，形成一个对internet的快照。这个过程是相当缓慢的。 所谓的搜索，只是对表中，已经下载并组织好的信息进行搜索。并不是直接对internet的搜索。 做到快速检索并不困难，首先，hash算法是O(1)算法，受规模增长的影响并不是很大。其次，所有的key都在内存里面，而现在的内存带宽是很夸张的，比如把4G内存遍历一边，按照20G/s的速度，只需要0.2秒左右的时间。Google有上万台这样的机器，通过并发搜索，的确可以在零点几秒内完成全局的搜索。按照我的假设，就是10000×4G=40T的存储空间，在0.2秒内遍历完毕。之前的假设是200G存下整个internet的内容，显然是不可能的。但是用40T来存下整个Internet内容的关键字，则完全可能。 说到这里，总算是可以让一次查询在0.2秒内得到满足。但是对于google每秒同时有上千万级别的查询，如何满足每笔都在0.2秒内完成，这就又是个问题了...... 其实这个问题也不复杂。之前用hash表支持一次查询。hash表的本质，是把一次查询集中在某个狭小的数据空间内，从而大大提高查询速度。但是当每秒有上千万次查询的时候，hash表是完全没用的。因为无论怎么分散，上千万次查询，就像是密集的暴雨一样，还是会把整个key空间覆盖满。此时再使用hash表就没有意义了。 这种情况下，吞吐量最大的算法，反而是最简单的方法：顺序扫描法。把整个key空间从头扫描到尾部，再返回从头扫描到尾部，如此不断进行。在扫描过程中会不断有新的查询请求进入，旧的查询请求命中并移出。这样每次查询请求最长会在一个扫描周期内得到满足。而这个扫描周期就是我之前说的，一台机器扫描4G内存的时间，也就是0.2秒。 当然以上只是大概的模型，组建一个实际的，高可靠性的系统，还有许多意外情况需要考虑。不过总体上应该是这个思路。