[FP] 07. 인덱스된 순차 화일

인덱스된 순차 화일

‘순차 데이터 화일’ + ‘인덱스 화일’로 구성

각 화일은 블록으로 구성

블록은 순차적으로 저장된 키 값과 자유 공간을 포함

 

순차 데이터 화일

• 키 값에 따라 레코드들이 순차적으로 정렬
• 레코드 전체에 대한 순차 접근을 지원
• 데이터 블록으로 구성
• 데이터 블록들은 연결 리스트로 논리적 순서를 유지

인덱스 화일

• 화일의 레코드들에 대한 키 값과 포인터를 저장
• 개별 레코드에 대한 직접 접근을 지원 
• 인덱스 블록으로 구성
• 트리 구조를 형성

마스터 인덱스

• 인덱스 트리의 최상위 레벨 인덱스 블록

인덱스 엔트리의 구성

• <최대 키 값, 포인터>
• 포인터는 해당 키 값을 최대 키 값으로 갖는 다음 레벨의 인덱스 블록이나 데이터 블록에 대한 주소

자유 공간

• 레코드의 추가 삽입을 위한 예비 공간
• 화일을 생성할 때, 각 블록에 분산 배치

---

---

B+트리

‘인덱스 세트’ + ‘순차 세트’로 구성 / 순차 탐색의 성능 향상이 목적

 

인덱스 세트

• 리프 이외의 노드로 구성
• 키 값만 저장
• 리프 노드를 접근하는 경로로만 이용

순차 세트

• 리프 노드들로 구성
• <키 값, 데이터 레코드의 주소> 쌍
• 키 값의 순서에 따라 모든 레코드를 순차 접근하는데 이용

---

m차 B+트리의 특성

---

B+트리와 B-트리의 차이

• 인덱스 세트와 순차 세트의 구분이 있으며 구조가 다르다.
• 인덱스 세트는 리프 노드에 있는 키 값을 찾는 경로로만 이용, 인덱스 세트의 키 값은 순차 세트에 다시 나타남
• 순차 세트는 실제 데이터 레코드를 찾는데 이용 (키 값과 그 키 값을 가진 레코드에 대한 포인터가 저장)
• 인덱스 세트의 노드와 순차 세트의 노드에 들어갈 수 있는 키의 개수가 다름 (구조가 다르기 때문에)
• 순차 세트의 모든 노드는 링크로 연결 : 화일 레코드의 순차 접근이 효율적

---

B+트리의 성능

• 검색은 항상 리프 노드까지 내려가야 종료 (인덱스에서 발견되어도 계속 진행)
• 키 값이 인덱스 노드에서 발견되어도 실제 리프 노드에는 없을 수 있다.
• 같은 수의 키 값을 가진 B-트리에 비해 B+트리는 레벨이 낮아질 수 있다. => 인덱스 노드는 레코드 포인터를 저장하지 않아 노드 내 공간이 절약되기 때문
• 순차 검색은 연결리스트를 순회하므로 B-트리에 비해 효율적이다. => 직접 처리와 순차 처리를 모두 필요로 하는 응용에서 효율적이다.

---

VSAM 화일

VSAM : Virtual Storage Access Method

B+트리 인덱스 구조 기법을 이용하는 대표적인 인덱스된 순차 화일 구성 방법

 

VSAM 화일의 구조

• 제어 구간 : 데이터 레코드 저장을 위한 공간 단위
• 제어 구역 : 일정 수의 제어 구간으로 구성된 공간 단위
• 순차 세트 : 제어 구역에 대한 인덱스를 저장하는 인덱스 공간
• 인덱스 세트 : 순차 세트에 대한 상위 인덱스, 다단계로 구성

---

제어 구간

• 하나 이상의 레코드를 저장할 수 있는 데이터 블록으로 구성
• 추가 레코드 삽입을 위해 자유 공간을 유지
• 레코드는 키 값에 따라 물리적으로 저장되고 유지된다.
• 제어 정보를 포함 (레코드 제어 정보, 자유 공간 제어 정보), 제어 구간 뒤쪽부터 저장됨

제어 구역

• 일정 수의 제어 구간으로 구성
• 제어 구간의 오버플로를 처리하기 위하여 제어 구역 내에 제어 구간을 자유 공간으로 예비 (보통 마지막 제어 구간)

순차 세트

• 순차 블록으로 구성, 하나의 순차 블록은 하나의 제어 구역에 1:1로 대응
• 순차 블록의 각 엔트리는 그 제어 구역에 속하는 제어 구간과 1:1로 대응
• 순차 블록의 엔트리는 <제어 구간의 최대 키 값, 포인터> 쌍으로 구성, 키 값 순으로 저장된다.
• 제어 구역에 속하는 제어 구간들의 논리적 순서는 순차 블록의 엔트리 순서에 의해 유지 (물리적 순서 X)
• 순차 세트 내에서의 순차 블록들은 제어 구역을 순차로 유지할 수 있도록 체인으로 연결 (순차 접근 용이)

인덱스 세트

• 인덱스 블록들로 구성된 m-원 탐색 트리 구조
• 인덱스 블록의 엔트리는 <차하위 레벨의 인덱스 블록의 최대 키 값, 포인터> 쌍으로 구성
• 최하위 레벨의 인덱스 블록 엔트리들은 각각 하나의 순차 블록을 가리킨다.
• 하나의 순차 블록 내에서는 엔트리들이 키 값의 크기 순으로 저장, 결과적으로 화일 전체가 키 순차로 저장됨

키 순차 화일을 지원 : 레코드들을 키 값 순으로 저장하고 유지

• 제어 구간 내에서 레코드들을 키 값 순서로 물리적으로 저장
• 제어 구역에 속한 제어 구간들의 키 값 순서는 순차 세트의 순차 블록 엔트리로 유지
• 순차 세트의 순차 블록 순서는 최하위 레벨의 인덱스 블록으로 순차를 유지
• 화일을 생성할 때, 자유 공간을 분산 배치 : 제어 구간 내에 자유 공간 할당, 제어 구역 내에 자유 제어 구간을 할당

---

순차 접근

• 인덱스 세트를 탐색하여 첫 번째 제어 구역에 대한 순차 세트의 첫 번째 순차 블록을 식별
• 연결된 순차 세트의 순차 블록들을 체인으로 따라가며 차례로 모든 제어 구간을 접근

직접 접근

• B+트리와 유사
• 레코드 접근을 위해서는 인덱스 세트 -> 순차 세트 -> 제어 구간 순으로 접근

---

레코드 삽입

• 해당 제어 구간을 식별 후 레코드 삽입, 삽입되는 레코드의  순차 유지를 위해 제어 구간 내의 레코드들을 이동
• 제어 구간이 꽉 차서 자유 공간이 없을 때는 제어 구간을 분할 
  -> 제어 구역의 자유 제어 구간으로 레코드의 절반을 이동, 순차 블록의 엔트리 조정으로 제어 구간의 순서를 유지
• 제어 구역이 꽉 차서 자유 제어 구간이 없을 때는 제어 구역을 분할 
  -> 화일의 자유 제어 구역으로 레코드 절반을 이동, 순차 세트 체인을 조정하여 제어 구역의 순서를 유지

레코드 삭제

• 해당 레코드를 식별하고 물리적으로 삭제, 나머지 레코드들의 순차 유지를 위해 제어 구간 내의 레코드를 이동
• 제어 구간의 최대 키 값을 삭제할 때는 그 제어 구간에 대한 순차 블록 엔트리의 키 값을 조정
• 제어 구역의 최대 키 값을 삭제할 때는 그 제어 구역에 대한 순차 블록 엔트리의 키 + 인덱스 세트의 엔트리를 조정

---

ISAM 화일

IBM의 Indexed Sequential Access Method

인덱스된 순차 화일을 저장 장치의 물리적 특성(실린더와 트랙)을 기반으로 구현하는 방법

 

인덱스 화일 + 데이터 화일 로 구성

• 인덱스 화일 : 마스터 인덱스 + 실린더 인덱스 + 트랙 인덱스
• 데이터 화일 : 기본 데이터 구역 + 오버플로 구역

---

ISAM 화일의 예시

• 기본 데이터 구역은 6개의 실린더로 구성
• 각 실린더는 4개의 트랙을 가지고 있다. (1개는 오버플로 구역) - 트랙당 5개의 레코드 수용 / 트랙당 40%의 자유 공간
• 트랙 인덱스 : 실린더 내에 저장된 데이터 트랙에 대한 인덱스
  각 실린더의 첫 번째 트랙(트랙 0)에 저장되어 있다. 각 엔트리는 <최소 키 값, 트랙 번호> 쌍으로 구성
• 실린더 인덱스 : 기본 데이터 구역(실린더)에 대한 포인터를 가짐
  각 엔트리는 <최대 키 값, 실린더 번호> 쌍으로 구성
• 마스터 인덱스 : 최상위 레벨의 인덱스 (화일 처리시 메모리에 상주
  각 엔트리는 <최대 키 값, 포인터>로 구성
  포인터는 해당 키 값을 가진 실린더 인덱스 엔트리를 가리킴

---

인덱스된 순차 화일의 설계

화일 설계 시 고려 사항

1. 레코드의 필드 수와 배치
2. 레코드의 키 필드와 크기 (고정, 가변 길이 레코드 모두 수용할 수 있도록, 직접 접근이 용이한 키를 선택)
3. 예상 레코드 추가 삽입 레코드 수 (일반적으로 40%의 자유 공간을 할당)
4. 주어진 시스템에서의 화일 구현 방법

구현을 위한 결정 요소

1. 데이터 블록의 크기
2. 인덱스 블록의 크기
3. 초기 인덱스 레벨 수
4. 최대 인덱스 레벨

위 4개의 실제 값은 시스템 본래의 블록 크기, 현재 혹은 예상되는 데이터 레코드 수. 화일의 용도 등에 따라 결정

 

직접 검색이 주로 요구되는 응용 : 밀집 인덱스를 사용하는 것이 유리

순차 검색이 주로 요구되는 응용 : 데이터 블록을 크게 하거나 기본 구역과 블로킹 인수를 크게 하는 것이 유리

 

인덱스 분기율

인덱스 블록의 참조 능력, 인덱스 설계 시 가장 중요한 매개변수

 

---