SDBMS ⑧ The R-Tree - Insert, Split

 

SDBMS 공간데이터베이스

 

⑧ The R-Tree

Insert, Split

 

---

 

0. Data Driven Structure

객체를 기준으로 인덱싱하는 구조

객체 주변에 존재하는 객체가 서로의 인덱싱에 영향을 준다.

위치를 기준으로 인덱싱(: Space Driven Structure)하지 않음.

 

 

---

 

1. R-Tree

: MBR을 이용하여 다차원 데이터를 관리하는 data driven structure

  아래 특징에 의해 R-Tree는 트리 빌드와 쿼리 수행에서 일정 수준 이상의 성능을 보장한다.

 

- Root 노드는 최소 2개의 자식 노드를 가진다.

- Root가 아닌 non-leaf 노드는 최소 m, 최대 M개의 자식 노드를 가진다.

- Leaf 노드는 최소 m, 최대 M개의 entry를 저장한다.

- Leaf 노드의 깊이가 일정한 트리이다.

B+tree와 비슷한 점이 상당히 많다.

그러나 B+tree는 key를 기준으로 total order를 따르는 반면

R-tree는 total order이 아닌 MBR에 따라 객체를 인덱싱한다.

 

- Leaf node의 각 entry는 객체에 대응한다.

Leaf node entry ↔ { object MBR, object pointer }

 

- 노드는 노드의 MBR에 대응한다.

- 부모 노드의 MBR은 자식 노드의 MBR을 모두 포함한다.

node ↔ { node MBR, node pointer }

 

- 같은 depth 노드의 MBR이 최대한 겹치지 않게 한다.

 

 

 

아래는 A~J의 사각형 객체를 관리하는 R-tree(오)와 각 노드의 MBR을 공간 상에 표현한 그림(왼)이다.

m=2, M=4

객체 A~J는 각각 entry A~J에 대응하고

leaf 노드 W는 leaf 노드 A, D, E를 자식 노드로

non-leaf 노드 U는 non-leaf 노드 W, Y를 자식 노드로 가진다.

Root 노드 R은 모든 객체의 MBR을 포함하는 MBR에 대응한다.

 

 

---

 

2. Insert

 

B+tree의 경우 root에서부터 leaf까지 새로운 객체와 노드의 key값을 비교해 객체를 삽입할 노드를 찾았다.

R-tree 또한 아래 알고리즘을 따라 객체를 삽입한다.

 

Insert(e)

객체 e를 트리에 삽입한다.

Insert(entry e) {
	node N = Root
    
	while(!N.isLeaf) N = ChooseChild(N,e)
	InsertToLeaf(N,e)
    
	if(N.overflow) SplitAdjust(N)
	else Adjust(N)
}

 

ChooseChild(N,e)

노드 N의 자식 노드 중 e를 삽입하기에 가장 적절한 노드를 찾아 반환한다.

여기서 가장 적절한 노드는 e 삽입 후 증가하는 MBR의 넓이가 가장 작은 노드를 말한다.

같은 depth 노드 MBR간 겹치는 영역을 최소화 하여 가까운 객체를 한 MBR로 묶기 위함.

 

InsertToLeaf(N,e)

노드 N에 객체 e를 leaf 노드에 삽입한다.

 

SplitAdjust(N)

노드 N의 자식 개수가 M개를 초과하면 노드를 분할해 새로운 노드를 만들어 N의 부모 노드에 삽입한다.

SplitAdjust(node N){
	node NewN = Split(N)
    
	if(N.isRoot) CreateNewRoot(N,NewN)
	else {
		node P = N.parent
		InsertNode(P,NewN)
        
		if(P.overflow) SplitAdjust(P)
		else Adjust(P)
	}
}

 

Adjust(N)

노드 N부터 Root까지 MBR의 크기를 조정한다.

새로운 객체를 삽입/노드 분할로 인해 MBR의 변화가 생길 수 있기 때문

 

Split(N)

노드 N의 자식 노드 수가 M개를 초과하므로 N의 일부 자식 노드를 새로운 노드로 옮긴다.

 

 

 

---

 

3. Split

 

분할된 두 노드의 기준이 될 자식 노드 A, B를 고른 후

남은 자식 노드를 기준에 따라 A, B가 삽입된 노드에 삽입한다.

 

분할 기준은 다양하나, 데이터 관리에서 우선순위에 따라 결정한다.

아래에서 a는 가장 간단하지만 공간 상 효율적이지 않고

d는 공간 상 가장 효율적이나 가장 복잡한 방법(브루트 포스,,)

 

a. Plane Sweep

: 단순 추가 순으로 일정 비율을 새로운 노드에 삽입한다.

b. Linear Split

: 한 축 기준으로 가장 멀리 있는 두 노드를 A, B로 하고 나머지 노드는 두 노드에 추가할 때 증가하는 MBR이 적은 곳으로 삽입한다.

c. Quadratic Split

: 한 MBR에 속하면 낭비되는 공간이 가장 큰 두 노드를 A, B로 하고, 나머지 노드는 두 노드에 추가할 때 증가하는 MBR의 넓이가 적은 순서대로 찾아 삽입한다.

d. Exponential Split

: 모든 분할 경우에 대해 계산한 후 공간 상 가장 효율적인 분할을 선택한다.

 

가장 일반적으로는 c를 사용한다.

QuadraticSplit(nodeset S){
	int Worst=0
	nodeset S1, S2
 	for(node A:S)
		for(node B:S)
			if(Waste(A.mbr,B.mbr)>Worse){
				Worst=Waste(A.mbr,B.mbr)
				S1={A}, S2={B}
			}
	S-=S1, S-=S2

	int d1, d2, Best=INF
	nodeset BestS
	node BestE
	while(S.isEmpty){
		for(node E:S){
			d1=Expansion(S1.mbr,E.mbr)
			d2=Expansion(S2.mbr,E.mbr)
            
			if(Best>d1 & d2>d1) Best=d1, BestS=S1, BestE=E
			else if(Best>d2 & d1>d2) Best=d2, BestS=S2, BestE=E
		}
		BestS+={BestE}, S-={BestE}
        
		if(S1.size>M-m) S2+=S, S.empty
		else if(S2.size()>M-m) S1+=S, S.empty
	}
}

STEP 1. 노드 N의 자식 노드 집합 S를 분할하는 기준 자식 노드 A, B를 고른다.

두 자식 노드의 MBR이 같은 MBR에 포함될 때

낭비되는 공간의 넓이가 가장 큰 쌍 (A, B)를 골라 A는 S1에, B는 S2에 각각 삽입한다.

이후 S에서 S1, S2의 원소를 삭제한다.

 

STEP 2. 남은 S의 원소를 S1, S2에 분배한다.

S의 각 원소에 대해 노드를 S1, S2에 삽입할 때 증가하는 MBR의 크기를 d1, d2로 구한다.

d1과 d2 중 최솟값이 가장 작은 원소를 BestE, BestE를 삽입할 집합을 BestS로 저장한다.

for문을 종료하고 BestS에 BestE를 삽입, S에서 BestE를 삭제한다.

S가 비어있을 때까지 반복하며, 두 집합 중 한 집합의 원소가 m 미만이 되지 않도록 한다.

 

 

---

 

* example

m=2, M=4인 아래 R-tree에 새로운 entry  K 를 삽입하자.

 K  삽입 시 증가할 MBR의 넓이가 가장 작은 node는 R→V→Z 순으로 찾을 수 있고

따라서  K 를 Z에 삽입한다. 삽입 후 조정(Adjust) 과정이 끝난 트리는 아래와 같다.

 

이제 새로운 객체  L 을 삽입하자.

 L 을 삽입하기에 적절한 노드는 Z이다.

 

 L 을 Z에 삽입하면 Z의 자식 노드 수가 5개가 되어 overflow가 발생하므로 Z를 분할해야 한다.

Quadratic Split에 따라

Seed로서 F, J를 선택해 F를 Z1에, J를 Z2에 삽입한 뒤

H, L, K 순으로 각각 Z1, Z2, Z1에 삽입하여 분할을 종료한다.

 

 L 을 삽입한 후 R-tree는 아래와 같다.

 

 

 

 

 

---

남은 내용(삭제, 쿼리, 변종 트리 등..)은 ⒝에서

 

 

너무 오랜만이라(약 4달) 글을 어떤 흐름으로 써야할지 감이 안와 갈팡질팡했다

R Tree는 프로젝트 때문에 열심히 공부했던 부분라 까먹은 부분 없이 다 기억하고 있었는데

오히려 다 알고 있다고 생각하니까 어떤 순서로 정리해놔야 할지 감이 안 왔다.. 휴

insert, split, 트리 자체의 특징을 구분하기가 어려워서.. (다 연관되어 있으니까)

 

암튼 4개월 숙원을 이뤄 다행.. 남은 포스팅을 밀리지 않고 마무리 하고 싶다