基于索引的算法 - zzyoga/JustTest GitHub Wiki

基于索引的算法广泛用于连接操作和选择操作等等。

对于选择操作来说，如果没有索引，我们需要吧整个表读入到内存当中，依序处理每个元组判断是不是符合条件。但是如果有索引的话，比如说我们给带检查表的属性A上建立一个索引，那么在进行选择操作的时候，我们就吧这个A的索引读入到缓冲区快速检索。

聚簇索引和非聚簇索引的使用效率是不一样的。如何通过索引来判断范围性的条件？

例如：假设B(R）=1000,T(R)=20000，即：R有20000个元组存放在1000个块中。a是R的一个属性，在a上有一个索引，并且考虑a=0的选择操作。

1）如果R是聚簇的，且不使用索引，查询代价1000个IO。

2）如果R不是聚簇的，且不使用索引，查询代价20000个IO。

3）如果R在a上不同的值有100个，而且索引是聚簇的，查询代价1000/100=10个IO（只读a=0的那些数据）。

4）如果R在a上不同的值有100个，而且索引是非聚簇的，查询代价20000/100=200个IO。

基于有序索引的连接算法：R.Y=S.Y（Zig-Zag算法）

R和S都在Y属性上有B+Tree索引，R和S均从左到右读取索引树的叶子节点。

（1）读R的第一个索引项赋予a，再读S的第一个索引项赋予b； （2）如果a不等于b则 （21）如果a<b，则将R的下一个索引项赋予a，继续执行2 （22）如果a>b，则将S的下一个索引项赋予a，继续执行2 （3）如果a=b，则将R和S关系中对应的元组读出并进行连接操作，直到R的所有相等的a值和S的所有相等的b值对应的元组都处理完毕；将R的下一个索引项赋予a，继续执行（2）。