R 트리: Difference between revisions
From CS Wiki
No edit summary |
No edit summary |
||
| (3 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
[[분류:데이터베이스]] | [[분류:데이터베이스]][[분류:자료 구조]] | ||
;R Tree | ;R Tree | ||
;다차원의 공간 데이터를 효과적으로 저장하고 지리정보와 관련된 질의를 빠르게 수행 할 수 있는 | ;다차원의 공간 데이터를 효과적으로 저장하고 지리정보와 관련된 질의를 빠르게 수행 할 수 있는 [[트리]] 자료 구조 | ||
* 공간을 최소 경계 사각형(MBR, Minimum Bounding Rectangle) 들로 분할하여 저장 | == 개요 == | ||
* 공간을 '''최소 경계 사각형'''('''MBR''', Minimum Bounding Rectangle) 들로 분할하여 저장 | |||
** 상위 레벨의 MBR 은 하위 레벨의 MBR들을 포함하는 계층적인 트리 구조 | ** 상위 레벨의 MBR 은 하위 레벨의 MBR들을 포함하는 계층적인 트리 구조 | ||
** MBR끼리 겹칠 수도 있음 | ** MBR끼리 겹칠 수도 있음 | ||
* 각 노드는 미리 정의된 범위내에서 유동적인 개수의 자식 노드들의 정보(MBR과 포인터)를 가짐 | * 각 노드는 미리 정의된 범위내에서 유동적인 개수의 자식 노드들의 정보(MBR과 포인터)를 가짐 | ||
[[파일:R 트리.png]] | |||
== R 트리의 종류 == | |||
{| class="wikitable" | |||
|- | |||
! 종류 !! 설명 | |||
|- | |||
| R 트리 || MBR을 이용해서 다차원의 공간 데이터를 저장하기 위한 계층적 트리 | |||
|- | |||
| R+ 트리 || R 트리에서 겹침으로 인한 성능 저하 개선을 위해 겹침 허용 안함 | |||
|- | |||
| R* 트리 || 겹침 허용하지만 최소화, 둘레•면적 최소화 등 합리적 방법 복합 사용 | |||
|} | |||
== 같이 보기 == | == 같이 보기 == | ||
{{틀:데이터베이스 인덱스 트리}} | {{틀:데이터베이스 인덱스 트리}} | ||
Latest revision as of 22:56, 27 December 2019
- R Tree
- 다차원의 공간 데이터를 효과적으로 저장하고 지리정보와 관련된 질의를 빠르게 수행 할 수 있는 트리 자료 구조
개요[edit | edit source]
- 공간을 최소 경계 사각형(MBR, Minimum Bounding Rectangle) 들로 분할하여 저장
- 상위 레벨의 MBR 은 하위 레벨의 MBR들을 포함하는 계층적인 트리 구조
- MBR끼리 겹칠 수도 있음
- 각 노드는 미리 정의된 범위내에서 유동적인 개수의 자식 노드들의 정보(MBR과 포인터)를 가짐
R 트리의 종류[edit | edit source]
| 종류 | 설명 |
|---|---|
| R 트리 | MBR을 이용해서 다차원의 공간 데이터를 저장하기 위한 계층적 트리 |
| R+ 트리 | R 트리에서 겹침으로 인한 성능 저하 개선을 위해 겹침 허용 안함 |
| R* 트리 | 겹침 허용하지만 최소화, 둘레•면적 최소화 등 합리적 방법 복합 사용 |
