[데이터베이스/Database] 파일 구조에 따른 성능 비교

B : 데이터 페이지들의 수

R : 페이지 당 레코드들의 수

D : 디스크 페이지를 read/write하기 위한 평균시간

	파일 스캔	동등 검색	범위 검색	삽입	삭제
힙 파일	BD	0.5BD	BD	2D	검색 연산 + D
정렬 파일	BD	Dlog2B	D (log2B + match page 수)	검색 연산 + BD	검색 연산 + BD
군집 트리 인덱스	1.5BD	DlogF1.5B	D(logF1.5B + match page 수)	검색 연산 + D	검색 연산 + D
비군집 트리 인덱스	BD(R + 0.15)	D(1 + logF0.15B)	D(logF0.15B + matched Records수)	D(3 + logF0.15B)	D(3 + logF0.15B)
비군집 해시 인덱스	BD(R + 0.125)	2D	BD	4D	4D

군집 트리 인덱스

: 실험적으로 각 페이지에 데이터가 2/3 차 있을 때 효율이 좋음.

데이터 파일 전체 페이지 수: X*2/3=B, X=1.5B

Fan-Out: F, F^h = 1.5B -> h = logF1.5B (height)

 

비군집 트리 인덱스

: 실험적으로 각 페이지에 데이터가 2/3 차 있을때 효율이 좋음.

데이터 엔트리의 크기를 데이터 레코드 크기의 1/10로 가정.

전체 리프 노드 페이지 수: X*2/3=0.1B, X=0.15B

Fan-Out: F, F^h = 0.15B -> h = logF 0.15B (height)

 

비군집 해시 인덱스

: 실험적으로 각 페이지에 데이터가 80% 정도 차 있을때 효율이 좋음.

데이터 엔트리의 크기를 데이터 레코드 크기의 1/10로 가정.

전체 인덱스 파일 크기: 0.8X = 0.1B, X= 0.125B

 

 

 

 

 

 

해시 인덱스 -> 동등 검색에 효율적. 범위 검색은 적절하지 않음.
트리 인덱스 -> 동등/범위 검색 모두 효율적.

Insert/Delete/Update : 해시 인덱스, 트리 인덱스 모두 효율적


트리 인덱스는 데이터 엔트리를 효율적으로 Insert/Delete 가능.
트리 인덱스의 검색 시간 >>>>> 정렬된 파일의 이진 탐색 시간

순차적인 순서로 여러 페이지들을 검색하는 경우-> 정렬 파일의 페이지들은 디스크에 물리적 순서대로 할당되어 있으므로 트리 인덱스보다 정렬 파일이 훨씬 효율적.