[파일처리] 다중 키 화일

다중 키 화일

• 다중 키 화일
  • 하나의 데이터 화일에 여러 종류의 상이한 탐색키를 이용한 여러 개의 접근 경로 제공
  • 탐색 키 = 기본 키 + 보조 키
    • 기본 키 : 하나의 레코드 식별
    • 보조 키 : 기본적으로 여러 개의 레코드 식별
• 화일의 복수 접근 경로
  1. 데이터 중복 이용
     • 동일한 내용의 화일 제공
     • 중복 저장 → 공간 낭비
     • 데이터 일관성 유지 곤란
     • 데이터 모순성 → 데이터 유효성 문제 발생
     • 데이터 무결성 손상
  2. 하나의 화일의 복수의 접근 경로 지원 ← 다중키 화일
     • 접근 경로 : 인덱스로 구축 → 이원 탐색 트리, B-트리, B+-트리
       
     • 인덱스와 레코드 사이 리스트 이용 → 역 화일, 다중리스트 화일
       

역 화일

• 구조

  • 인덱스 이용
  • 도치 (inversion, 역) → 인덱스 값으로 데이터 레코드 화일을 도치
    

• 역 인덱스

  • 인덱스 키 값 → 인덱스 엔트리로 모두 포함
  • 각 엔트리 : 인덱스 키 값을 가지고 있는 모든 레코드들에 대한 포인터 포함
  • 인덱스 엔트리 = <인덱스 키 값, 레코드 포인터>
  • DBMS의 물리적 DB구조에서 많이 이용

• 역 인덱스 구성

  • 인덱스를 1차원 정렬시켜 유지 → 이원탐색기법 사용 가능 O(logN)
    
  • 정렬된 키 순서 ≠ 레코드 순서
  • 트리와 같은 동적 구조로 구성 → 검색 시간 빠름 / 삽입 삭제 복잡
    
  • 보통 인덱스된 순차 화일이나 직접 화일 위에 구성

• 역 화일의 종류

  • 역의 본질
    • 인덱스 키 값 제거하여 역 인덱스 엔트리에 위치
    • 인덱스 키 필드가 제거
    • 일반적으로 인덱스 키 필드를 제거하지 않고 역 인덱스 구성
  • 역 인덱스가 만들어지는 수에 따라
    1. 완전 역 화일
       • 모든 필드에 대해 역 인덱스 구축
       • 역 인덱스 키 필드 값들을 모두 제거 → 완전 역 화일은 데이터 레코드 화일이 논리적으로 존재 X
       • 레코드의 어떤 필드로도 데이터 레코드에 대한 접근 경로 제공
    2. 부분 역 화일
       • 몇 개의 주요 필드에 대해서만 역 인덱스 구성

• 효율적인 역 인덱스 구성

  • 데이터 화일에서 학번 2908로 학생 레코드 주소 직접 검색
  • 주민번호 역 인덱스에서 레코드 주소 포함하고 있는 인덱스 엔트리 탐색
  • 키
    • 기본 키 : 유일 식별, 물리적 순서 결정
    • 보조 키 : 레코드 접근을 위한 필드
  • 대안
    • 간접 주소 기법 이용
    • 역 인덱스 엔트리 = <인덱스 키, 기본 키>
  • 장점
    • 데이터 화일의 물리적 재구성(재조직) 가능 → 역 인덱스 화일에 영향 X
      
  • 인덱스 엔트리에 복수의 포인터를 포함시키는 구현

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

    2. 고정 길이 인덱스 엔트리로 관리

       → 최대 수의 기본 키 값을 수용할 수 있는 공간 할당

    3. 인덱스 엔트리를 중복시켜 관리

       → 역 인덱스 엔트리는 <인덱스 키 값, 하나의 기본 키> 로만 구성

  • 복수의 포인터 정렬시켜 유지하면
    • 레코드 검색 신속
    • 레코드 갱신 시 추가 부담

• 역 인덱스 응용

  인덱스 만으로 질의 처리 가능

  • 주민번호가 20010921인 학생이 있는가?

  • 컴퓨터학부에는 몇 명의 학생이 있는가?

  • 컴퓨터학부에 속하는 학생의 학번들을 나열하라

  • 주민번호가 20010921인 학생의 학번은 무엇인가?

    ex. ‘학번’ 키로 하는 인덱스된 순차화일 주고, ‘주민번호’ 인덱스 키로 하는 역 인덱스 구성

    → ‘학번’, ‘주민번호’에 의한 직접 접근

    → ‘학번’에 의한 순차 접근도 지원

    ‘주민 번호’를 키로 만든 역 인덱스에서 키 엔트리 정렬시켜 유지

    → ‘주민번호’ 순으로 순차 접근 가능

• 예제

  

  → ‘주민번호’와 데이터 레코드의 ‘주소’쌍으로 구성한 직접 주소 기법

  • ‘학번’이 3358인 학생의 ‘주민번호’는 무엇인가?
    1. 데이터 화일에서 ‘학번’이 3358인 학생 레코드의 주소를 검색
    2. ‘주민번호’ 역 인덱스에서 이 레코드 주소를 포함하고 있는 인덱스 엔트리 탐색 (순차 검색 필요 : 비효율적)

        ← ‘주민번호’값은 데이터 레코드에 없기 때문
        

    

    → 학번을 이용한 주민 번호 역 인덱스 (보조키, 기본키 쌍) 간접 주소 기법

  • 레코드 주소 대신 기본 키 사용

    → 역 인덱스 화일과 데이터 레코드 화일은 독립적 X

    → 기본 키를 기초로 한 데이터 레코드 화일: 물리적 재구성, 재조직

    → 기본 키 값을 통해서만 접근 가능
    

• 역 화일의 연산

  1. 연산
     • 데이터 화일, 인덱스 화일 포함 → 고 비용
  2. 삽입
     • 데이터 화일 : 레코드 삽입
     • 모든 역 인덱스 화일 수정 → 인덱스 엔트리로 삽입 → 레코드 포인터만 첨가
       
  3. 삭제
     • 데이터 화일 : 레코드 삭제
     • 모든 역 인덱스 화일을 수정 → 포인터 삭제 후 공백 되면 인덱스 엔트리 제거
       
  4. 갱신
     • 데이터 화일에서 레코드 갱신
     • 갱신 영향을 받은 모든 역 인덱스 화일에 삽입, 삭제 연산 수행

다중리스트 화일

• 다중 리스트 화일

  

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

• 데이터 레코드 구조

  

• 설계시 고려사항

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

• 레코드 검색 과정

  • 역 화일은 인덱스만 접근해도 가능
  • 다중 리스트는 데이터 레코드를 접근해야 가능 → 대안 : 인덱스 엔트리에 리스트 길이 정보 추가 → 인덱스 엔트리 = <인덱스 키 값, 첫 번째 레코드의 포인터, 리스트 길이>
    

• 리스트 길이 정보 활용

  • 입학년도 = 01이고 학과 = 컴퓨터인 학생의 이름을 검색하라
  • 처리 방법

    1. 학생 데이터 화일 순차적 검색

       → 20개의 레코드 접근

    2. 학과 다중 리스트 인덱스 사용

       → 4개의 레코드 접근

    3. 입학년도 다중 리스트 인덱스 사용

       → 7개의 레코드 접근

• 삽입

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

• 삭제

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

• 갱신

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

• 구현 방법

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

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

• 역 인덱스
  • <인덱스 키 값, 키 값을 가진 모든 레코드들에 대한 포인터>
  • 인덱스 엔트리 : 여러 개의 포인터 값을 갖는 가변길이
• 다중 리스트 인덱스
  • <인덱스 키 값, 키 값을 가진 첫 번째 레코드에 대한 포인터>
  • 나머지 레코드는 기본 데이터 레코드 화일에서 하나의 연결 리스트로 유지
  • 헤드만 유지하는 디렉터리 역할
  • 인덱스 엔트리 : 하나의 포인터 값을 갖는 고정길이
• 구조
  • 역 화일 → 역 인덱스 구성해도 데이터 화일 구조에 영향 X
    
  • 다중 리스트 화일 → 다중 리스트 인덱스의 구성은 데이터 화일 구조의 변경 필요 → 인덱스 리스트 구축을 위한 링크 필드 추가 필요 → 데이터 레코드의 링크 필드 수 = 다중 리스트 인덱스 수
    
• 공통점
  • 원하는 레코드 필드에 대해 인덱스 유지
  • 인덱스는 테이블이나 트리 형태로 구성
  • 인덱스 엔트리들 정렬 가능
  • 데이터 레코드의 접근법 : 직접/ 간접 주소법 이용
• 차이점