KEMBAR78
R Tree | PDF | Database Index | Computer Programming
Scribd
Upload
118 views11 pages

R Tree

- R-trees are an indexing structure that extends B-trees to multiple dimensions, allowing efficient querying of multidimensional data. - They were invented by Antonin Guttman in 1984 to organize points and rectangles in spatial databases. - In an R-tree, data objects are grouped into minimum bounding rectangles which are then organized into a tree structure similar to a B-tree, enabling efficient range and k-nearest neighbor queries on the multidimensional data.

Uploaded by

ddro
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
118 views11 pages

R Tree

- R-trees are an indexing structure that extends B-trees to multiple dimensions, allowing efficient querying of multidimensional data. - They were invented by Antonin Guttman in 1984 to organize points and rectangles in spatial databases. - In an R-tree, data objects are grouped into minimum bounding rectangles which are then organized into a tree structure similar to a B-tree, enabling efficient range and k-nearest neighbor queries on the multidimensional data.

Uploaded by

ddro
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 11

Introduction to R-trees

Many real-life applications require the organization and


management of multidimensional data (e.g., each
image is represented as a point in the 5-dimensional
space).
To enable efficient query processing, data should be
organized by means of an indexing scheme which is
used to speed-up processing.
The index helps in reducing the number of inspected
objects significantly, avoiding the sequential scan of
the whole database.
Indexing schemes for multidimensional data work in a
similar manner to access methods for simple numeric
data (e.g., B-trees and Hashing).
48

Introduction to R-trees
One of the most important contributions
in the area of multidimensional
indexing is due to Antonin Guttman
which invented the R-tree.

His work:
R-trees: a dynamic index structure for spatial searching,
ACM SIGMOD Conference 1984
has received more than 2,900 citations
(source google scholar)
49

Introduction to R-trees
The R-tree can be viewed as an extension of the B+-tree to handle
multiple dimensions. Recall that, a B+-tree is used to organize
numeric data in one dimension only.
Each node
corresponds
to a disk page

B+ tree example with 6 nodes:


root
8

leaf 1

14 16

leaf 2

17

24

19 20 22

leaf 3

30

24 27 29

leaf 4

33 34 38 39

leaf 5
50

Introduction to R-trees
R-trees have been extensively used in spatial
databases to organize points and rectangles.
They show excellent performance in processing
interesting queries such as:
Range query: return the points that are contained
in a specified region.
K-nearest-neighbor: given a point p and an integer
k return the k objects closer to p.
51

Introduction to R-trees

range query example:


which cities are within distance R from Amsterdam

k-NN query example:


Find the 3 cities closer to Utrecht (k = 3)
52

Introduction to R-trees
y axis
10

Example:
13 points in
2 dimensions

m
g

8
6

e f
i
d

region of interest

b
2

x axis
0

10

Range query example: find the objects in a given region.


E.g. find all hotels in Utrecht.
No index: scan through all objects. NOT EFFICIENT!
53

Introduction to R-trees structure


y axis
10

m
g

8
6

E3

b
2

Minimum Bounding Rectangle (MBR)

Each node
corresponds
to a disk page

x axis
0

10

Root
E
1
E
1
a
E
3

E
3

E
4

d
E
4

E
2

E
5

E
6

f
E
5

E
7
i

h
E
6

E
2
j

k
E
7

m
54

Introduction to R-trees structure


y axis
10

E7

m
g

8
6

E5

E4

E6

E3

b
2

x axis
0

E
1
E
1
a
E
3

E
3

E
4

d
E
4

10

Root

E
2

E
5

E
6

f
E
5

E
7
i

h
E
6

E
2
j

k
E
7

m
55

Introduction to R-trees structure


y axis
10

m
g

E7

E5
f

E4
4

E3

E2

E1

b
2

E6
i

x axis
0

10

Root
E
1
E
1
a
E
3

E
3

E
4

d
E
4

E
2

E
5

E
6

f
E
5

E
7
i

h
E
6

E
2
j

k
E
7

m
56

Introduction to R-trees range query


y axis
10

m
g

E7

E5

E4
b

E3

E2

E1

E6

e f

x axis
0

E1
a
E3

E3

E4

d
E4

Root
E1

E2

10

E5

E6

f
E5

E7
i

h
E6

E2
j

k
E7

m
57

Introduction to R-trees range query


y axis
10

m
g

E7

E5
e f

E4
b
2

E3

E2

E1

E6
i

x axis
0

E1
a
E3

E3

E4

d
E4

Root
E1

E2

10

E5

E6

f
E5

E7
i

h
E6

E2
j

k
E7

m
58

You might also like