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

인덱스된 순차 화일의 구조

• 인덱스된 순차 화일

  

  • 순차 데이터 화일 + 인덱스
  • 순차 데이터 화일
    • 키 값에 따른 레코드 순차적 정렬
    • 레코드 전체에 대한 순차 접근 지원
  • 인덱스 화일
    • 화일의 레코드들에 대한 키 값, 포인터 저장
    • 개별 레코드에 대한 직접 접근 지원
  • 각 화일은 block으로 구성
    • 인덱스 화일 : 인덱스 블록, 트리 구조
    • 순차 데이터 화일 : 데이터 블록, 연결리스트로 논리적 순서 유지
    • 블록은 순차적으로 저장된 키 값, 자유공간 포함

• 구조

  • 마스터 인덱스 : 최상위 레벨 인덱스 블록
  • 인덱스 엔트리 : <최대 키 값, 포인터>
  • 자유 공간 : 레코드 추가 삽입을 위한 예비 공간 → 화일 생성 시 각 블록에 분산 배치
    

• 삽입

  • 오버플로우 났을 때 → 절반 나눠 분할 후 인덱스 블록에 최댓값 추가

    

    

B+-트리

• B+-트리
  • 인덱스 세트 + 순차 세트
  • B-트리의 순차 탐색 성능 향상
• 인덱스 세트
  • 리프 이외의 노드, 리프 노드를 접근하는 경로로만 이용
  • 키 값만 저장
• 순차 세트
  • 리프 노드
  • <키 값, 데이터 레코드의 주소>
  • 키 값의 순서에 따라 모든 레코드를 순차 접근하는 데 이용

m차 B+-트리

• 같은 수의 키 값을 가지고 있는 B-트리에 비해 B+-트리의 레벨이 낮다.

• 루트 : 0, 2~m개 사이의 서브트리

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

• 한 노드의 키 값들은 오름차순

• index key값과 data key값이 같을 수 있다

• 리프노드 구조

• 인덱스와 리프노드 구조 다름

  • 인덱스 구조 <n, P0, K1, P1, K2, P2, … , KN, PN>
    
  • 리프노드 구조 <q, <K1, A1>, … , <Kq, Aq>, Pnxt>
    

• 삽입

  

• 삭제

  

  

VSAM 화일

• VSAM

  

  • Virtual Storage Access Method
  • B+-트리 인덱스 구조 기법을 이용 → 인덱스된 순차 화일 구성
  • 구조
    1. 제어 구간 : 데이터 레코드 저장을 위한 공간 단위
    2. 제어 구역 : 일정 수의 제어 구간으로 구성된 공간 단위
    3. 순차 세트 : 제어 구역에 대한 인덱스를 저장하는 인덱스 공간
    4. 인덱스 세트 : 순차 세트에 대한 상위 인덱스, 다단계로 구성

• 제어 구간 control interval

  

  • 하나 이상의 레코드를 저장할 수 있는 데이터 블록으로 구성
  • 자유 공간 : 추가 레코드 삽입 목적
  • 키 값에 따라 물리적 순차로 저장 및 유지
  • 제어 정보 포함
    • 레코드, 자유 공간에 대한 제어 정보
    • 제저 구간 뒤쪽에 저장

• 제어 구역 control area

  • 일정 수의 제어 구간으로 구성
  • 제어 구간 오버플로 처리 → 자유 공간 예비

• 순차 세트

  • 하나의 순차 블록은 하나의 제어 구역에 1:1 대응
  • 순차 블록의 각 엔트리는 그 제어 구역에 속하는 제어 구간과 1:1 대응

• 인덱스 세트

  • 인덱스 블록으로 구성된 m-원 탐색 트리 구조

• 키 순차 화일 지원

  • 제어 구간 내 레코드들은 키 값 순으로 물리적으로 저장
  • 제어구간들의 키 값 순서는 순차세트의 순차 블록 엔트리로 유지
  • 순차 세트의 순차 블록 순서는 최 하위 레벨의 인덱스 블록으로 유지
  • 화일 생성이 자유공간 분산 배치

• 순차 접근 + 직접 접근

  • 순차 접근 : 인덱스 세트 탐색
  • 직접 접근 : B+-트리와 유사, 레코드 접근을 위해 인덱스 세트 → 순차 세트 → 제어 구간 접근

• 삽입

  • 제어 구간 내 레코드들 이동
  • 자유 공간 없을 경우 → 제어 구간 절반으로 분할
  • 제어구간이 없을 경우 → 화일의 자유 제어 구역으로 절반 이동

• 삭제

  • 레코드 식별 후 물리적으로 삭제
  • 제어 구간 최대 키 값 삭제 → 제어 구간에 대한 순차 블록 엔트리의 키 값 조정
    
  • 제어 구역 최대 키 값 삭제 → 제어 구간에 대한 순차 블록 엔트리의 키 값 + 인덱스 세트의 엔트리 조정
    

ISAM 화일

• ISAM

  

  • 인덱스된 순차 화일을 저장장치의 물리적 특성 실린더&트랙 기반으로 구현
  • 인덱스 화일 + 데이터 화일
  • 인덱스 화일
    • 마스터 인덱스
    • 실린더 인덱스
    • 트랙 인덱스
  • 데이터 화일
    • 기본 데이터 구역
    • 오버플로 구역

• 마스터 인덱스

  • 최상위 레벨의 인덱스
  • 각 엔트리 : <최대 키 값, 포인터>
  • 해당 키 값을 가진 실린더 인덱스 엔트리 가리킴

• 실린더 인덱스

  • 데이터가 저장되어 있는 기본 데이터 구역(실린더)에 대한 포인터
  • <최대 키값, 실린더 번호>

• 트랙 인덱스

  • 실린더 내 데이터 레코드들이 저장되어있는 트랙에 대한 인덱스
  • 실린더의 첫 번쨰 트랙(트랙0)에 저장
  • <최소 키 값, 트랙 번호>

• 삽입

  

  • 트랙에서의 키 값 오름차순 정렬
  • 오버플로 구역(트랙)을 사용
  • 트랙 인덱스에 오버플로 인덱스 추가 <키 값, 오버플로 포인터(op)>
  • 오버플로 레코드 : <레코드, 같은 트랙의 다음 오버플로 레코드에 대한 포인터>
  • 오버플로 체인 길어짐 → 성능 저하 → 주기적 화일 재구성 필요

• 삭제

  1. 삭제할 레코드를 물리적으로 삭제
     • 기본 데이터 구역에 있는 경우
       • 삭제할 레코드 뒤에 있는 레코드들 한 자리씩 왼쪽으로
       • 필요한 경우 오버플로 트랙의 레코드를 기본 구역으로 이동 → 오버플로 인덱스 엔트리 조정
         
     • 오버플로 구역에 있는 경우
       • 연결 리스트 적절히 조정
       • 체인에 대한 오버플로 인덱스 엔트리 조정
  2. 삭제할 레코드를 물리적 삭제 X 삭제 표시만 O
     • 검색 시 삭제 표시된 레코드는 생략
     • 일정한 주기로 삭제 표시된 레코드 정리 필요 → 공간 낭비, 불필요한 오버플로 레코드 발생
       

인덱스된 순차 화일의 설계

• 화일 설계 시 고려 사항

  • 레코드의 필드 수와 배치
  • 레코드의 키 필드와 크기 → 고정 길이, 가변 길이 레코드 모두 수용 가능하도록 → 화일에 대한 직접 접근이 용이한 키 선택
    
  • 예상 레코드 추가 삽입 레코드 수 → 40%의 자유 공간 할당
    
  • 주어진 시스템에서의 화일 구현 방법

• 구현을 위한 결정 요소

  • 데이터 블록 크기
  • 인덱스 블록 크기
  • 초기 인덱스 레벨 수
  • 최대 인덱스 레벨

• 응용

  • 개별 레코드에 대한 직접 검색 주로 요구 → 밀집 인덱스 사용
    
  • 순차 검색이 주로 요구 → 데이터 블록 크게 → 기본 구역과 블로킹 인수 크게
    

• 인덱스 설계

  • 인덱스 블록의 참조 능력 : 인덱스 분기율

    

    분기율 ⬆️ 인덱스 레벨 ⬇️ 검색 속도 ⬆️
    

• 예시