물리적 데이터베이스 설계에 대하여(2)

04.  파일 조직

파일 조직은 파일 내의 데이터를 보조 기억 장치에 블록과 레코드들로 배치하는 것입니다. 전형적인 파일 조직의 유형으로는 히프 파일(heap file), 순차 파일(sequential file), 인덱스 된 순차 파일(indexed sequential file), 직접 파일(hash file)등이 있습니다.

①  히프 파일(heap file)

히프 파일은 가장 단순한 파일 조직입니다. 일반적으로 레코드들이 삽입된 순서대로 파일에 저장됩니다. 일반적으로 새로 삽입되는 레코드는 파일의 가장 끝에 첨부됩니다. 따라서 삽입이 쉬우며 레코드들의 순서는 없습니다. 원하는 레코드를 찾기 위해서는 모든 레코드들을 순차적으로 접근해야 합니다. 삭제는 원하는 레코드를 찾은 후에 그 레코드를 삭제하고, 삭제된 레코드가 차지하던 공간을 재사용하지 않습니다. 이 공간을 재사용하려면 레코드를 삽입할 때 파일의 끝 대신에 파일 중간에서 빈자리를 찾아야 하므로 레코드 삽입 시간이 증가합니다.

시간이 오래 흐르면 삭제된 레코드들이 차지했던 공간이 재사용되지 않으면서 빈 공간으로 남아 있어서 파일 크기가 증가하게 됩니다. 검색 시엔 빈 공간도 검사하게 되므로 검색 시간이 오래 걸리게 됩니다. 따라서 검색 시에는 빈 공간도 검사하게 되므로 검색 시간이 오래 걸리게 됩니다. 따라서 좋은 성능을 유지하기 위해서는 이프 파일을 주기적으로 재조직할 필요가 있습니다. 파일 재조직 시에는 빈 공간들을 회수해서 자유 공간에 반환합니다.

릴레이션에 데이터를 한꺼번에 적재할 때(bulk loading), 릴레이션에 몇 개의 블록들만 있을 때, 모든 투플들이 검색 위주로 사용될 때 히프 파일이 주로 사용됩니다. 

 

EMPLOYEE 파일을 히프 파일로 저장

►히프 파일의 성능

히프 파일은 질의에서 모든 레코드들을 참조하고 레코드들을 접근하는 순서는 중요하지 않을 때 효율적인 방법입니다.

예를 들어, 다음의 질의는 EMPLOYEE 릴레이션에서 모든 레코드들을 임의의 순서로 검색합니다.

 

SELECT         ∗ 

FROM            EMPLOYEE  ;

 

그러나 특정 레코드를 검색하는 경우에는 히프 파일은 비효율적입니다. 예를 들어, 다음의 질의는 EMPLOYEE 릴레이션에서 EMPNO가 1365인 사원을 검색합니다. 히프 파일에 b개의 블록이 있다고 가정합시다. 원하는 블록을 찾기 위해서는 평균적으로 b/2개의 블록을 읽어야만 합니다.

 

SELECT         TITLE

FROM            EMPLOYEE

WHERE         EMPNO = 1365  ;

 

몇 개의 레코드들을 검색하는 경우에도 비효율적입니다. 이 경우에는 조건에 맞는 레코드를 이미 한 개 이상 검색했더라도 파일의 마지막 블록까지 읽어서 원하는 레코드가 존재하는 가를 확인해야 하기 때문에 b개의 블록을 모두 읽어야 합니다. 다음의 질의는 EMPLOYEE 릴레이션에서 2번 부서에 근무하는 사원 레코드들을 검색하는데, 2번 부서에서 근무하는 사원이 여러 명 있을 수 있으므로 모든 레코드들을 접근해야만 합니다.

 

SELECT         EMPNAME, TITLE

FROM            EMPLOYEE

WHERE         DNO = 2  ;

 

급여의 범위를 만족하는 레코드들을 모두 검색하는 아래의 질의도 EMPLOYEE 릴레이션의 모든 레코드들을 접근해야 합니다.

 

SELECT         EMPNAME, TITLE

FROM            EMPLOYEE

WHERE         SALARY  > =  3000000   AND   SALARY   < =   4000000  ;

 

히프 파일을 갱신하는 데도 시간이 많이 걸립니다.

연산의 유형과 소요 시간

연산의 유형	시간
삽입	효율적
삭제	시간이 많이 소요
탐색	시간이 많이 소요
순서대로 검색	시간이 많이 소요
특정 레코드 검색	시간이 많이 소요

②  순차 파일(sequential file)

순차 파일은 레코드들이 하나 이상의 필드 값에 따라 순서대로 저장된 파일입니다. 레코드들이 일반적으로 레코드의 탐색 키(search key) 값의 순서에 따라 저장됩니다. 탐색 키는 순차 파일을 정렬하는 데 사용되는 필드를 의미합니다. 순차 파일은 레코드들을 순차 접근하는 응용에 적합합니다. 파일의 레코드들이 정렬된 필드를 사용하여 특정 레코드를 검색하는 경우에는 이진 탐색을 사용하여 순차 탐색보다 탐색 시간을 줄일 수 있습니다.

삽입 연산은 삽입하려는 레코드의 순서를 고려해야 하기 때문에 시간이 많이 걸릴 수 있습니다. 삽입 연산은 레코드를 삽입할 위치를 찾은 후에 그 자리에 빈 공간이 있으면 레코드를 삽입하고, 빈 공간이 없는 경우에는 삽입할 레코드를 오버플로 블록에 넣거나, 삽입할 곳 이전의 레코드들을 이전 블록으로 이동하거나, 삽입할 곳 이후의 레코드들을 다음 블록으로 하나씩 이동합니다.

레코드를 삭제하는 연산은 삭제된 레코드가 사용하던 공간을 빈 공간으로 남기기 때문에 히프 파일의 경우와 마찬가지로 주기적으로 순차 파일을 재조직해야 합니다. 기본 인덱스가 순차 파일에 정의되지 않는 한 순차 파일은 데이터베이스 응용을 위해 거의 사용되지 않습니다.

 

EMPLOYEE 파일을 순차 파일로 저장

예를 들어, EMPLOYEE 파일이 EMPNO의 순서대로 저장되어 있을 때 첫 번째 SELECT문은 이진 탐색을 이용할 수 있고, 두 번째 SELECT문의 WHERE절에 사용된 SALARY는 저장 순서와 무관하기 때문에 파일 전체를 탐색해야 합니다.

 

SELECT         TITLE

FROM            EMPLOYEE

WHERE         EMPNO = 1365  ;

 

SELECT         EMPNAME, TITLE

FROM            EMPLOYEE

WHERE        SALARY  > =  3000000   AND   SALARY   < =   4000000  ;

 

연산의 유형과 소요 시간

연산의 유형	시간
삽입	시간이 많이 소요
삭제	시간이 많이 소요
탐색 키를 기반으로 탐색	효율적
탐색 키가 아닌 필드를 사용하여 탐색	시간이 많이 소요

 

 

[IT 공부하기/데이터베이스] - SQL의 SELECT문에 대하여(3)

SQL의 SELECT문에 대하여(3)