有关SQL时间复杂度的问题，请指教。

怎么估算出每个SQL语句的时间复杂度呢？例如，有两个表 t1, t2， t1里有 100W数据，t2 里有20W数据，两者必须通过关键字 id来查询，能否估算出这个语句的时间复杂度呢？？？select t1.*, t2.name
from t1, t2
where t1.id = t2.id

解决方案 »

  1.   

    1、先用规划器看一下扫描的行数。
    2、运行时间可以加上 where 0.忘了怎么算时间复杂度了。
      

  2.   

    时间复杂度Ot = Nt1 * Nt2 如果没有索引    [align=center]==== 思想重于技巧 ====
    [/align]
      

  3.   

    时间复杂度如果有索引
    Ot = Nt2 * Log2(Nt1), 如果考虑mySQL的索引具体方式，理论上会更小一些，但只是估算用这个就行了。    [align=center]==== 思想重于技巧 ====
    [/align]
      

  4.   

    Ot = Nt1 * Nt2 如果没有索引 
    这个是你需要对两个表进行全表扫描，相当于进行了两个欠套循环，所以是*如果有索引
    Ot = Nt2 * Log2(Nt1),
    是对第一个表进行扫描，使用索引，一般索引都是树结构，时间复杂度就是log2(nt1),整体的就是Nt2 * Log2(Nt1)
    如果在不明白，去找本数据结构的书看看怎么计算时间复杂度。