R-Tree

R-Tree

- B-트리의 다차원 확장

- 균형잡힌 검색트리

- 모든 레코드는 리프 노드에서만 가리킴

- 다차원 도형의 저장 가능

- 기본적으로, KDB-Tree와 노드 구조를 같이 한다.

 

삽입 연산

1. 노드가 삽입될 위치를 찾은 후, 값을 해당 노드에 삽입한다.

2-1 삽입 이후에 OverFlow가 발생하지 않았으면 삽입에 성공

2-2 삽입 이후에  overflow가 발생한 노드가 있다면 재분배 시도

2-3 삽입 이후에 overflow가 발생한 노드가 있는데 재분배가 안되는 경우 노드를 분할한다.