[DB] 화일 조직

화일에는 다음과 같은 유형이 있다.

히프 화일

순차 화일

인덱스된 순차 화일

직접 화일

 

히프 화일

가장 단순한 화일 조직이다.

일반적으로 레코드들이 삽입된 순서대로 화일에 저장된다.

삽입 : 새로 삽입되는 레코드는 화일의 가장 끝에 첨부된다.

검색 : 원하는 레코드를 찾기 위해서는 모든 레코드들을 순차적으로 접근해야 함.

삭제 : 원하는 레코드를 찾은 후에 삭제한다. 삭제된 레코드가 차지하는 공간을 재사용하지는 않는다.

좋은 성능을 유지하기 위해 하프 화일을 주기적으로 재조직할 필요가 있다.

하프 화일

모든 레코드들을 참조하고, 레코드들을 접근하는 순서는 중요하지 않을 때 사용한다. (ex : SELECT 문)

특정 레코드를 검색할 때에는 비효율적 -> b개의 블록이 있다고 하면 평균적으로 b/2개의 블록을 읽어야 한다.

한 개 이상의 레코드를 찾을 때에도 비효율적이다. 조건에 맞는 레코드들을 찾아도 b개의 블록을 모두 읽어야 하기 때문이다.

하프 화일 소요 시간

순차 화일

레코드들이 하나 이상의 필드 값에 따라 순서대로 저장된 화일이다.

레코드들이 일반적으로 레코드의 탐색 키(search key) 값의 순서에 따라 저장된다.

탐색 키는 순차 화일을 정렬하는데 사용되는 필드를 의미한다.

삽입 연산은 삽입하려는 레코드의 순서를 고려해야 하기 때문에 시간이 많이 걸릴 수 있다.

삭제 연산은 삭제된 레코드가 사용하던 공간을 빈 공간으로 남기기 때문에 히프 화일의 경우와 마찬가지로 주기적으로 순차 화일을 재조직해야 한다.

기본 인덱스가 순차 화일에 정의되지 않는 한 순차 화일은 데이터베이스 응용을 위해 거의 사용되지 않는다.

순차 화일

탐색 키를 기반으로 탐색할 때에는 이진 탐색을 활용할 수 있다.

탐색 키가 아닌 필드를 사용하여 탐색할 때에는 이진 탐색을 활용할 수 없다.

순차 화일 소요 시간

단일 단계 인덱스

인덱스를 통해서 임의의 레코드를 접근할 수 있는 화일이다.

각 엔트리는 <탐색 키, 레코드에 대한 포인터>

엔트리들은 탐색 키의 오름차순으로 정렬된다.

인덱스

덱스는 데이터 화일과는 별도의 화일에 저장된다.

인덱스의 크기는 데이터 화일의 크기에 비해 훨씬 작다.

하나의 화일에 여러 개의 인덱스들을 정의할 수 있다.

인덱스와 화일

인덱스가 정의된 필드를 탐색 키라고 부른다.

탐색 키의 값들은 후보 키처럼 각 튜플마다 반드시 고유하지는 않는다.

키를 구성하는 애트리뷰트뿐만 아니라 어떤 애트리뷰트도 탐색 키로 사용될 수 있다.

인덱스의 엔트리들은 탐색 키 값의 오름차순으로 저장되어 있으므로 이진 탐색을 이용할 수도 있다.

 

기본 인덱스(primary index)

탐색 키가 데이터 화일의 기본 키인 인덱스를 기본 인덱스라고 부른다.

기본 인덱스는 기본 키의 값에 따라 정렬된 데이터 화일에 대해 정의된다.

기본 인덱스는 흔히 희소 인덱스로 유지할 수 있다.

각 릴레이션마다 최대한 한 개의 기본 인덱스를 가질 수 있다.

기본 인덱스