[FP] 09. 다중 키 화일

다중 키 화일

하나의 데이터 화일에 여러 종류의 상이한 탐색 키를 이용한 여러 개의 접근 경로를 제공

탐색 키는 기본 키(primary key)와 보조 키(secondary key)로 구분

• 기본 키 : 하나의 레코드를 식별
• 보조 키 : 기본적으로 여러 개의 레코드를 식별

---

복수 접근을 지원하는 방법

 1. 데이터 중복을 이용하여 여러 개의 동일한 내용의 화일을 제공

• 각 응용의 접근 요구에 맞는 화일을 개별적으로 구성
• 같은 내용의 데이터를 중복 저장함으로써 공간의 낭비
• 데이터 일관성 유지가 곤란
• 데이터 모순성으로 인한 데이터 유효성 문제 발생
• 데이터 무결성에 손상 

2. 하나의 화일에 복수의 접근 경로를 지원하는 시스템이 다중 키 화일

• 접근 경로는 기본적으로 인덱스로 구축 : 이원 탐색 트리 / B-트리 / B+트리
• 인덱스와 레코드 사이의 리스트를 이용하여 구축 : 역 화일 / 다중리스트 화일

---

역 화일

역 화일 구조

• 기본적으로 인덱스를 이용하는 구조
• 원리는 도치(역)
• 인덱스 값으로 데이터 레코드 화일을 전도(도치)

역 인덱스

• 데이터 화일에 있는 인덱스 키 값을 인덱스 엔트리로 모두 포함
  그 인덱스 키 값을 가지고 있는 모든 레코드들에 대한 포인터를 포함
• 인덱스 엔트리 : <인덱스 키 값, 레코드 포인터>
• DBMS의 물리적 데이터베이스 구조에 많이 이용됨

 

학생 데이터 화일을 “주민 번호” 필드를 인덱스 키로 도치시키면 오른쪽과 같은 역 인덱스가 된다. 

-> 인덱스를 1차원으로 정렬시킨다. 장점 : 이원 탐색 기법을 사용할 수 있다. 

이원 탐색:O (logN) / 순차 탐색:O(N/2)

• 역 인덱스의 정렬된 키의 순서와 레코드 순서는 반드시 일치하지 않음
• 데이터 화일에 레코드가 삽입되면 역 인덱스도 갱신
• 화일 관리 비용이 많이 든다.
• 인덱스 구조를 트리와 같은 동적 구조로 구성 -> 검색 시간이 빠름, 삽입/삭제 처리는 복잡해진다.
• 보통 인덱스 된 순차 화일이나 직접 화일 위에 구성 
   - 예시 : 학번을 기본 키로 하는 인덱스된 순차 화일에서 주민 번호로 역 인덱스를 구성하면 
   -> 학번, 주민 번호로 직접 접근 가능, 학번으로 순차 접근 가능, 
   ‘주민 번호’로도 순차 접근이 가능하게 하려면 비용이 많이 든다. (역 인덱스에서 키 엔트리를 정렬)

---

역(inversion)의 본질

• 데이터 화일에서 인덱스 키 값을 제거하여 역 인덱스 엔트리에 위치
• 데이터 화일에는 인덱스 키 필드가 제거
• 일반적으로 인덱스 키 필드를 제거하지 않고 역 인덱스를 구성

완전 역 화일

• 데이터 레코드의 모든 필드에 대해 역 인덱스 구축
• 데이터 레코드 화일은 논리적으로 존재할 수 없다.

부분 역 화일

• 몇 개의 주요 필드에 대해서만 역 인덱스를 구성

만약 역 인덱스의 키 값을 데이터 레코드에서 제외했을 때는?

• 학번(기본 키)이 3358인 학생의 주민 번호(역 인덱스)는?
• 주민 번호는 역 인덱스에만 있고 이 역 인덱스와 데이터 화일은 레코드 주소로 연결되어 있음
• 데이터 화일에서 학번 3358로 학생 레코드의 주소를 직접 검색
• 주민 번호 역 인덱스에서 이 레코드 주소를 포함하고 있는 인덱스 엔트리를 탐색하여 주민 번호를 찾음 (순차 탐색으로 비효율적)
• 기본 키 : 유일 식별, 물리적 순서를 결정
• 보조 키 : 레코드 접근을 위한 필드
  => 대안 : 간접 주소 기법을 이용 / 역 인덱스의 엔트리를 <인덱스 키, 기본 키>로 구성

 

인덱스 엔트리에 복수의 포인터를 포함시키는 구현

1. 가변 길이 인덱스 엔트리로 관리
2. 고정 길이 인덱스 엔트리로 관리 : 최대 수의 기본 키 값을 수용할 수 있는 공간을 할당
3. 인덱스 엔트리를 중복시켜 관리 : 역 인덱스의 엔트리는 <인덱스 키 값, 하나의 기본 키>로만 구성

복수의 포인터(기본 키)를 정렬시켜 유지하면 레코드 검색은 신속, 하지만 레코드 갱신 시 추가 부담

 

역 화일의 응용 : 인덱스만으로 질의가 처리 가능

1. 주민 번호가 1036432인 학생이 있는가?
2. 컴퓨터공학과에는 몇 명의 학생이 있는가?
3. 기계과에 속하는 학생의 학번을 나열하라
4. 주민 번호가 1032589인 학생의 학번은 무엇인가?

역 화일의 연산 : 데이터 파일과 역 인덱스 파일을 포함해야 하므로 고비용이다.

• 레코드의 삽입
   - 기본 데이터 레코드 화일에 새 레코드 삽입함과 동시에 모든 역 인덱스 화일을 수정한다. - 인덱스 엔트리로 삽입하거나 레코드 포인터만 첨가
• 레코드의 삭제
   - 기본 데이터 레코드 화일에서 원하는 레코드를 삭제시킨 뒤에 그 레코드가 참여하고 있는 모든 역 인덱스에서 
   삭제 연산을 수행, 포인터를 삭제하고 공백이 되면 인덱스 엔트리를 제거
• 레코드의 갱신
   - 기본 데이터 레코드 화일에서 해당 레코드의 갱신 작업을 마친 뒤 
   영향을 받는 모든 역 인덱스 화일에 대한 삽입과 삭제 연산을 적절히 수행한다.

---

다중 리스트 화일

기본 개념

• 인덱스와 기본 데이터 화일을 연결하는 방법
• 현재 많은 상용 DBMS의 물리적 DB 구조의 기초
• 기본 데이터 레코드 화일과 각 보조 키에 대해, 하나의 다중 리스트 인덱스 화일로 구성

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

• 역 인덱스 : <인덱스 키 값, 그 키 값을 가진 모든 레코드들에 대한 포인터>
   - 인덱스 엔트리 : 여러 개의 포인터 값을 갖는 가변 길이
• 다중 리스트 인덱스 : <인덱스 키 값, 이 키 값을 가진 첫 번째 레코드에 대한 포인터>
   - 나머지 레코드는 기본 데이터 레코드 화일에서 하나의 연결리스트로 유지
   - 각 리스트의 헤드만 유지하는 디렉터리 역할
   - 인덱스 엔트리는 하나의 포인터 값만 갖는 고정 길이

역 화일에서는 역 인덱스를 구성하더라도 데이터 레코드 화일 구조 자체에는 영향을 주지 않았다. 다중 리스트 화일 구조에서는 다중 리스트 인덱스를 구성하면 화일의 구조도 변경되어야 한다. 기본 데이터 레코드 화일은 각 다중 리스트 인덱스 키 값에 따라 접근할 수 있게 연결리스트를 구현할 링크 필드가 추가되어야 한다.

---

 

다중 리스트 인덱스 설계 시의 고려 사항

1. 인덱스 키 값들은 정렬할 것인가?
2. 인덱스의 구성 방법(구조)은?
3. 주소법 : 직접 혹은 간접?
4. 리스트의 데이터 레코드(노드)의 정렬 여부

레코드의 검색
질의 유형의 예시

1. 컴퓨터공학과에는 몇 명의 학생이 있는가?
2. 컴퓨터공학과에 속한 학생들의 학번을 모두 검색하라. 3. 학번이 6861인 학생의 학과가 컴퓨터공학과인가?

질의 처리 과정

• 역 화일은 인덱스만 접근해도 가능
• 다중 리스트 화일은 데이터 레코드에 접근을 해야 한다. (아니면 인덱스 엔트리에 리스트 길이 정보를 추가)
• 다중 리스트 인덱스 엔트리의 변형 : <인덱스 키 값, 첫 번째 레코드의 포인터, 리스트 길이>

리스트 길이 정보의 활용

• 특정 유형의 질의에 최적 접근 경로 선정 시 이용
• 질의 : 입학년도=01, 학과=컴퓨터 인 학생의 이름을 검색하라.
• 1. 학생 데이터 화일의 순차적 탐색 : 20개의 레코드에 대한 접근 필요
• 2. 학과 다중 리스트 인덱스 사용 : 4개의 데이터 레코드에 대한 접근 필요
• 3. 입학년도 다중 리스트 인덱스 사용 : 7개 데이터 레코드에 대한 접근 필요
   => 2번을 최적 방법으로 선택
   => 학과=컴퓨터 인 4개의 레코드를 접근하고 입학년도 필드를 검사하여 이름 검색 가능

레코드의 삽입

• 데이터 화일에 새 레코드를 삽입
• 다중 리스트 인덱스 필드를 전부 참조해서 데이터 레코드 화일의 연결리스트에 연결
• 레코드 키 값이 인덱스 엔트리에 없으면 새 인덱스 엔트리로 삽입

레코드의 삭제

• 데이터 화일에서 레코드 삭제
• 모든 다중 리스트 인덱스의 연결리스트에서 삭제
• 리스트 인덱스에서 유일한 멤버이면 인덱스 엔트리를 삭제
• 리스트 인덱스의 첫 번째 레코드가 삭제된 경우, 두 번째 레코드를 인덱스 엔트리 포인터에 연결

레코드의 갱신

• 데이터 화일과 다중 인덱스 리스트의 변경 초래
• 갱신되는 레코드가 다중 인덱스의 첫 번째 레코드인 경우, 다중 리스트 인덱스의 삭제나 변경이 필요

다중 리스트의 구현 방법

1. 단순 연결 (원형) 리스트
2. 이중 연결 (원형) 리스트

---

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

공통점

• 원하는 레코드 필드에 대해 인덱스를 유지
• 인덱스는 테이블이나 트리 형태로 구성
• 인덱스 엔트리들을 정렬 가능
• 데이터 레코드의 접근법은 직접/간접 주소법을 사용

차이점