Editing R-tree (section)

=== Search ===

The search process in an R-tree embodies a two-phase approach that aligns with the [[Filter and refine| Filter and Refine Principle (FRP)]]. In this structure, the internal nodes serve as an initial filter by quickly excluding regions of space that do not intersect the query, while the leaf nodes provide a refined, precise evaluation by storing the actual spatial objects.

Specifically, in [[range searching]], the input is a search rectangle (Query box). Searching is quite similar to searching in a [[B+ tree]]. The search starts from the root node of the tree. Every internal node contains a set of rectangles and pointers to the corresponding child node and every leaf node contains the rectangles of spatial objects (the pointer to some spatial object can be there). For every rectangle in a node, it has to be decided if it overlaps the search rectangle or not. If yes, the corresponding child node has to be searched also. Searching is done like this in a recursive manner until all overlapping nodes have been traversed. When a leaf node is reached, the contained bounding boxes (rectangles) are tested against the search rectangle and their objects (if there are any) are put into the result set if they lie within the search rectangle.

For priority search such as [[nearest neighbor search]], the query consists of a point or rectangle. The root node is inserted into the priority queue. Until the queue is empty or the desired number of results have been returned the search continues by processing the nearest entry in the queue. Tree nodes are expanded and their children reinserted. Leaf entries are returned when encountered in the queue.<ref>{{Cite conference | doi = 10.1109/ICICS.1997.652114| chapter = Fast k nearest neighbour search for R-tree family| title = Proceedings of ICICS, 1997 International Conference on Information, Communications and Signal Processing. Theme: Trends in Information Systems Engineering and Wireless Multimedia Communications (Cat. No.97TH8237)| pages = 924| year = 1997| last1 = Kuan | first1 = J.| last2 = Lewis | first2 = P.| isbn = 0-7803-3676-3}}</ref> This approach can be used with various distance metrics, including [[great-circle distance]] for geographic data.<ref name=geodetic/>