R-tree

R-tree (Rectangle tree)

• 각 노드가 최소 50%이상 사용되도록 하는 트리
• insert와 split이 수월하다
• query수행 시 MBR을 사용한다.
• DISK 기반의 TREE임 (A multi-way external memory tree)
• 현재 가장 많이 사용하는 TREE
• HEIGHT(level)이 균일하므로 DISK I/0가 균일하게 발생함
• 하나의 노드는 최소 m개의 entry가, 최대 M개의 entry를 가지도록 제한됨
• 단, root 노드는 최소 2개의 entry(children)를 가질 수 있음(한개도 괜찮음)

m과 M에 대한 예시

** mbr의 grouping의 결과를 tree 구조로 나타낸 것임

** 일부분이 걸쳐있는경우에는 포함이 안됨

    (P3에 H는 포함 안됨)

** F = 4 이므로 p1~p4까지의 mbr이 있음

leaf 노드가 가지고 있는 값

빨간점(x-low, y-low)

파란점(x-high, y-high) 와 같은 모서리 값을 가지고 있음

** 3차원이면 z-low 등과 같은 값도 필요함

R-tree에서의 rectangle  찾기

R-tree에서의 window query시 B+-tree와의 차이점:

unique 한 path로만 내려가지 않음

(위의 예제에서 p3, p4둘다 내려가서 찾아야 함)

R-tree의 main point(특징)

- every parent node completely covers its ‘children’ 

- a child MBR may be covered by more than one parent

  : it is stored under ONLY ONE of them. (ie., no need for dup. elim.) 

   → 어떤 노드의 parent가 1개여야 함 

- a point query may follow multiple branches

   → 위의 예시에서 G, H를 검색해야 되므로 multiple branch(p3, p4)를 검색해야함

데이터 삽입 (insertion)

위의 그림과 같이 걸쳐져 있는 Y가 들어오면 겹쳐있는 쪽에 입력을 해주고

완전히 커버해 주기 위해 p2의 영역이 파란색 구역까지 늘어남

만약 x와 같이 겹쳐져 있는 영역에 추가로 들어온다면

늘어나는 공간이 최소화 되는 노란색쪽을 선택하여 P1이 선택되어 들어감

dead space를 최소화 하기 위함임

dead space

아래그림에서 dead space를 최소화 하는 a가 R-tree에서는 더 좋은 것임

** 늘어나는 면적이 같다면, 각 각의 면적의 사이즈를 구해서

작은쪽의 면적을 크게 하는 방향으로 선택하여 데이터가 입력됨

M을 한계까지 도달했을 때의 split방법

위와 같이 4개의 leaf node가 꽉 차있을 때 W가 입력된다면 

split하여 insert 시킴

split할때 사용하는 다양한 방법들

• (A1: plane sweep, until 50% of rectangles) 

   → 50%의 사각형이 들어올수 있도록 sweep하는것

   → 간단하지만, 최적의 split을 제공하지 않음

• A2: ‘linear’ split (주로 사용)

• A3: quadratic split (주로 사용)

• A4: exponential split: 2M-1 choices 

  → 최적의 split방법을 제공하지만 연산이 복잡하여 사용하지 않음

A2 vs. A3

A2, A3 둘다 seed를 사용함

그리고 가장 “가까운” seed 주변으로 clustering 함

“가까운의 의미” 

seed를 포함했을 때 얼마나 면적이 많이 늘어나는가를 기준으로 clustering 함

seed1에 포함하는 것이 면적이 적게 늘어남

Linear에서 seed 구하기:

Find the highest and lowest side in each dimension, normalize the separations,

choose the pair with the greatest normalized separation

→ x축과 y축의 scale을 동일하게 표준화 하고,

    seed를 잡을 때, 한 축을 기준으로 가장 멀리있는 두 노드를 선택

Quadratic: 

For each pair E1 and E2, calculate the rectangle J=MBR(E1, E2) and d= J-E1-E2. 

Choose the pair with the largest d 

→ 모든 rectangle의 pair를 seed로 잡고, 그 안에서 면적을 가장 크게 하는 조합으로 seed를 설정하는 것임 

→ nC2의 조합이므로 n(n-1)/2이고, 즉 O(n2)의 복잡도를 가짐 

d는 위의그림에서 J-E1-E2한 영역임

R-tree 삭제

R-tree 삭제시 m의 조건보다 더 작은 값을 leaf노드에 갖게 되면 

아예 그 leaf노드를 제외하고 기존 leaf와 합쳐서 포함함

위 그림에서 G가 삭제되면 최소 2인 m을 만족하지 못하므로 

p3를 제외하고 기존 노드에 합쳐 [H, I, J, F]로 변경됨

R-TREE의 변형

R+-tree: DO not allow overlapping, so split the objects (similar to z-values) 

→ 기존 R+tree 단점: 기존에 overlapping되는 영역에 W가 insert 되면 두번(A,B) 탐색해야됨

→ 겹치치 않게 구성하는 tree를 R+tree라고함

단, 아래그림처럼 중복(G)이 되어 표현이 되는 경우가 있어 연구하기만 하고 실제 사용 되지는 않음

 

R*-tree: change the insertion, deletion algorithms

  (minimize not only area but also perimeter, forced re-insertion ) 

Hilbert R-tree: use the Hilbert values to insert objects into the tree 

→ Hilbert ordering을 통해 삽입을 할때 MBR순서를 정해줘서

    더 compact한 R-tree를 구성할 수 있음(Object의 인접성을 고려)