[파일 처리] 07 인덱스 된 순차 화일

 

1. 인덱스된 순차화일의 구조

 

1) 구조

-  순차적으로 정렬된 순차데이터 화일과 이 데이터 화일에 대한 포인터를 가지는 인덱스로 구성

- 각 화일은 블록으로 구성 : 인덱스 블록(트리 구조), 데이터 블록(데이터 레코드와 자유공간)

ⓐ 마스터 인덱스 : 최상위 레벨의 인덱스 블록

ⓑ 인덱스 엔트리의 구성 : <최대 키 값, 포인터>

ⓒ 자유 공간 : 레코드의 추가를 위해 남겨둔 여분의 공간, 화일 생성 시 각 블록에 만듦

> 인덱스된 순차 화일

  - 키 값에 따라 정렬된 레코드를 순차적으로 접근 or 직접 접근하는 경우 사용

  - 사전 검색 시 사전 옆면의 색인이 인덱스랑 같은 역할

* 일괄처리와 대화식 처리가 적합한 경우

 

2) 삽입

- 최대 키값에 따라 삽입, 만약 블록이 꽉찼다면 반으로 분할한다.

- 분할됐으면 포인터 되는 키 값이 새로 만들어 져야 한다.

 

2. B+트리

1) 특징 

- B트리의 또다른 변형 구조

- 순차탐색의 성능 향상을 위해 만들어짐

 

2) 구조

ⓐ 인덱스 세트 : 리프 이외의 노드, (키 값, 리프 노드에 대한 경로)만 제공

ⓑ 순차 세트 : 리프 노드, (키 값, 데이터 레코드의 주소)들이 존재

 

3) 차수가 m인 B+트리의 특성

① 리프가 아닌 노드 구조 : <n, P0, K1, P1, K2, P2, ..., Pn-1, Kn, Pn>

② 한 노드 안에 있는 키 값들은 오름차순으로 정렬

③ Ki < Pi 노드 키값들 < Ki+1

④ 모든 리프 노드는 같은 레벨

⑤ 루트는 리프가 아니면 적어도 2개 서브트리를 가짐

⑥ 루트와 리프를 제외한 모든 내부 노드는 m/2~m개의 서브트리 가짐

⑦ 리프 노드는 화일 레코드들의 순차 세트를 나타내며 모두 링크로 연결 됨

⑧ 리프 노드의 구조 : <q, <K1, A1>, ... , <Kq, Aq>, Pnext>

 

4) B트리와 B+트리의 차이

- 인덱스 세트와 순차 세트의 구분이 있으며 구조가 다름

- 인덱스 세트는 리프 노드에 있는 키 값을 찾는 경로로만 이용, 순차 세트에 다시 나타남

- 순차 세트는 실제 데이터를 찾는 데 이용

=> 효율적인 순차 접근이 가능해짐

 

5) 삽입

- B트리에서 삽입과 유사

- 차이 : 리프노드 분할 시 중간 키값의 복사본이 부모 인덱스 노드로 올라가 저장

* 중간 키값 : 왼쪽노드에서 가장 큰 값

 

6) 삭제

- B트리에서 삭제와 유사

- 차이 : 키 값의 삭제는 리프 노드에서만 수행

* 인덱스 세트의 키 값을 삭제할 필요가 있는 경우에는 삭제하지 않고 분리자로 이용

 

7) B+트리의 성능

ⓐ 장점 : 인덱스 노드에는 레코드 포인터를 저장하지 않으므로 노드내 공간 절약 => 트리 레벨 낮아짐

ⓑ 단점 : 검색이 항상 리프노드까지 내려가야만 종료

* 순차 검색은 리프노드에서 연결리스트를 순회하므로 효율적

* B+트리는 직접처리와 순차처리를 모두 필요로 하는 응용에서 효율적