[Database] 디스크 안에 파일 레코드를 저장하는 방법

데이터는 파일 속에 레코드 형태로 보관이 된다.

 

이러한 레코드는 

1. 고정 길이 레코드
2. 가변 길이 레코드

로 나뉜다.

 

고정 길이의 경우 길이가 고정되어 있기 때문에 원하는 정보를 얻기 쉬우나

 

가변 길이의 경우 구분자를 사용한다.

 

고정길이

가변길이

 

---

blocking factor (블록 당 레코드의 수)

블록의 크기가 512 Bytes이고 레코드의 크기가 100 Bytes라고 한다면 하나의 블록에는 5개의 레코드가 들어가고 12Bytes는 남게 된다.

 

즉 512/100에서 소수점을 버리면 이게 곧 blocking factor 이다.

 

bfr(blocking factor) = B(블록 크기)/R(레코드 크기)

 

블록마다 남는 크기는 B - bfr * R 이다.

 

레코드들의 크기가 블록의 크기보다 커진다면 어떻게 할까? 두 가지 방법이 있다.

 

1. spanned organization(신장) : 블록의 남는 부분을 사용하지 않고 다음 블록에 레코드를 저장한다.
2. unspanned organization(비신장) : 블록의 남는 부분을 사용하고 나머지 레코드는 다음 블록에 저장한다.

 

디스크에 파일 블록을 할당하는 방법

1. consecutive allocation : 연속으로 저장. 읽는 속도 빠름. 파일 확장이 어려움
2. linked allocation : 다음 블록의 포인터를 저장. 읽는 속도 느림. 파일 확장이 쉬움
3. indexed allocation : 인덱스 블록이 존재하고 각각의 인덱스 블록은 실제 파일 블록의 포인터를 갖고 있음

file header

1. 파일 블록의 디스크 주소를 결정한다.
2. 길이 순서 등등 포맷 형식을 결정한다.

이상적인 물리적 데이터베이스 설계는 원하는 레코드를 찾을 때 block transfer를 최소화 해야한다.

 

Heap file

Heap file의 경우 레코드들이 삽입된 순서대로 저장된다.

 

정렬이 되어있지 않기에 linear search를 할 수 밖에 없고 n개의 블록이 있다면 평균적으로 n/2의 시간이 걸린다.

 

Heap file의 데이터 삽입 과정

Heap file의 데이터 수정 과정

 

삽입과 비슷하게 먼저 해당 블록을 메인 메모리로 가져온다.

 

바꿀 레코드를 삭제를 하거나 삭제 마크를 달아놓는다. ( 두 방법 모두 해당 레코드를 사용하지 못한다.)

 

그리고 삽입과 마찬가지로 마지막 블록을 가져와서 바꿀 내용을 적는다.

 

이렇게 수정을 하면 쓰지 못하는 레코드가 존재하므로 주기적으로 정리를 해줘야한다.

 

레코드가 가변 길이라면 옛날 레코드를 삭제하고 새로운 레코드를 추가해야한다.

 

이러한 heap file은 정렬이 되어있지 않기 때문에 따로 정렬된 레코드들을 따로 만들어서 검색을 하곤 한다.

 

이 방법을 external sorting이라고 한다.

 

크게 정렬 방식은 두 가지로 나뉜다.

1. internal sorting(내부 정렬) : 메인 메모리에 모든 것을 올려놓고 정렬한다.
2. external sorting(외부 정렬) : 메인 메모리에 가져올 수 있을 만큼 잘라서 가져와서 정렬을 하고 정렬된 것들을 모아서 다시 정렬을 한다.

external sorting(외부 정렬)

파일을 잘게 잘라서 정렬을 하고 이렇게 정렬된 각각의 조각들을 합치면서 다시 정렬을 한다.

 

척 보기에도 부담스러운 방식이다.

 

상대 파일

상대적인 번호로 검색한다.

 

예를 들어 bfr은 4이고 110번째 레코드를 찾으려 한다면

 

110/4의 소수점을 버리면 27이고 나머지는 2이다.

 

즉 27번째 블록의 3번째 레코드를 의미한다.

 

다음 포스팅에서 정렬된 파일에서의 연산을 공부해보려한다.