引言

查找，或者说搜索，主要涉及有两个方面，一个是查找的精确度，也就是用户期望值与查找匹配的内容的相似度；第二个个就是查找的效率了，也就是查找的耗时。这里我主要想讨论后者。

《代码之美》Tim Bray在他的‘查找’一文提出，“在提出一个有关搜索问题的过程中，我们可以从两个方面来权衡时间的消耗。第一种消耗在于用户输入关键字点击查询后的等待时间，另外一类耗时则出现在程序员构建该搜索程序的过程中，包含项目管理的时间以及用户等待该程序变得可用的时间。”

首先，整体的设计和框架考虑应该要优先于查找算法、数据库优化等方面。设计先行，这是最基本和核心的原则，一个好的设计，就能减轻服务器很多压力。

譬如像百度贴吧这样一个每天每时每刻都有海量帖子更新的一个大型系统，数据如何存储到数据库，如何进行读取就是一个首先要考虑到的问题。对于数据库设计来说，是考虑实时更新数据呢，还是每天定时更新新增的和被删除的数据，比如每天晚上0点？数据量过于庞大，是否考虑对数据库进行分区设计？如果进行定时处理，那么就先得对那些还没来得及更新在客户端的数据进行缓存处理，那么是直接放入服务器内存中呢，还是写入文件放入磁盘好？ 这些都是应该首先要考虑的问题。

整体考虑完之后，还有哪些地方可以值得优化？这是接下来要认真考虑的问题。上网看了一些帖子，总结可优化的地方如下：

1 数据库设计优化

2 索引文件读取方式的优化

3 查找算法选取和设计的优化

4 sql查找语句的优化

5 客户端代码的优化

数据库设计优化

       我的认知范围里，数据库优化上主要考虑两个方面，一是是否对某个表建立分区，二是是否对表某些字段建立索引,三是使用存储过程。

索引文件读取方式优化

对于文件的读取操作，首先应该看文件大小。

对于大文件，我们可以考虑是否可以通过散列或者其他的方式映射为多个小文件，这样一来为服务器减轻了负担，也提供了多种可选的处理方式，例如并行处理或者单个逐步处理等，或者考虑使用多台机器进行分布式处理。

然后考虑优化文件读取的缓存方式。常规的缓存考虑主要有两种，一种是一次性将所有数据放入缓存中进行处理，另外一种是在缓存中放一部分就取一部分，一批一批处理。那么具体如何选取就看具体实际情况来考虑了。但我们能考虑的是，是否可以对缓存进行分区块或者分片处理，也即将缓存区块单独分割开来分别处理不同的数据读取，也就相当于一个并行处理了，但这些都是与机器硬件条件相关联的。

然后是流类的选择以及数据传输的方式。我们可以考虑字节或者字符方式，或者直接以二进制方式，进行数据读取，数据传输方式一般都对应着程序语言相关联的流类，因此不同程序语言，不同的流处理会有不同的区别。不过主流程序语言对于流类的封装都比较成熟，因此个人认为程序语言对性能的优化方面影响不大，当然，选取哪一种语言实现在整个系统搭建之初便基本已经确立好，也较难更改。

最后值得一提的是，在对文件进行大数据读取操作时，应该每隔一定内容便测试输出一下，例如每隔10000行便打印测试日志，那么我们在进行读取操作时，如果应用程序运行很慢，那么到底是程序进入了无终止的死循环，还是文件过大或者其他线程占用太多CPU资源？测试语句可以确保当出现异常情况时，我们能及时定位问题的所在。

查找算法选取和设计的优化

对于大文件的查找，首要考虑还是散列查找和二分查找算法，也是目前主流的实现方式。

对于散列查找算法我们并不陌生，O(1)的时间复杂度让我们趋之若鹜。但这只是最理想的情况，而现实中这种情况极少出现的，散列查找有不少的限制条件。

散列函数的选取，冲突的处理，内存的限制，映射文件数据量庞大都是实际需要考虑的地方。对于散列函数和冲突，我们知道P值的选取时关键，P值越大，越不容易出现冲突，但同时也造成大量内存空间的浪费，这对于服务器机器内存有限和所操作文件数据量庞大来说，是个不小的矛盾。这里我们可以考虑使用“分而治之”的策略来处理，即将大文件按照一定规则分割成多个小文件单独处理，但这样一来，不同文件就必须进行单独的排序和查找，也会多消耗一定的时间，具体看我们如何权衡利弊了。

因此，对于使用散列查找，我们需要考虑的地方主要有一下几个方面：

1 散列函数的选取

2 冲突处理方式

3 P值的选取

4 大文件分割

5 排序算法

这里列举一个比较典型的大数据查找问题及解决思路：

问题：海量日志数据，提取出某日访问百度次数最多的那个IP。

  思路：首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法， 比如模1000，把整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash_map进行频率统计，然后再找出频率最大 的几个）及相应的频率。然后再在这1000个最大的IP中，找出那个频率最大的IP，即为所求。
    算法思想：分而治之+Hash

1.IP地址最多有2^32=4G种取值情况，所以不能完全加载到内存中处理； 

2.可以考虑采用“分而治之”的思想，按照IP地址的Hash(IP)24值，把海量IP日志分别存储到1024个小文件中。这样，每个小文件最多包含4MB个IP地址； 
    3.对于每一个小文件，可以构建一个IP为key，出现次数为value的Hash map，同时记录当前出现次数最多的那个IP地址；
    4.可以得到1024个小文件中的出现次数最多的IP，再依据常规的排序算法得到总体上出现次数最多的IP；

5. 对于第3步和第4步取得出线次数最多的Ip地址，我们使用经典的堆排序Top K算法，找出Top K，时间复杂度为N*logK。

对于二分查找算法：Tim Bray推崇之至，他的理由如一下几点：

a) 二分查找的时间复杂度为O(log2N)。在一台32位的计算机上，我们所能碰到的最大的log2N就是32，这对于现实世界大多数场景来说，具有如此性能上限的算法已经是‘足够好’了。

b) 二分查找的代码很短，也很简单。因此它更容易被人们理解，对于短小的代码来说，可供问题容身的场所很少。同时，紧凑的代码在指令集，指令缓存以及JIT编译器上都可以获得更好的优化，从而运行的更快。

c) 一旦对数组排序完毕，我们将不再需要额外的索引结构，这方面，二分查找可以节省大量的空间。

    对二分查找算法的推崇，其实有一个更直接的理由。目前对于全文搜索的标准做法基于posting这个概念，posting是个小的、固定大小的记录。在创建索引的过程中，我们读取所有的文档，然后对每个词，我们都为它创建一个posting，用来描述这个词x在文档y中的位置z出现。而由于posting很小而且尺寸固定，同时它们的数目又非常巨大，使用二分查找的做法因而也就显得很自然了。

sql查找语句的优化

数据库对海量数据进行查询，我们主要考虑的是尽量避免进行全表查询。具体到SQL语句上来说，一篇文章对此进行了详细的阐述，具体如下：

来源网页地址：http://blog.fufuok.com/Article/507.aspx

    1.对查询进行优化，应尽量避免全表扫描，首先应考虑在 where 及 order by 涉及的列上建立索引。

2.应尽量避免在 where 子句中对字段进行 null 值判断，否则将导致引擎放弃使用索引而进行全表扫描，如：
select id from t where num is null
可以在num上设置默认值0，确保表中num列没有null值，然后这样查询：
select id from t where num=0

3.应尽量避免在 where 子句中使用!=或<>操作符，否则将引擎放弃使用索引而进行全表扫描。

4.应尽量避免在 where 子句中使用or 来连接条件，否则将导致引擎放弃使用索引而进行全表扫描，如：
select id from t where num=10 or num=20
可以这样查询：
select id from t where num=10
union all
select id from t where num=20

5.in 和 not in 也要慎用，否则会导致全表扫描，如：
select id from t where num in(1,2,3)
对于连续的数值，能用 between 就不要用 in 了：
select id from t where num between 1 and 3

6.下面的查询也将导致全表扫描：
select id from t where name like '�c%'
若要提高效率，可以考虑全文检索。

7. 如果在 where 子句中使用参数，也会导致全表扫描。因为SQL只有在运行时才会解析局部变量，但优化程序不能将访问计划的选择推迟到运行时；它必须在编译时进行选择。然 而，如果在编译时建立访问计划，变量的值还是未知的，因而无法作为索引选择的输入项。如下面语句将进行全表扫描：
select id from t where num=@num
可以改为强制查询使用索引：
select id from t with(index(索引名)) where num=@num

8.应尽量避免在 where 子句中对字段进行表达式操作，这将导致引擎放弃使用索引而进行全表扫描。如：
select id from t where num/2=100
应改为:
select id from t where num=100*2

9.应尽量避免在where子句中对字段进行函数操作，这将导致引擎放弃使用索引而进行全表扫描。如：
select id from t where substring(name,1,3)='abc'--name以abc开头的id
select id from t where datediff(day,createdate,'2005-11-30')=0--‘2005-11-30’生成的id
应改为:
select id from t where name like 'abc%'
select id from t where createdate>='2005-11-30' and createdate<'2005-12-1'

10.不要在 where 子句中的“=”左边进行函数、算术运算或其他表达式运算，否则系统将可能无法正确使用索引。

（此处只列出部分，查看全文请去本文源地址）

问题处理示例

       在网上看到有人发帖提出以下问题：

问题描述：

数据库DB 【表A】是存放过滤关键词的表，字段 id,wd,count。目前有记录1万。

数据库DB 【表B】是存分类谷歌信息的表，字段 tid,title,content。目前有记录10万。

有一个自检功能，程序自动的获取A表的字段wd后，将统计到的表B字段content匹配的个数存放到表A的字段count中。

提问者自我解决方式：

$queryA = DB::query("SELECT * FROM A LIMIT 100 ");

while($rowA = DB::fetch($queryA))

{

  $id = $rowA['id'];

  $wd = $rowA['wd'];

  $count = DB::result_first("SELECT COUNT(*) FROM B WHERE `content` LIKE '%$wd%' ");

  DB::query("UPDATE A SET `count`='$count' WHERE id='$id' ");

}

回帖中的质疑和解决方案：

1 你这自检程序就只能增加数据库的压力；一但数据量上来了，后果将会很严重。

2  like是全文检索啊，快不了。

3 你的自检程序可以定时运行，比如每天晚上0点运行；统计前一天的数据的增加，删除情况，然后更新数量。这样比你一次like数10万的数据要快很多。

4一个贴吧 一个独立处理单元（可以分目录，分表,分端口，分服务器...etc）

不要老想去索引。。散列原理才靠普。

凡是巨量的数据，都必须散列...

不要指望银河计算多么多么给力,给力也是分布式运算。。还是散列原理..

优良的代码不如优良的架构.

5方案1。对回复 建立索引 索引中一个字段就是用户名 查询这个字段即可

方案2。数据冗余 有专门的用户表存储用户的回复 也有地方存储帖子。数据按照用户id hash 分表分库

       6不同的查找方式，采用不同的存储方法，比如：

a)按照用户查找，最快的当然是根据用户id建立发表帖子的映射（hash或map等），同一用户下的不同的帖子可以再根据一些属性建立分类或索引。

b)按照关键词查找，建立倒排索引，搜索引擎就是这么干的，贴吧数据量比搜索引擎小吧？！

       7 分布式，数据切分（比如根据userid切分或者username切分），数据库表里面对查询字段加索引。

总结

       最后我需要说明的是，这里只是对大数据查找提供一些可选的思路，但对于具体到每一个细节如何处理和解决，没有实践过也没有多少经验，这也是我下一步需要做的事情。