[prev] 11 [next]

Multi-dimensional Tree Indexes

Over the last 20 years, from a range of problem areas
  • different multi-d tree index schemes have been proposed
  • varying primarily in how they partition tuple-space

Consider three popular schemes:   kd-trees, Quad-trees, R-trees.

Example data for multi-d trees is based on the following relation: 

create table Rel (
    X char(1) check (X between 'a' and 'z'),
    Y integer check (Y between 0 and 9)
);