[데이터베이스] R-tree의 종류별 개요, 기능, 특성분석 및 활용도 조사

목차

기본 R-tree
1. R-tree
　1) Introduction
　2) Definition
　3) Operation
　4) Discussion
2. R+-tree
3. R*-tree
➢ 기본 R-tree의 활용도
R-tree를 기반으로 시공간 색인에 쓰이는 tree
4. HR-tree, HR+-tree
5. MV3R-tree
6. TIR-tree
➢ R-tree를 기반으로 시공간 색인에 쓰이는 tree의 활용도
R-tree를 기반으로 궤적색인에 쓰이는 tree
7. STR-tree
8. TPR-tree
9. MPR-tree
➢ R-tree를 기반으로 궤적색인에 쓰이는 tree의 활용도
참고문헌

본문내용

* 각 chapter별 세부사항은 1. R-tree의 세부사항 순서와 동일
기본 R-tree
1. R-tree
1) Introduction
Spatial data를 효율적으로 처리하기 위해 Database System은 공간 위치에 따라 data items을 신속하게 가져오는 것을 도와줄 index mechanism이 필요하다. 그러나 기존의 indexing methods는 다차원 공간에 위치하는 non-zero size의 data object에 적합하지 않다. 이러한 필요를 충족시켜 줄 수 있는 것이 R-tree라고 불리는 dynamic index structure (삽입과 삭제가 탐색과 함께 서로 사용되고 주기적인 재구성이 필요하지 않은 구조) 이다. B+ tree를 2차원이상으로 확장한 tree이며, 각 node와 객체는 MBR(Minimum Bounding Region) 또는 MBB(Minimum Bounding Box)에 의해 표현된다. tree는 MBR들간의 포함관계로 표현된다.

* 참고 : MBR이란?
선들과 기하학적으로 인코드된 불규칙 다각형들은 X Y평면에서 객체의 끝점에 닿기 위해 직교 사각형으로 나타낸다.

　≪ 그 림 ≫

2) Definition
Multi-dimensional point data를 처리하기 위해 R-tree구조는 non-zero size Nodes를 가진 spatial data object들을 indexing하는데 유용하다.




≪ … 중 략 … ≫




R-tree를 기반으로 시공간 색인에 쓰이는 tree
4. HR-tree, HR+-tree
1) Introduction
　R-tree에 거리시간 개념을 추가하여 이력정보를 표현할 수 있으며, 연속적인 상태를 표현하기 위해 R-tree에 중복 개념을 추가한 것이다. 기존의 R-tree는 항상 현재 상태의 dataset만을 색인 내에 유지(과거 상태 보존)하였다. HR-tree는 모든timestamp마다 다른 색인 인스턴스로 구성된다. 기본적인 기술은 원래의 tree는 유지하고 상태가 변한 루트와 가지를 대체함으로써 현재와 과거를 유지하는 것이다. 상태가 변하지 않는 가지들은 복제되지 않는다. 현재의 상태에 대한2차원R-tree를 만들어 유지하는 방법을 사용한다. HR+-tree는 HR-tree의 동일한 node내에 서로 다른 버전(timestamp)의 entry를 허용하지 않는 제약 조건을 없애므로써 성능개선을 하였다.

키워드

R-tree,   R-tree 종류,   R-tree 기능,   R-tree 특성,   R-tree 활용도