| Nested loop for all tuple f є F for all tuple r є R if overlap(F.Geom, R.Geom) then add If F needs M pages with pf tuples in each page, and R needs N pages with pr tuples in each of them, the computational cost is prohibitive. If we consider B buffers in memory, one can transfer B-2 pages from F, leave one buffer for R, and one for the results of An alternative is to use each tuple in F as a window query over an indexed R Tree matching: Both tables are indexed SJ(R1,R2: nodes) forall er2 in R2 { forall er1 in R1 { if overlap(er1.rect, er2.rect) then { if R1 and R2 are leaf pages then output(er1.oid,er2.oid) elseif R1 is leaf page then ReadPage(er2.ptr); SJ(er1.ptr.er2.ptr) else if R2 is leaf page then ReadPage(er1.ptr); SJ(er1.ptr.er2.ptr) else { ReadPage(er1.ptr), ReadPage(er2.ptr) SJ(er1.ptr,er2.ptr) } } } }
|
Última modificación: Thursday, 24 de November de 2005, 15:04