Database Reference
In-Depth Information
x0
x1
x2
x3
x4
x5
x6
x7
T2
y0
T1
R7
y1
L1
R1
y2
R6
L4
y3
L3
y4
R3
y5
R5
y6
R2
R4
y7
L2
(a) Rectilinear bounded regions
T1
T2
L1
L2
L3
L4
R1
R2
R3
R4
R5
R6
R7
(b) R-tree representation
Figure 6.10
R-Tree indexing of bounded rectilinear 2D dataset.
Figure 6.10a shows a collection of points grouped into rectangular boxes of at
most three points per box and indexed by an R-Tree.
Like the
B
+
-Tree, an R-Tree specifies the maximum number of entries
B
,
that can be contained in a node and satisfies the following properties:
1. A leaf node contains between
B
/
2 and
B
entries unless it is the root
node.
2. For an entry
in a leaf node,
R
is the minimum rectilinear
bounding box of the object
RI D
.
3. An internal node contains between
B
RI D
,
R
/
2 and
B
entries unless it is the
root node.
4. For an entry
in an internal node,
R
is the minimum rectilinear
bounding box that encloses the MBRs in the node pointed to by
ptr
.
5. A root node can contain at least two children unless it is a leaf node.
6. All leaf nodes appear at the same level.
ptr
,
R
