<TIL> 140. R-tree

R-tree

B-tree와 비슷한데, 다차원의 공간 데이터를 저장하는 색인
'현재 위치에서 200km 이내의 모든 도시를 찾아라'와 같은 질의에 대해 빠르게 응답.

R-tree는 공간을 최소 경계 사각형(MBR, Minimum Bounding Rectangle) 들로 분할해 저장.
MBR 끼리 겹칠 수도 있고, 상위 레벨의 MBR은 하위 레벨의 MBR들을 포함하는 계층적인 트리 구조.
각 노드는 미리 정의된 범위 내에서 유동적인 개수의 자식 노드들의 정보(MBR과 포인터)를 가짐.

R-tree의 저장과 삭제 알고리즘 - 가까운 데이터들은 되도록 같은 단말 노드(leaf)에 형성
-> MBR 유지 가능, 검색 성능 향상.

검색 알고리즘

교차 질의(intersection)

최소 경계 사각형 MBR을 질의 입력으로 받지만, 검색은 B-tree와 유사.
검색은 루트 노드로부터 시작.
단말 노드를 제외한 모든 중간의 비단말 노드들은 자식 노드의 MBR을 포함하는 MBR을 가짐
단말 노드들의 MBR? 단말 노드가 가리키는 공간 데이터들을 둘러쌈.
-> 모든 노트들은 질의 입력 MBR과 자식 노드들의 MBR을 비교해 교차되는 영역이 있는 자식 노드들에게만 질의 전달. -> 재귀함수로 구현 가능

포함 질의(Containment)

교차 질의와 유사, 교차되는 영역이 있는 자식노드가 아닌, 질의를 포함하는 자식노드들만 검색

근접 이웃 질의(Nearest Neighbor)

점 좌표와 거리를 입력으로 받음. 특정 점 좌표로부터 가장 가까운 거리에 위치한 데이터를 찾는 알고리즘 필요

삽입 알고리즘(insertion)

부적절한 상태에 있는 노드 -> 적절한 범위에서 벗어난 수의 항목을 가지고 있다는 것 의미

1. 노드가 어느 위치로 삽입될지 찾은 후 삽입
2. 부적절한 상태의 노드가 없으면 삽입 종료
3. 만약, 어떤 노드가 너무 많은 항목 보유시, 두 노드로 분류 -> 반복적으로 트리를 타며 진행.
   -> 루트 노드를 분리했을 시는 새로운 루트 노드 생성
4. B-tree와 달리, 노드 분리 시, 공간의 특성 고려.
   분리된 MBR들의 겹침정도를 고려해 분리할 차원을 결정, 선형(linear), 사각형(quadratic), 소모적(exhaustive) 분리 알고리즘 있다.

삭제 알고리즘

1. 자율 값의 위치를 찾은 후 그 값을 가진 노드 삭제
2. 부적절한 상태의 노드가 없다면, 삭제 과정 종료
3. 부적절한 상태의 노드 존재시, B-tree와 유사하게 해결.