[데이터베이스/Database] 힙 파일, 정렬 파일, 해시 기반 파일

페이지: 데이터를 읽고 쓰는 기본 단위 (대부분 4KB/8KB, 데이터베이스에서 주로 사용)

블락: 메인메모리와 디스크간의 데이터 입출력의 기본 단위. 몇 개의 페이지들로 구성. (운영체제에서 주로 사용)

 

데이터베이스 연산 처리시간

: 페이지들의 입출력 시간 + CPU 처리 시간

페이지의 입출력 시간이 CPU 처리 시간보다 훨씬 크므로 데이터베이스의 데이터를 빠르게 처리하기 위해서는 데이터의 입출력에 필요한 페이지 수를 최소화할 필요가 있음

 

 

데이터베이스는 여러 개의 파일로 구성

논리적으로는 테이블들로 구성, 물리적으로는 파일들로 저장

 

 

1) Heap 파일 (순서가 없는 파일)

동등검색(ex: 학번이 1234인 학생을 검색)	키(ex: 학번, 주민번호) : 평균적으로 전체 페이지의 절반을 검색 값을 찾은 후에는 나머지 페이지를 검색할 필요가 없음
	중복 가능 속성(ex: 성별, 학년, 학과) : 전체 페이지를 검색
범위검색(ex: 학년이 2이상인 학생을 검색)	전체 페이지를 검색
INSERT	마지막 페이지에 삽입(처리시간 우수)
DELETE	동등검색하여 삭제
UPDATE	동등검색하여 다른 값으로 변경

INSERT를 제외한 모든 연산에 검색이 동반됨

INSERT 연산의 처리시간 우수. 그 외 모든 연산은 처리 시간이 오래 걸림

 

 

 

3) 정렬 파일 (한 속성을 기준으로 정렬)

속성    / 연산	입출력 페이지 수
	정렬 속성	키 값	중복 가능 속성
동등검색	log2(전체 페이지 수)	평균적으로 전체 페이지의 절반	전체 페이지 수
범위검색	Iog2(전체 페이지 수) + 해당 페이지 수	전체 페이지 수	전체 페이지 수
Insert	정렬 속성의 값으로 동등검색/비교하여 삽입, 뒤 쪽 데이터가 한칸씩 이동
Delete	정렬 속성의 값으로 동등검색하여 삭제, 뒤 쪽 데이터가 한칸씩 이동
Update	Delete후에 Insert	평균 전체 페이지의 절반	전체 페이지 수

정렬된 속성에 대한 검색의 처리시간 우수

Binary Search (이진검색)을 사용하므로 log2(전체 페이지 수)

시간과 메모리 사용 관점에서 정렬 유지가 고비용

 

 

 

3) 해시 기반 파일 (해시 함수로 속성을 분류)

해시 함수를 적용하여 레코드를 버켓에 저장

동등 검색에만 유용. 범위 검색에 사용할 수 없음(대소관계로 속성이 분류되지 않으므로)

 

ex)

해시 함수: h1(age) = age % 4

버켓 번호: B0, B1, B2, B3

h1(Age) 해시 함수를 적용해 각 버켓에 레코드를 저장

 

이상적인 해시 함수: 특정 패턴을 가진 레코드들이더라도 동등한 분포를 갖도록 각 bucket에 골고루 분배. 해시값을 소수로 결정하는 것이 좋음.

최악의 해시 함수: 모든 레코드들을 같은 bucket에 해시