一个数据库文件 --------- 多个 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
同效果不同的语句可能产生不一样的速度，所以商用数据库的底层优化工作很重要
取决于执行伪代码(汇编代码)