一个数据库文件 ---------  多个 B-trees
一个 B-tree          ---------  一个table or index
一个 B-tree          ---------  多个pages( 一个page默认大小1024Btyes )
一个 B-tree          ---------  在root page 中有一个id
一个 B-tree 每行  ---------  一个 RowID 即 表的 key

rowid 按顺序储存

SELECT y FROM ex1 WHERE x= "dddd" 如何没有索引表，则时间复杂度：
为 O(n); 依次序要查找，即线性查找，如果查找RowId ,则时间复杂度: O(logN);


语句SELECT y FROM ex1 WHERE x="dddd":
在索引表中带有 rowid , 利用索引表查找的时间复杂度: O(logN)
利用二分法查找！

 优化:
 SELECT * FROM t1, t2 WHERE t1.rowid=t2.a;

 伪代码：复杂度O(n*n)
  for each row in t1:
     for each row in t2:
       if (t1.rowid = t2.a) continue
       output one row of result
     end
  end

SELECT * FROM t2, t1 WHERE t1.rowid=t2.a;

伪代码：复杂度O(n*logN)
for each row in t2:
     lookup the row in t1 where t1.rowid=t2.a
     output one row of result
end

同效果不同的语句可能产生不一样的速度，所以商用数据库的底层优化工作很重要
取决于执行伪代码(汇编代码)