SDBMS ⑧ The R-Tree - Search, Delete, Variations

 

SDBMS 공간데이터 베이스

 

⑧ The R-Tree

Search, Delete, Variations

 

---

 

Recall

R-tree의 노드는 { mbr, node pointer } 로 표현하며 leaf 노드의 entry는 각 객체와 대응한다.

각 노드의 자식 노드 mbr은 부모 노드 mbr에 포함된다.

Insert 및 split 시 R tree는 같은 깊이 노드 mbr이 최대한 겹치지 않는 방향으로 작동한다.

 

 

 

 

4. Search

R-tree에서 search 역시 mbr을 활용하여 진행한다.

 

Search(R)

Root의 자식 노드 중 범위 R과 겹치는(overlap) 노드에 대해서

해당 노드의 자식 노드 중 범위 R과 겹치는 노드를 찾는 과정을 반복한다.

해당 노드가 leaf 노드일 때 집합에 entry를 추가하고, 과정이 모두 종료되면 집합을 결과로 반환한다.

BFS로 큐를 사용해 해결해도 되고

DFS로 아래와 같이 노드 N에서 R과 겹치는 entry를 찾는 함수를 사용해도 된다. 

Search(node N, range R){
	entryset S
	
	if(N.isLeaf)
		for(entry e:N.children) if(Overlap(e.mbr,R)) S+={e}
	else 
		for(node C:N.children) if(Overlap(C.mbr,R)) S+=Search(C,R)

	return S
}

 

위 과정에 따라 아래 트리에서 초록색으로 칠한 부분(*)과 겹치는 객체 { B, F, H, K }를 아래 과정을 통해 얻는다.

R → V → X ⇒ { B }

R → V → Z1 ⇒ { F, H, K }

R → V → Z2 ⇒ { }

 

노드가 탐색 대상일 때 

V, Z1와 같이 자식 노드 또한 모두 탐색 대상일 수 있고

R, X와 같이 자식 노드의 일부만 탐색 대상일 수도,

Z2와 같이 자식 노드 중 탐색 대상이 없을 수도 있다.

 

그러나 탐색 대상이 아닌 노드의 자식 노드는 모두 탐색 대상이 아니므로 오류없이 search를 수행할 수 있다.

 

 

 

 

---

5. Delete

R-tree에서 어떤 객체 E를 삭제하고 싶다면

그 객체 E가 있는지 먼저 찾은 뒤 객체가 있으면 제거한다.

 

자식 노드를 제거한 객체의 mbr은 축소할 수 있으므로

삭제된 객체의 부모 노드부터 root 노드까지 mbr의 변화가 생길 수 있다.

 

또한 deletion으로 인해 non-root 노드의 자식 노드 수가 m개 미만이 되거나

leaf 노드의 자식 entry 수가 m개 미만이 되는 경우(underflow)

해당 노드는 삭제하고 자식 노드를 트리에 재삽입한다.

 

 

아래 트리가 m=2를 만족해야 할 때

delete E

W는 자식 노드 A, D만을 갖게 되고, W의 mbr 크기는 감소, U, R의 mbr 크기는 현재 상태를 유지한다.

 

delete A

W는 자식 노드 D, E만을 가지며 W, U, R의 mbr 크기가 모두 감소한다.

 

delete L

Z2가 자식 노드를 J 한 개 가지게 되어 Z2 삭제, L을 Z1에 삽입한다.

 

delete G

Y underflow ⇒ Y 삭제, I를 W에 삽입,

U underflow ⇒ U 삭제, W를 V에 삽입,

루트 R 또한 underflow, R을 삭제하고 루트를 V로 바꿔 트리의 높이가 1 감소한다.

 

 

 

---

R-tree는 non-root 노드의 자식 노드 수를 m이상 M이하로 유지하고

모든 leaf 노드가 같은 depth가 되게 유지하며

같은 depth의 노드 mbr의 overlap을 최대한 방지하는 방향으로 데이터를 인덱싱하기 때문에

insert, delete와 각종 query(select, range, window ...)의 보장된 성능을 제공한다.

 

그러나 노드 mbr의 overlap이 전혀 없진 않으며 최악의 경우 모든 노드를 탐색해야 하는 단점이 있다.

이런 단점을 보완하기 위해 R-tree를 변형한 트리를 사용할 수도 있다.

 

 

 

6. R*-tree

R-tree의 기존 특징 중 아래 네 가지를 최적화한 트리이다.

- 각 노드 mbr의 넓이

- 각 노드 mbr의 둘레 길이

- 두 노드 mbr이 겹치는 면적의 넓이

- 저장공간 이용율

 

Insert

객체를 삽입할 노드를 고를 때,

다음 노드가 leaf 직전 노드이면 늘어나는 mbr 넓이가 최소, 겹치는 mbr 넓이가 최소, mbr 넓이가 최소인 노드

아닌 경우 겹치는 mbr 넓이가 최소, mbr 넓이가 최소인 노드를 선택한다.

 

Split

노드의 자식 노드 수가 M+1개가 되어 split할 경우

1. Split 기준 축 선택

자식 노드를 각 축에 대해 정렬한 후,정렬 순서에 따라 (k,M+1-k)

개로 자식 노드를 두 노드 A, B로 분배한 후

A, B의 mbr 둘레 길이 합이 최소인 경우를 선택한다.⇒ 이때 k는 최소 m, 최대 M+1-m일 수 있으므로 축마다 M-2m+1가지 경우의 수를 계산해야 한다.

2. Least Overlap Split

고른 축에 대해, 자식 노드를 두 노드 A, B로 분배시 A, B의 mbr이 겹치는 넓이가 최소인 경우를 선택한다.

 

아래 그림과 같은 노드에서,

R-tree에서는 1, 5를 각각 A, B의 seed로 잡은 후 3을 A에 삽입, 4를 A에 삽입해 2를 B에 삽입해

(A,B)=({1,3,4},{5,2})가 돼 A와 B의 overlap이 발생한다.

R*-tree에서는

가로축에 대해 정렬(1,3,4,2,5), (A,B) = ({1,3},{4,2,5}), ({1,3,4},{2,5})일 때의 각 둘레 길이의 합

세로축에 대해 정렬(1,2,4,3,5), (A,B) = ({1,2},{4,3,5}), ({1,2,4},{3,5})일 때의 각 둘레 길이의 합을 비교해

가로축을 선택한 후 (A,B)=({1,3},{2,4,5})가 되도록 split하여 A와 B의 overlap이 발생하지 않는다.

 

Force Reinsert

Split 대신, 의도적으로 몇 개의 entry를 삭제해 겹치는 mbr을 축소한 뒤

entry를 재삽입해 다른 노드의 이용률을 높이며 overlap을 최소화하는 방법이다.

 

가령 위 그림에서 R-tree, R*-tree에 관계없이 A={1,3,4} B={2,5}이고

아래 그림과 같이 B에 6,7,8이 추가된 경우

R-tree에서는 B={2,5,6,7,8}을 {2,6}과 {5,7,8}로 분할해 자식 노드 수가 각각 3, 2, 3개인 세 개의 노드가 생기지만

R*-tree에서는 B={2,5,6,7,8}에서 2를 삭제후 재삽입해서 A={1,2,3,4} B={5,6,7,8}로 해

A와 B의 노드 사용률을 높이며 겹치지 않도록 만들 수 있다.

 

 

 

---

7. Other Variations

 

STR packed R-tree

R-tree나 R*-tree의 데이터 양이 늘어나 트리가 너무 커질 경우 잦은 overlap으로 성능이 저하될 수 있다.

R-tree가 static한 상태를 유지할 수 있는 경우

STR algorithm으로 R-tree를 packing, R-tree 구조를 최적화해 노드 수와 overlap을 줄일 수 있다.

 

Entry가 $N$개, node maximum capacity가 $M$일 때,

leaf 노드가 최대한 많은 자식 entry를 가지도록 R-tree를 최적화하면

leaf 노드의 개수는 최소 $P=\left \lceil N/M \right \rceil$개 가능하다.

즉, $N$개의 객체가 존재하는 공간을 수평, 수직으로 각각 $\sqrt{P}$개로 분할해

그에 맞게 데이터를 각 leaf 노드에 분배하는 방법이다.

아래 논문에서 노드 overlap을 최소화한 상태를 볼 수 있음

STR: A Simple and Efficient Algorithms for R-Tree

 

 

R+-tree

Search알고리즘에서 multiple path를 방지할 수 있는 모델로

동일 level 노드 mbr overlap을 절대 허용하지 않지만 leaf 노드에서는 중복 저장이 일어날 수 있다.

 

 

 

 

 

 

이제껏 leaf node를 object로 할지, object를 자식으로 가지는 노드로 할지 정하는 건 구현 이슈라고 생각했는데

읽어본 거의 모든 자료에서 leaf node를 후자로 설명해둔 걸 보고 잘못 생각해왔다는 걸 깨달았다;;

크게 달라지는 건 없지만 모호한(어쩌면 가장 중요한) 용어 정리가 된 듯.

+ 저번에 구현한 코드를 조금 바꿔야 할 것 같다. (위의 전자처럼 구현했기 때문)

 

포스팅이 생각보다 오래 걸린다 ㅠㅠ 다음 공간데이터 포스팅은 9월 중으로 할 수 있었으면 좋겠다.