[파일 처리] 06 인덱스 구조 - 중간고사 전

1. 인덱스

1) 특징 : 파일의 레코드들에 대한 효율적 접근 

- <레코드 키값, 레코드 주소(포인터)> 쌍

 

2) 종류

- 키에 따른 인덱스 : 기본 인덱스, 보조 인덱스

- 파일 조직에 따른 인덱스 : 집중 인덱스, 비집중 인덱스

- 데이터 범위에 따른 인덱스 : 밀집 인덱스, 희소 인덱스

 

3) 이진 트리 : 왼쪽 서브트리와 오른쪽 서브트리로 구성

 

2. 이원 탐색 트리

- 이진트리이면서 각 노드 Ni 레코드 키Ki와 이 키를 가지고 있는 레코드 포인터를 포함함

- 왼쪽 서브트리 < 루트 노드 < 오른쪽 서브트리

 

1) 이원 탐색 트리에서의 검색(키 값 K)

- 트리가 공백 : 검색은 노드를 찾지 못하고 실패

- K = Ki : 노드 Ni가 원하는 노드

- K < Ki : 루트의 왼쪽 서브트리를 검색

- K > Ki : 루트의 오른쪽 서브트리를 검색

 

2) 이원 탐색 트리에서의 삽입

- 트리가 공백 : K를 루트 노드로 삽입

- K = Ki : 트리에 같은 기 값이 존재하므로 삽입 거부

- K < Ki : 루트의 왼쪽 서브트리로 이동하여 계속 탐색

- K > Ki : 루트의 오른쪽 서브트리로 이동하여 계속 탐색

 

3) 이원 탐색 트리에서의 삭제

- 삭제 노드가 가진 자식 수에 따른 삭제 연산

① 자식이 없으면 단순히 그 노드 삭제

② 자식이 1개면 삭제되는 노드에 자식 노드 위치

③ 자식이 2개면 왼쪽 서브트리에서 가장 큰 키 값/ 오른쪽 서브트리에서 가장 작은 값으로 대체 선택하여 삭제

 

4) 이원 탐색트리의 성능

ⓐ 편향 이원 탐색트리 : 리프 노드의 탐색 시간은 최악

* n개의 노드인 이원 탐색 트리에서의 최악의 탐색 시간은 n의 노드 탐색

ⓑ 우수한 성능이 되기 위한 조건

- 가장 자주 접근되는 노드는 루트에 가장 가까이 유지함

- 트리가 균형 트리가 되도록 함

ⓒ 이원 탐색 트리의 단점

- 삽입, 삭제 후 효율적 접근을 위한 균형 유지 부담

- 작은 분기율에 따른 긴 탐색 경로와 검색 시간

 

3. AVL 트리

1) 정의

- 트리의 모든 노드에 대해 오른쪽 서브트리와 왼쪽 서브트리의 높이차는 1이거나 같음

 

2 )특징

- 트리 전체를 재 균형 시키지 않고도 트리의 균형 유지

- 삽입, 삭제 연산 시간이 짧음, 검색시간 O(logN)

 

3) AVL 트리에서의 검색과 삽입

ⓐ 검색 : 일반 이원 탐색 트리의 검색 연산과 동일,  O(logN)

ⓑ 삽입 : 삽입되는 위치에서 루트로의 경로에 있는 조상 노드들의 균형인수에 영향을 줄 수 있음

* 불균형이 탐지된 가장 가까운 조상 노드의 균형인수롤 ±1 이하로 재 균형 시켜야 함

X : 불균형으로 판명된 노드
LL : X의 왼쪽 자식의 왼쪽 서브트리에 삽입
RR : X의 오른쪽 자식의 오른쪽 서브트리에 삽입
LR : L의 왼쪽 자식의 오른쪽 서브트리에 삽입
RL : X의 오른쪽 자식의 왼쪽 서브트리에 삽입

> 회전

- 단순 회전 : 한번의 회전만 필요(LL, RR), 탐색 순서를 유지하면서 부모와 자식 원소 위치 교환

- 이중 회전 : 두번의 회전이 필요함(LR, RL)

 

4) AVL 트리의 높이

ⓐ AVL 트리에서 높이의 범위 : 완전 균형 이원탐색 트리보다 45% 이상은 높아지지 않음

ⓑ 완전 균형 이원 탐색 트리와 높이 균형 이원 탐색 트리의 비교

- 완전 균형 이원 탐색 트리는 변경 시 전체 재균형 작업이 필요, 높이 균형 이원 탐색 트리는 부분적인 재구성

- 높이 균형 이원 탐색 시간이 더 작다 O(1.4logN) : O(logN)

ⓒ AVL 트리는 메인 메모리에 거주하는 내부 구조로서 너무 크면 균형 m-원 탐색 트리 사용