검색어 입력폼

R트리,R+트리,R*트리

저작시기 2013.04 |등록일 2013.04.27 워드파일MS 워드 (docx) | 4페이지 | 가격 1,000원

목차

1. R-트리의 개념
2. R-트리의 특징

1. R+-트리의 개념
2. R+-트리의 특징
3. R-트리와의 차이점
4. R-트리의 장단점

1. R*-트리의 개념
2. R-트리 질의 처리시 고려해야 할 사항(=성능 개선을 위해 고려한 파라미터)
3. R-트리에 비해 개선된 부분
4. R*-트리의 변경 사항
5. R*-트리의 장점

본문내용

1. R-트리의 개념
① B-트리를 다차원 구조로 확장
② 디스크 페이지 단위로 데이터를 저장, 검색할 수 있어서 대용량 데이터에 대한 인덱스 구조로 적당
③ 인덱스 구조는 B-트리와 같이 높이 균형 트리(height balanced tree)
④ 리프 노드의 엔트리는 객체 MBR과 이 객체가 저장된 주소(포인터)로 구성
⑤ 중간 노드의 엔트리는 자식 노드의 모든 MBR을 포함하는 보다 큰 MBR과 자식 노드에 대한 포인터로 구성
2. R-트리의 특징
① 루트 노드가 아닌 노드는 최소 m (m(<=M/2): 한 노드가 저장해야 되는 최소 엔트리 수), 최대 M(한 노드가 저장할 수 있는 최대 엔트리 수)개의 인덱스 엔트리와 자식 포인터를 포함한다.
② 루트 노드는 리프가 아닌 이상 최소 2개의 자식 노드를 갖는다.
③ 모든 리프 노드는 최소 m, 최대 M개의 인덱스 엔트리를 포함한다
④ 리프 노드에 있는 각 인덱스 엔트리는 객체 데이터를 실제 공간적으로 포함하고 있는 MBR과 이 공간 객체가 저장된 페이지 주소를 포함한다.

<중 략>

4. R*-트리의 변경 사항
① ChooseLeaf 알고리즘 변경
- 중간 노드 선택 시에는 최소 면적이 최소인 MBR을 우선
- 리프 노드 선택 시에는 중첩 영역의 증가가 최소가 되는 MBR을 우선
② 노드 분할 알고리즘 변경: 2단계 heuristic 사용
- 분할 축(split axis) 선택: 분할된 두 MBR의 둘레 길이 합이 최소가 되게 하는 축

참고 자료

없음
다운로드 맨위로