R-Tree

MBR(Minimum Bounding Region)

 

최소 경계

 

[개념] R-Tree에서 공간을 저장하기 위한 단위, 공간을 분할하여 저장하는 영역

[종류] 중간 MBR, 리프노드 MBR, 객체 MBR

[표현] 2차원 공간>시각적 MBR>R-Tree

 

---

 

R트리

 

다차원 균형 트리

 

[개념]최소사각형(MBR, Minimum Bounding Rectangle)에 기반한 공간정보 탐색 지원 인덱싱 기법

[구성요소]1)Branch Node(영역표현, I:하위레벨 노드의 엔티티에 있는 모든 사각형을 포함하는 사각형, Child Pointer:R트리에서 하위레벨 노드의 주소) 2)Leaf Node(데이터 객체에 대한 포인터를 포함, I:n차원 Rectangle, Tuple-Identifier:데이터 레코드에 대한 유니크한 포인터)

[탐색]

1)교차질의:영역검색질의,재귀함수,경로검색

2)포함질의:위치추적

3)근접이웃질의:K-NN질의, 우선순위 큐, 주변검색

[삽입] 

1)단말노드 선택 : ChooseLeaf 알고리즘

2)단말노드 데이터 선택: 빈공간 => 새로운 엔트리, 없는 경우 => 노드 분할

3)트리 재조정: MBR 조정, 분할노드 삽입/내부노드 분할

4)트리 높이 증가: 분할시 새로운 루트노드 생성

 

 

SAM(Spatial Access Method) 같은 선/면/다각형/다면체의 저장, 검색에 활용

[장점] 다차원 data쿼리 가능, 구현용이

[단점] 임의삽입순서로 성능저하, 겹침현상

[고려사항]1)Overlap:같은 객체를 두번이상 검색 ex)X를 검색:R6-R2-R5를 검색

2)Dead Space:검색은 하지만 데이터가 없음

 -R*트리를 통해 겹침으로 인한 성능저하 해결(같은 레벨의 노드간 겹침 불허)

 

---

 

R+트리

 

k-d-b트리, MBR중복제거

node간 겹침삭제

disjoint

 

[개념] R트리의 MBR중복제거, k-d-B 트리 특징을 통해 성능 향상된 트리

[특징] 중첩 성능저하 해결, 노드간 중첩 제거, 중복저장

[개선]

1)적어도 1/2 엔트리 채워진다는 보장 없음

2)중간노드 MBR은 중첩되지 않음

3)데이터 객체 분할시 리프노드 중복 저장가능성>공간사용증가

 

[장/단점]

장 - MBR겹침문제 개선, 노드탐색 개선

단 - 노드분할에 따른 하위파급 문제, 중복으로 성능하락

 

---

 

R*트리

 

노드 클러스터링, 삽입/삭제개선

Update속도 느림, 강제재삽입

 

[개념] R-트리의 삽입,삭제 알고리즘 개선

[특징] 삽입,삭제연산시 부모노드의 MBR 효율적 확장

[개선]

1)분할알고리즘 개선(중첩감소)

2)삽입 오버플로발생시 강제 재삽입>복잡도 증가

3)점,공간데이터 동시 효율지원

 

[장/단점]

장 - 노드 클러스터링 효과증대, 겹침현상 감소

단 - 느린 Update, 삽입시 부적절한 분할로 성능저하 가능성 존재

[성능개선시 고려]

중첩최소화,면적최소화,MBR 정사각형화

 

---

 

 

N- 차원의 공간 데이터를 효과적으로 저장하고 지리정보와 관련된 질의를 빠르게 수행 할 수 있는 자료구조

 

나. R-tree의 특징

- 저장단위: 공간의 최소경계사각형(MBR: Minimum Bounding Rectangle)들로 분할하여 저장

- 저장구조: MBR들이 서로 겹칠수 있으며 상위레벨 MBR은 하위레벨 MBR들을 포함하는 계층적 트리구조를 가짐

- 관리정보: R-Tree의 각 노드는 미리 정의된 범위내에서 유동적인 개수의 자식노드들의 MBR과 포인터 정보를 가짐

- 동적 인덱스: 삽입과 삭제가 탐색과 함께 서로 사용되고 주기적인 재구성이 필요하지 않음

 

 

. R-Tree 구현 알고리즘

- 교차질의(Intersection): 모든 노드들은 질의입력 MBR과 자식노드들의 MBR을 비교하여 교차되는 영역이 있는 자식노드들에게만 질의를 전달함. 이러한 검색은 재귀함수로 구현 가능함

- 포함질의(Containment): 교차되는 영역이 있는 자식노드가 아닌, 질의를 포함하는 자식노드들만 검색

- 근접이웃질의(Nearest Neighbor): 점좌표와 거리를 입력받아 특정 점좌표로부터 가장 가까운 거리에 위치한 데이터를 찾는 알고리즘

- 이외에도 검색, 삽입, 삭제 알고리즘이 존재함