[파일처리] 다중 키 파일

다중 키 파일의 개념

단일 키 파일

• 지금까지 살펴 본 파일들로 기본 키(primary key) 사용
  • 순차파일: 기본키에 따라 정렬된 순차접근지원
  • 직접피일: 기본키에 따라 해싱결과로 직접접근지원
  • 인덱스된 순차파일: 기본키에 대해 만들어진 인덱스를 통해 직접 접근과 키 값에 따른 순차 접근 지원

다중 키 파일

• 하나의 데이터 화일에 대해 여러 다른 탐색 키를 이용한 여러 개의 접근 경로를 제공
  
• 다중키: 학번, 학과별, 입학년도별, 지도교수별
• 사용되는 키는 보조 키(secondary key)가 됨
• 보조키는 레코드가 유일하지 않을 수도 있음

구현방법

• 데이터 중복 이용하여 각 응용에 맞는 파일을 각각 구성

  • 학번을 키로 하는 직접 화일 구성,학과를 통한 순차 화일 구성, 이름을 키로 하는 인덱스된 순차 화일 구성
  • 접근 경로만 다르고 화일의 데이터 내용은 모두 같음(중복) 기억 공간 증가
  • 데이터 갱신 시 일관성(consistency) 유지가 어렵고 시간이 많이 걸림 데이터 무결성(integrity)에 손상을 가져올 수 있음

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

  • 역 파일(inverted file) : 인덱스 이용
  • 다중리스트 파일(multilist file) : 레코드 사이의 리스트 이용

역 파일

역 파일 구조

• 역 인덱스를 이용하는 구조
• 역(inversion) : 인덱스와 데이터 레코드 파일을 연결

역 인덱스

• 데이터 파일에 있는 키 필드값을 인덱스 키로 포함
• 인덱스 엔트리 = (키 값, 레코드 포인터)
• 파일은 키 필드에 대해 전도(도치)되었다고 함
• 많은 DBMS의 물리적 데이터베이스 구조에 사용

학생 데이터 파일

레코드 주소를 이용한 주민등록번호 역 인덱스

역 인덱스의 구성

• 주민등록번호(인덱스)들이 정렬되어 있다면

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

• 역 인덱스에서 정렬된 키의 순서 ≠ 레코드의 순서

  • 데이터파일에 레코드가 삽입되면: 역인덱스도갱신
  • 파일 관리 비용이 많이 듦

• 인덱스구조

  • 테이블: 정적 구성
  • 트리: 동적 구성,검색시간은 단축되나 처리가 더 복잡

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

  • 학번을 기본 키로 하는 인덱스된 순차 화일에서
  • 학번, 주민등록번호로 직접 접근이 가능하고, 학번으로 순차 접근이 가능

주민등록번호를 이용한 역 인덱스

역 화일의 종류

• 역(inversion)
  • 데이터 파일에서 키 값 제거하여 역 인덱스에만 위치
• 역 인덱스가 만들어지는 수에 따라
  • 완전 역 화일 (Completely inverted file): 데이터 레코드의 모든 필드에 대한 역 인덱스
  • 부분 역 화일 (Partially inverted file): 몇 개의 필드에 대해서만 역 인덱스 구성

역 인덱스 구성 방법의 대안

• 역 인덱스의 키 값을 데이터 레코드에서 제외했을때
  주민등록번호를 역 인덱스로 갖는 부분 역 파일에서
  "학번이 2918인 학생의 주민번호는 ?"

1. 데이타 화일: 학번 2918인 학생 레코드의 주소 검색
2. 역 인덱스: 주민등록번호 역 인덱스에서 순차 탐색하여 레코드 주소 포함하는 주민등록번호 찾음

-> ~~가 비효율적

• 직접주소기법
  • 인덱스 엔트리 = (보조 키, 레코드 주소)
  • 데이터 파일의 물리적 변화에 대해 역 인덱스 화일이 영향을 받음
• 대안
  • 간접주소기법이용
  • 인덱스 엔트리 = (보조 키, 기본 키)
• 키
  • 기본 키 (primary key) : 유일 식별, 물리적 순서 결정
  • 보조 키 (secondary key) : 레코드 접근을 위한 필드

기본 키를 이용한 주민등록번호 역 인덱스 구조의 변형

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

• 학과 이름에 대한 역 인덱스

• 고려할 점은?

  • 키 값 엔트리(학번)들을 정렬할 것인가?
  • 인덱스는 어떻게 구성할 것인가? (테이블 혹은 트리)
  • 주소 기법은? (직접 혹은 간접)

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

  1. 가변 길이 인덱스 엔트리로 관리
  2. 고정길이 인덱스 엔트리로 관리
     최대수의 엔트리를 수용할 수 있는 공간을 할당
  3. 인덱스 엔트리를 중복시켜 관리
     역 인덱스의 엔트리 = (보조키 값, 하나의 주소) 쌍

• 역 화일의 장점은 인덱스만으로도 질의 응답이 가능하다는 것! (다 되는 건 아님~)

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

역 화일의 연산

• 레코드의 삽입
  - 데이터 파일: 레코드 삽입
  • 역인덱스화일: 기존 인덱스 엔트리에 포인터만 첨가하거나 새로운 인덱스 엔트리 삽입
• 레코드의 삭제
  • 데이터 파일: 레코드삭제
  • 역 인덱스 파일: 포인터 제거,공백이면 엔트리 제거
• 레코드의 갱신
  • 데이터 파일: 레코드 갱신 작업
  • 역 인덱스 화일: 갱신 영향을 받은 모든 역 인덱스 화일에 삽입, 삭제 연산을 수행
  • 학번이 3241인 학생이 토목과에서 컴퓨터과로 전과하면 학과 인덱스에서 토목과의 3241 삭제하고 컴퓨터과에 3241 삽입

다중 리스트 파일

• 현재 많은 상용 DBMS의 물리적 DB구조의 기초
• 각 보조키에 대해 하나의 다중 리스트 파일 유지
• 다중 리스트 인덱스

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

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

• 역인덱스
  • (키값,그 키 값의 모든 레코드들에 대한 포인터)
  • 인덱스 엔트리: 여러개의 포인터값을 갖는 가변길이
• 다중리스트인덱스
  • (키 값, 하나의 레코드에 대한 시작 포인터)
  • 나머지 레코드
    → 데이터 파일에서 연결리스트 구조로 유지
• 인덱스 엔트리: 하나의 포인터 값만을 갖는 고정길이

역화일과 다중 리스트 파일의 차이점

• 역화일
  - 역인덱스를구성 → 데이터 파일구조에 영향 없음
• 다중 리스트 파일
  - 다중 리스트 인덱스 구성 → 데이타화일구조변경필요
  • 데이터 파일: 인덱스의 리스트를 위한 포인터 필드 추가
  • 데이터 레코드의 포인터 필드의 수 = 인덱스 수
• 인덱스 엔트리: 하나의 포인터 값만 갖는 고정길이

학과, 입학년도 다중 리스트 인덱스

• 학과에 대한 다중 리스트 인덱스
  
• 입학년도에 대한 다중 리스트 인덱스
  

학과, 입학년도, 다중리스트에 대한 학생 데이터 파일

다중리스트 파일의 구조

• 데이터 레코드 구조
  

• 다중 리스트 인덱스 설계 시의 고려사항
  - 인덱스 키 값들을 정렬할 것인가?

  • 인덱스의 구성 방법은? 테이블 혹은 트리?
  • 주소법 : 직접/간접
  • 리스트의 데이타 레코드의 정렬 여부

레코드의 검색과정

• 질의유형의 예
  1. 컴퓨터공학과에는 몇 명의 학생이 있는가 ?
  2. 컴퓨터공학과에 속한 학생의 학번을 모두 검색하라.
  3. 학번이 6861인 학생의 소속이 컴퓨터 공학과인가 ?
• 처리과정
  • 역화일:인덱스만접근해도가능
  • 다중리스트 : 데이타 레코드를 접근해야 가능
    • (1 대안) 인덱스 엔트리에 리스트 길이 정보를 가짐
• 다중 리스트 인덱스의 변형
  • 인덱스 엔트리
    = (키값,첫번째레코드의포인터,리스트길이)

학과, 입학년도에 대한 다중리스트 인덱스

리스트 길이 정보의 활용

• 특정 유형 질의에 대한 최적 접근 경로 선정 시 이용
  - (질문) "입학년도 = 01, 학과 = ‘컴퓨터’인 학생의 이름을 검색하세요"
• 처리 방법은?
  1. 학생 데이터 파일의 순차적 탐색
  • ?개 레코드 접근
  2. 입학년도 다중 리스트 인덱스 사용
  • ?개 레코드 접근
  3. 학과 다중리스트 인덱스 사용
  • ?개 레코드 접근
• 선택
  • 학과 = 컴퓨터인 레코드 접근해서
  • 4개의 레코드 : 입학년도 필드 검사

다중 리스트 파일의 연산

• 레코드의 삽입
  • 데이타 파일: 새 레코드를 삽입
  • 인덱스 참조 → 데이타 화일의 연결리스트에 연결
  • 인덱스에 없으면 → 새 인덱스 엔트리로 삽입
• 레코드의 삭제
  • 데이타 화일: 연결리스트에서 하나의 노드 삭제
  • 인덱스: 연결리스트에서 유일 멤버이면 → 인덱스 삭제
• 레코드의 갱신
  • 데이터 파일: 레코드 필드 값이 변경되면
  • 다중 리스트 변경(필요 시 다중 리스트 인덱스도 갱신)
• 다중 리스트의 구현 방법
  • 단순/이중 연결 (원형) 리스트

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

• 공통점
  • 모든 보조키에 대한 인덱스 유지
  • 인덱스는 테이블,트리 형태로 구성
  • 인덱스 엔트리들은 정렬 가능
  • 데이터 레코드는 직접/간접주소법 사용