7. File

File이란?

-> record의 연속

 

Fixed length record : 모든 레코드는 정확히 같은 사이즈

variable length record : 모든 레코드는 다른 사이즈

 

Primary File Organizations

heap file(비정렬 파일)

- 새로운 데이터가 생성되면 파일의 끝에 추가됨

 

sorted file(순차 파일)

- 검색키를 기반으로 정렬된 순서를 갖음

 

hashed file

- hash function을 적용해 디스크에서 record 위치 결정

 

블록 저장방식

블록 B byte를 R byte로 나눔 (B >= R)

 

Blocking Factor (bfr) = B / R

ex) 고정 길이 레코드에서 512byte의 file이 있고, record가 100byte일 때

bfr = 512 / 100 = 5

따라서 실제 레코드엔 500 byte가 들어감 사용하지 않는 12byte 발생

 

저장방식

위의 고정 길이 레코드 방식에선 12byte의 남은 용량이 발생했다.

이 남은 공간은 어떻게 처리할지에 대해 2가지 방법이 있다.

 

1. unspanned

블럭 여유 공간에 비해 레코드 크기가 크다면,

해당 블럭을 버리고, 다음 블럭에 저장

 

2. spanned 방식

남은 블록 공간에 최대한 넣고, 마지막에 다음 블록으로 이어지는 포인터 할당. (잘 안 씀)

 

그림으로 정리하면 다음과 같다.

출처 : 교수님 ppt

 

 

File operation

record at a time

한 번에 한 레코드 연산 (reset, find, read, delete, insert 등)

set at a time

한 번에 여러 레코드 연산(find All, find N, reorganize, order)

open/close

scan 

find, read등의 연산이 올 때, 연산을 streamling

 

File of Unorderd Records(Heap files)

레코드가 삽입된 순으로 저장되는 방법

수집이 목적

탐색시, linear search를 해야 함

 

삭제 방식

- delete 표식을 남기거나

- 레코드를 빼고 다시 rewrite (이러면 빈 공간은 다시 사용 못해서 주기적으로 정렬 작업 필요)

 

주소 계산법(relative positon)

Ex) bfr = 4 일 대, 110번째 record 위치 (0부터 시작하니 #109)

110 / 4 = 27.5 , 110 mod 4 = 2 (0, 1, 2)

그러므로 110번째 record는 27번 블록의 3번 레코드에 있다.

 

File of Orderd Records(Stored files)

bfr의 한 부분을 읽으면, 나머지 부분은 버퍼에서 바로 찾을 수 있음

 

삭제 방식

매 변경마다 정렬을 해야 해서 비효율적

그러므로, 데이터 사이에 별도의 칸을 두거나,

별도의 임시 파일을 만들고 거기에서 재구성

 

정렬되지 않은 임시 파일을 overflow 또는 transaction File 이라 함

실제 정렬된 파일은 main 또는 master File 이라 함

 

Hashing

- 특정 검색 조건에서, 레코드에 빠르게 접근할 수 있는 기본 파일 구성

- 검색 조건은 해시 Key하고 같은 조건이어야 함

Hashing 구조

 

내부 해싱(Internal Hashing)

Internal File에서는, 해싱은 일반적으로

레코드의 배열을 사용해 해시 테이블 구성

h(K)  = K mod M

Collision

hash field의 고유 값이 actual space로 매칭된다는 보장이 없음

= 동일한 값이 생기는 경우가 있음

hash field >> actual space여서 생기는 문제

 

 

해결방법

1. open address

-> 사용하지 않은 빈 위치를 찾을 때 까지 탐색

Ex) h(K) mod 100 이고, 103과 203이 입력됐다고 하면,

Data Filed엔 3번 위치에 103이 들어가지만,

203도 3번위치에 들어가야 하는데 이미 103이 있으므로, 다음 번지(4번)에 203 저장

 

2. multiple hash

-> 충돌이 발생하면, 다시 hash function 적용

 

3. chaining

-> 새로운 위치에 저장을 한 뒤, 충돌이 난 곳에 해당 위치 포인터 저장

 

 

External Hashing

디스크 File에 대한 Hashing

타겟 address 즉, hashing 함수의 결과 space가 bucket이 됨

 

bucket

- 하나의 디스크 블럭 or 여러 개의 블럭

- hashing Function은 key 값으로 상대 번호를 찾음

- Chaining의 변형

 

 

Dynamic Hashing

1. Extendible hashing

2. Linear Hashing(선형 해싱)

3. Dynamic hashing

 

Extendible hashing

Directory = 버킷 주소의 배열(2^d)

d = Directory의 Global Depth

처음 d비트는 directory entry index

해당 항목 값(주소)은 해당 레코드가 저장되는 버킷 결정

Local Depth = directory entry를 그룹화하는 용도

(Global Depth >= Local Depth)

만약, d` = 2이면, 첫 2bit가 동일한 디렉토리와 버킷이 저장

 

그림으로 정리하면 다음과 같다.

 

d=3이니, 각 버킷의 local depth도 최대 3bit까지 비교할 수 있으나,

3번재 버킷 처럼 2bit만 비교해서 여러 디렉토리가 오게 할 수 있다.

 

Global depth 의 비트는 늘릴 수 있다.

늘리는 걸 doubling, 줄이는 걸 halving이라 한다.