Transcript Chapter 5 R
R-Trees
Index Structures for Spatial Data
Outlines
Spatial Applications
Requirements for indexing spatial data
Properties of R-trees
Insertion
Deletion
2
R-Trees: Index Structures for Spartial Data
2301474
Spatial Applications
Maps
3
Google Earth
Navigation Systems
Computer Aided Design
Automobile design
Interior design
Computer Graphics
R-Trees: Index Structures for Spartial Data
2301474
Requirements for Indexing Spatial Data
Support both point and region data.
Support data in 2-, 3-, 4-dimensional spaces.
Support spatial queries such as overlap, adjacent,
in, contain, to the north of, …
4
R-Trees: Index Structures for Spartial Data
2301474
Concepts of R-Trees
5
The minimum bounding
rectangle (MBR) of an object is
the smallest box in the ndimensional space bounding
the object.
In an n-dimensional space, the
index of a set of spatial objects
is an n-dimensional box
bounding the set of objects.
Bounding boxes are used as
indices in R-trees.
Similar to B+ trees, but indices
are allowed to be overlapped.
R-Trees: Index Structures for Spartial Data
2301474
Properties of R-Trees
An index record is composed of
6
R
Q
P
S
Each node contains at most M
index records.
a bounding rectangle B, and
a pointer to a child node or a
pointer to a data record.
Non-root nodes contain between
M/2 and M index records.
The root node contains at least 2
index records.
Q
R S
R-trees are height-balanced.
R-Trees: Index Structures for Spartial Data
P
2301474
Example
A
H
C
D
I
J
A
B
E
K
D
L
P
Q
J
R
E
L
M
I
Q
P
F
7
N
K
H
C
M
G
F
N
R
G
R-Trees: Index Structures for Spartial Data
B
2301474
Query I
A
H
C
D
I
J
A
B
E
K
D
L
P
Q
J
R
E
L
M
I
Q
P
F
8
N
K
H
C
M
G
F
N
R
G
R-Trees: Index Structures for Spartial Data
B
2301474
Query II
A
H
C
D
I
J
A
B
E
K
D
L
P
Q
J
R
E
L
M
I
Q
P
F
9
N
K
H
C
M
G
F
N
R
G
R-Trees: Index Structures for Spartial Data
B
2301474
Insertion
Choose a leaf node L to insert
the new record E.
IF there is a room in L:
10
Different criteria for choosing
the node.
1
THEN insert E in L.
ELSE split L into L and L’, with
records in L and E.
4
2
3
5
4
5
Add the index of L’ in the
parent of L.
R-Trees: Index Structures for Spartial Data
2301474
Insertion
1
11
2
3
4
5
4
5
R-Trees: Index Structures for Spartial Data
2301474
Insert without Split
A
H
C
D
I
J
A
B
E
K
D
L
P
Q
J
R
E
L
M
I
Q
P
F
12
N
K
H
C
M
G
F
N
R
G
R-Trees: Index Structures for Spartial Data
B
2301474
Insert with Split
A
C
H
I
D
J
A
B
E
L
K
D
M
J
N
Q
P
L
X
R
E
Y
M
I
Q
P
F
13
Y
K
H
C
X
G
F
N
R
G
R-Trees: Index Structures for Spartial Data
B
2301474
Splitting a Node
Splitting can be propagated up the tree.
If the root node is split, a new root node is created.
14
R-Trees: Index Structures for Spartial Data
2301474
Splitting
A
C
D
E
L
15
B
M
X
G
F
Y
N
R-Trees: Index Structures for Spartial Data
P
Q
R
2301474
Splitting
A
C
E’
D
L
16
B
X
E
M
G
F
Y
N
R-Trees: Index Structures for Spartial Data
P
Q
R
2301474
Splitting
A
C
E’
D
L
17
B
X
E
M
G
F
Y
N
R-Trees: Index Structures for Spartial Data
P
Q
R
2301474
Splitting
A
C
E’
D
L
18
B’
B
X
E
M
G
F
Y
N
R-Trees: Index Structures for Spartial Data
P
Q
R
2301474
Deletion
Find the leaf node L containing the record E to be
deleted.
Remove E from L.
Set Q = {}.
WHILE (E is not the root and has < m elements)
Remove the pointer to E from its parent node.
Adjust the bounding rectangle of the parent of E.
Set Q = Q U {E}, E=parent of E.
For each node N in Q
19
Re-insert all elements in N in the correct level.
R-Trees: Index Structures for Spartial Data
2301474
How to split
20
R-Trees: Index Structures for Spartial Data
2301474
Variations of R-trees
21
R-Trees: Index Structures for Spartial Data
2301474