Editing R+ tree (section)

==Difference between R+ trees and R trees==
R+ trees are a compromise between [[R-tree]]s and [[K-d tree|kd-trees]]: they avoid overlapping of internal nodes by inserting an object into multiple leaves if necessary. '''Coverage''' is the entire area to cover all related rectangles. '''Overlap''' is the entire area which is contained in two or more nodes.<ref>{{cite book|last=Härder, Rahm|first=Theo, Erhard|title=Datenbanksysteme.|year=2007|publisher=Gardners Books|location=Berlin [etc.]|isbn=978-3-540-42133-7|pages=285, 286|edition=2., überarb. Aufl.}}</ref> Minimal coverage reduces the amount of "dead space" (empty area) which is covered by the nodes of the R-tree. Minimal overlap reduces the set of search paths to the leaves (even more critical for the access time than minimal coverage). Efficient search requires minimal coverage and overlap.

R+ trees differ from R trees in that: nodes are not guaranteed to be at least half filled, the entries of any internal node do not overlap, and an object ID may be stored in more than one leaf node.