近日一个朋友发过来一个页面, 说是上面有一段代码执行慢, 想看看能不能用一些方法让这个等待过程不要这么久, 看了一下代码, 朋友所指的代码大概像下面一段:

[php]if (cond)

{

$query = “select id, name from demoTable where age >= “ . $age . “ and score >= “. $score . “ “;

$result = mysql_query($query);
list( $id,$name) = mysql_fetch_row($result);
print &quot;<td class="text">&quot;.$id.&quot;</td>
print &quot;<td class="text">;&quot;.$name.&quot;</td>;

}[/php]

另外的信息是, 数据库的记录大概是三十多万条, 由于这个查询语句要在一个循环语句里执行多次, 当循环十次的时候速度会很明显的很慢.

据俺已有的知识和对mysql的理解, 对于十万量级的记录, 数据库的效率应该没有问题, 首先想到的便是从优化数据库开始, 第一条当然是建立索引了, 于是建议他用age + score做一个索引, 但朋友讲做过索引后没有太大影响(我怀疑他是单独为age 和 score做了索引, 我的意思是为age/score做一个综合索引, 但后面这个就没机会尝试了). 于是再尝试一些新的方法, 回过头去分析这段代码, 可以发现, 这里只是用到了返回结果集的第一条记录(或者原来的作者只期望得到一条记录), 毫无疑问, 把所有的记录查询下来是很破费时间/内存的, 于是从这里入手, 我们把查询改成只查一条记录.

于是修改后的查询语句就是

$query = “select id, name from demoTable where age >= “ . $age . “ and score >= “. $score . “  LIMIT 1“;

让朋友尝试新的代码, 果然速度提升了很多, 基本不用再做其他的优化了. 那我们分析一下加上LIMIT 1之后相对能优化了多少次的查询, 这里我们假设每条记录被查询到的机率相同(不然还要再具体分析就太麻烦了…)

1. 假设没有索引, 那么对于原始查询, 基本是遍历整个表, 时间复杂度为O(n), 而对于优化后的查询来讲, 它会找到第一条匹配的记录后返回, 平均时间复杂度为(1 + n) / 2, 相当于优化了一半的时间.

2. 假设分别建立了age和score的索引, 对于原始的查询, 平均时间复杂度(二分法)应该大致在log2(n) + (log2(n/2) 左右, 这个需要根据具体的查询来分析, 不过这个值应该也算差不多, 而对于优化后的查询时间复杂度大致为 log2(n) + log2(n/2) = 2 log2(n) – 1, 貌似并没有优化掉多少时间 (是不是这里错了???? )…….

至于空间复杂度, 如果对于每次查询只可能有一条记录满足条件, 则都为O(1), 如果是有可能有多匹配记录, 当然对于优化后的查询会好很多.