데이터 베이스의 내부 구조

데이터베이스의 거주장소 보조기억장치(Secondary Memory) DB는 파일(File)의 형태로 저장됨 주기억장치 (RAM, ROM)에 비교해서 디스크(Disk) : 여러 Disk, Track, Sector 영구성(persistence),비휘발성(non-volatile) 값싸고 방대한 저장장소 접근 시간(access time : disk I/O)의 비효율성 <- 기계 장치를 필요로 하므로 Flash Memory와 서로 경쟁하는 관계 DB는 파일(File)의 형태로 저장됨

처리 과정 find the location of data (from disk) read data and move it to buffer (in main memory) Sector의 데이터가 동시에 읽혀짐 process it Update, insert, delete write it back (to the disk)

파일 시스템에서의 DB 용어 필드(field) << 레코드(record) << 화일(file) << 데이타베이스(database) 속성(attribute) → 필드(field) 터플(tuple) → 레코드(record) 릴레이션(relation) → 화일(file)

DB의 성능 평가 파일 시스템 설계에 의해 영향을 받는다 평가 요소 응답시간(Response Time) : 질의를 시작해서 질의 결과가 처음으로 나오는데 걸리는 시간 공간 이용률(Space Utilization) : 파일 및 접근 경로(access path) 구조가 사용하는 저장공간의 양 트랜젝션 처리율(Transaction Throughput) : 데이타베이스 시스템에 의해 처리되는 트렌젝션의 평균수

응답시간에 영향을 미치는 요소 디스크의 물리적인 특성 (s + r + t) Blocking 방법 효과적인 Access 방법 탐색 시간(searching time : s) : 정확한 트랙을 찾는 시간 회전 지연 시간(rotational delay : r) : 정확한 블록을 찾는 시간 전송 시간(transfer time : t) : 블록을 판독하여 버퍼로 이동하는 시간 하드 디스크의 RPM이 중요 : 5000/7000/10000 등 Blocking 방법 블럭킹 인수(blocking factor : bfr) : 한 블록에 저장되는 레코드들의 개수 한 Block은 주로 한 Sector 효과적인 Access 방법 Indexing, Hashing, Clustering

Blocking Factor(bfr) bfr = B / R 예) bfr 이 크면 클수록 레코드 크기 : 100 Byte, 블럭 크기 : 1024 Byte 이면 bpr = 1024 / 100 = 10 레코드의 전체 개수가(r)가 10,000 이라면 필요한 블럭의 총수 (b) 는 r / bfr = 1000 개 bfr 이 크면 클수록 (장점) - 디스크 I/O 를 줄임 (단점) - 버퍼 크기만큼 main memory 의 손실 - 블록의 일부만 처리하더라도 블럭 전체를 전송

Access 방법 순차 파일 (Sequential File) 인덱스 파일(Index File) 해싱 파일(Hashing File)

순차 파일(Sequential File) I 구성 저장장치에서의 레코드 순서와 실제 화일의 순서와 일치 특정 필드에 대해 순차적으로 저장: 예) 키(key) 필드 각 필드이름에 해당하는 필드값 만 저장 오버플로우(overflow) 영역인 트렌잭션 화일(transaction file)을 따로 관리 성능 검색 이진 탐색(binary search)을 이용 최악의 경우 log2 b 개의 블럭들을 검색 특히 차위 레코드(next record)들의 검색이 매우 효율적

순차 파일(Sequential File) II 성능 삽입 삽입되는 레코드의 위치를 검색해야 함 방법 1) 레코드들을 이동(shift)함: 최악의 경우 b 개의 블럭들 이동 --> 파일의 크기가 방대할 때 매우 비효율적 방법 2) 오버플로우 영역(transaction 화일)에 비순차적으로 삽입한 후, 정기적으로 원래의 데이타 파일(master file)과 합병(merge)하여 순차 유지 --> 검색시 master file을 먼저 탐색후 없으면 transaction file을 탐색 삭제 삽입과 거의 동일함

순차 파일(Sequential File) III 응용 일괄 처리(batch processing) 응용에 특히 적합: 예) 사원봉급 명세서 삽입 / 삭제가 거의 없는 응용에 효율적 차위 레코드(next record)의 검색에 효율적 재조직이 off-line으로 실행됨

인덱스 파일(Index File) I

인덱스 파일(Index File) II 키값에 따라 정렬된 레코드를 순차적으로 접근 주어진 키값(인덱스)을 가지고 직접 접근 인덱스 구성 방법 정적인 방법 동적인 방법 레코드 삽입, 삭제시 레코드의 순서 유지 및 인덱스 갱신 방법의 차이

인덱스 파일(Index File) III 인덱스 구조의 예 : 3차 B-Tree

인덱스 파일(Index File) IV 직접탐색: 순차 검색: 삽입, 삭제 키 값을 이용한 검색 트리(Tree)의 균형 유지 분할(Split) : 높이 증가 합병(Merge) : 높이 감소

해싱 파일(Hashing File) I 다른 레코드 참조 없이 목표 레코드 직접 접근 - 직접 파일(direct file) 키값과 레코드 주소 사이의 관계 예측 해싱 함수(hashing function) 키 값으로부터 주소를 계산 사상 함수(mapping function) : 키 → 주소 삽입, 검색에도 이용

해싱 파일(Hashing File) II