concept r - tree in category algorithms
This is an excerpt from Manning's book Algorithms and Data Structures in Action MEAP V14.
Retrieving the `N` closest points to a target point (not necessarily in the container).
10.2.2 From B-Tree to R-tree
R-trees extends the main ideas behind B+ trees to the multidimensional case: while for unidimensional data each node corresponds to an interval (the range from the left-most and right-most keys in its sub-tree, which are in turn its minimum and maximum keys), in R-trees each node N covers a rectangle (or better a hyper-rectangle in the most generic case) whose corners are defined by the minimum and maximum of each coordinate, over all the points in the subtree rooted at N.
Similarly to B-trees, R-trees are also parametric: instead of a branching factor d controlling the minimum number of entries per node, R-trees requires their client to provide two parameters on creation:
Figure 10.4 The tree representation for the R-tree of figure 10.3. The parameters for this R-tree are m==1 and M==3. Internal nodes only hold bounding boxes, while leaves hold the actual points (or, in general, k-dimensional entries). In the rest of the chapter we will use a more compact representation, for each node drawing just the list of its children.
