[prev] 23 [next]

R-Trees

R-trees use a flexible, overlapping partitioning of tuple space.
  • each node in the tree represents a kd hypercube
  • its children represent (possibly overlapping) subregions
  • the child regions do not need to cover the entire parent region
Overlap and partial cover means:
  • can optimize space partitioning wrt data distribution
  • so that there are similar numbers of points in each region
Aim: height-balanced, partly-full index pages   (cf. B-tree)