자료구조 - R트리(R-Tree)

□ R-Tree 개념

R-Tree는 점, 선, 면과 같은 2차원 이상의 공간 정보를 효율적으로 저장하기위한 자료구조로 위치기반 데이터에서 자주 사용된다.

 

□ R-Tree 구조

R-Tree는 여러개의 노드에 MBR(최소 경계 사각형)을 저장하여 그안에 포함되는 객체들의 공간을 나타낸다.

□ MBR(최소 경계 사각형)

각 객체에 사각형으로 경계를 만들고 묶어서 표현하면 아래와 같다.

MBR(최소 경계 사각형)

 

 

위 MBR을 트리로 나타내면 아래와 같다.

 

• 부모 노드(Parent Node): 한 노드에 대해 바로 위에 연결된 노드.
• 자식 노드(Child Node): 한 노드에 대해 바로 아래에 연결된 노드.
• 리프 노드(Leaf Node): 자식이 없는 노드. 트리의 끝을 나타냄.
• 형제 노드(Sibling Node): 같은 부모 노드를 공유하는 노드들.

□ R-Tree와 B-Tree의 차이점

구분	R-Tree	B-Tree
데이터 타입	2차원 이상의 공간 데이터	정렬된 일반 데이터(숫자 ,문자열 등)
노드 구성 방식	MBR(최소 경계 사각형)	키-값 쌍으로 저장
검색 방식	범위와 영역	단일 값
노드 분할 방식	겹침을 최소화하는 알고리즘으로 분할	중간값 기준으로 분할
사용처	위치기반, 공간데이터 검색에 사용	정렬된 데이터 검색 시 사용