[파일 처리] 09 다중 키 화일

 

01 다중 키 화일

 

1. 다중 키 화일의 개념

1) 단일 키화일

- 지금까지 살펴 본 화일들로 기본 키를 사용하는 화일

- 순차 화일, 직접화일, 인덱스된 순차화일

 

2) 다중 키 화일

- 하나의 데이터 화일에 대해 여러 다른 탐색키를 이용한 여러 개의 접근 경로를 제공

 

3) 구현 방법

- 데이터를 중복 이용하여 각 응용에 맞는 화일을 각각 구성 

- 한 화일에 대한 다수의 접근 경로 구축 : 다중 키 화일

• 역 화일 : 인덱스 이용
• 다중리스트 화일 : 레코드 사이의 리스트 이용

 

02 역 화일

1. 역 화일 구조

- 역 인덱스를 이용하는 구조

- 역 : 인덱스와 데이터 레코드 화일을 연결

 

2. 역 인덱스

1) 특징

- 데이터 화일에 있는 키 필드 값을 인덱스 키로 포함

- 인덱스 엔트리 = (키 값, 레코드 포인터)

- 화일은 키 필드에 대해 도치되었다고 함

- 많은 dbms의 물리적 데이터베이스 구조에 사용

 

2) 구성

- 인덱스들이 정렬되어 있다면 이원 탐색(O(logN)), 순차 탐색(O(N))

- 역 인덱스에서 정렬된 키의 순서 != 레코드의 순서

- 인덱스 구조 : 테이블-정적구성, 트리-동적 구성

- 직접 화일 위나, 인덱스 된 순차 화일 위에 구성 가능

 

3) 종류

- 역 : 데이터 화일에서 키 값 제거하여 역 인덱스에만 위치

- 역 인덱스가 만들어지는 수에 따라 

• 완전 역 화일 : 데이터 레코드의 모든 필드에 대한 역 인덱스
• 부분 역 화일 : 몇개의 필드에 대해서만 역 인덱스 구성

4) 역 인덱스 구성 방법의 대안

- 직접 주소 기법 : 인덱스 엔트리 = ( 보조 키, 레코드 주소 )

- 대안 : 간접 주소 기법 이용(보조 키, 기본 키)

* 간접 주소 기법 장점 : 역 인덱스 파일에 영향을 주지 않는다. 

- 키 : 기본 키, 보조 키

 

5) 비 유일 보조 키에 대한 역 인덱스

- 가변수 포인터를 위한 인덱스 구현 방법

ⓐ 가변 길이 인덱스 엔트리로 관리

ⓑ 고정 길이 인덱스 엔트리로 관리, 최대 수의 엔트리를 수용할수 있는 공간을 할당

ⓒ 인덱스 엔트리를 중복시켜 관리 : 역 인덱스의 엔트리 = (보조키 값, 하나의 주소) 쌍

- 역화일의 장점은 인덱스만으로도 질의 응답이 가능

 

6) 연산

① 삽입

- 데이터 화일 : 레코드 삽입

- 역 인덱스 화일 : 기존 인덱스 엔트리에 포인터만 첨가하거나 새로운 인덱스 엔트리 삽입

② 삭제

- 데이터 화일 : 레코드 삭제

- 역 인덱스 화일 : 포인터 제거, 공백이면 엔트리 제거

③ 갱신

- 데이터 화일 : 레코드 갱신 작업

- 역 인덱스 화일 : 갱신 영향을 받은 모든 역 인덱스 화일에 삽입, 삭제 연산을 수행

 

 

03 다중 리스트 화일

1. 특징

- 현재 많은 상용 DBMS의 물리적 DB구조의 기초

- 각 보조키에 대해 하나의 다중 리스트 화일 유지

 

2, 역 인덱스와 다중 리스트 인덱스의 차이점

1) 역 인덱스

- (키 값, 그 키 값의 모든 레코드들에 대한 포인터)

- 인덱스 엔트리 : 여러 개의 포인터 값을 갖는 가변길이

- 역 인덱스를 구성 -> 데이터 화일 구조에 영향 없음

 

2) 다중 리스트 인덱스

- (키 값, 하나의 레코드에 대한 시작 포인터)

- 나머지 레코드 -> 데이터 화일에서 연결리스트 구조로 유지 

- 인덱스 엔트리 : 하나의 포인터 값만을 갖는 고정길이

- 다중 리스트 인덱스 구성 -> 데이터 화일 구조 변경 필요

- 데이터 화일 : 인덱스 리스트를 위한 포인터 필드 추가

 

3. 구조

...

다중 리스트 인덱스 필드 1

링크 필드 1

다중 리스트 인덱스 필드 2

링크 필드 2

 

4. 연산

1) 삽입

- 데이터 화일 : 새 레코드를 삽입

- 인덱스 참조 -> 데이터 화일의 연결리스트에 연결

- 인덱스에 없으면 -> 새 인덱스 엔트리로 삽입

 

2) 삭제

- 데이터 화일 : 연결리스트에서 하나의 노드 삭제

- 인덱스 : 연결리스트에서 유일 멤버이면 -> 인덱스 삭제

 

3) 갱신

- 데이터 화일 : 레코드 필드 값이 변경되면

- 다중 리스트 변경

 

4) 다중 리스트의 구현 방법

- 단순/이중 연결 (원형)리스트

 

04 역 화일과 다중 리스트 화일의 비교

1. 공통점

- 모든 보조 키에 대한 인덱스 유지

- 인덱스는 테이블, 트리 형태로 구성

- 인덱스 엔트리들은 정렬 가능

- 데이터 레코드는 직접/간접 주소법 사용

차이점	역 인덱스	다중 리스트 인덱스
인덱스 엔트리	보조키 값의 모든 레코드 포인터	첫 번째 레코드만 포인터, 나머지 레코드는 연결리스트
엔트리 길이	가변 길이	고정 길이
정렬	오버헤드	오버헤드
데이터 화일 구조	영향 없음	링크 필드 첨가
질 의	질의 처리 능력 우월	인덱스 관리 용이 (고정길이 엔트리)