인덱스된 순차 화일 (ISF, Indexed Sequential File) - 2

■ VSM (Virtual Storage Method) 

B+ 트리 인덱스 구조 기법을 이용하는 대표적인 

인덱스된 순차 화일 구성방법

■ VSM의 화일 구조

제어 구간 - 데이터 레코드 저장을 위한 공간 단위

제어 구역 - 일정 수의 제어 구간으로 구성된 공간 단위

순차 세트 - 제어 구역에 대한 인덱스를 저장하는 인덱스 공간

인덱스 세트 - 순차 세트에 대한 상위 인덱스, 다단계로 구성

인덱스 세트 -> 순차 세트 -> 제어 구역 -> 제어 구간(레코드)


■ 제어 구간은 레코드, 추가 레코드 삽입을 위한 자유공간 그리고 제어정보를 포함한다.

제어정보는 레코드에 대한 제어 정보와 자유 공간에 대한 제어 정보를 담고 있으며 제어 구간 뒤쪽부터 저장된다.

■ 제어 구역은 일정 수의 제어 구간으로 구성된다.

제어 구간의 오버플로를 처리하기 위하여 제어 구역 내에 제어 구간을 자유 공간으로 둔다. (화일 생성 시 보통 제어 구역의 마지막 제어 구간 )

■ 순차 세트는 순차 블록으로 구성되고 하나의 순차 블록은 하나의 제어 구역에 1:1로 대응된다. 

<제어 구간의 최대 키값, 포인터>로 구성

■ 인덱스 세트는 인덱스 블록들로 구성된 m-way 탐색 트리 구조, <하위 레벨의 인덱스 블록의 최대 키값, 포인터>로 구성

■삽입과 삭제는 B+ 트리와 유사함, 



■ ISAM (Indexed Sequential Access Method)

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

■ 구성

인덱스 화일 - 마스터, 실린더, 트랙(오름차순) 인덱스

데이터 화일 - 기본 데이터, 오버플로 구역


■ 레코드의 추가 삽입이 많은 경우에는 

독립된 실린더 오버플로 구역을 예비

오버플로 체인이 길어져 성능 저하 -> 주기적인 화일 재구성 필요

■ 물리적 삭제와 삭제표시만 하는 방법이 있다.

삭제표시만 할 경우에는 주기적으로 정리를 해주어야 하기 때문에, 공간낭비와 불필요한 오버플로 레코드를 발생시킨다.


■ 인덱스된 순차 화일의 설계, 구현


■ 고려사항

레코드의 필드 수와 배치

레코드의 키 필드의 크기 (고정or가변, 직접접근 용이한 것)

예상 레코드 추가 삽입 레코드의 수 (약 40%의 자유공간 할당)

주어진 시스템에서의 화일 구현 방법

■ 구현을 위한 결정 요소

데이터 블록의 크기

인덱스 블록의 크기

초기 인덱스 레벨 수

최대 인덱스 레벨

■ 개별 레코드에 대한 직접 검색이 주로 요구되는 응용 -> 밀집 인덱스 유리

■ 순차 검색 주로 -> 데이터 블록을 크게 하거나 기본 구역과 블로킹 인수를 크게 하는 것이 유리

인덱스 3.1

'computer' 카테고리의 다른 글

인덱스된 순차 화일 (ISF, Indexed Sequential File) - 2  (0) 2012.05.26
B+ Tree  (0) 2012.05.26
인덱스된 순차 화일 (ISF, Indexed Sequential File) - 1  (0) 2012.05.26
c++ get() 함수, 개행문자 읽기  (0) 2012.05.07
신호.  (0) 2012.04.30
Modeling (모델링).  (0) 2012.04.30