화일 저장 구조

<디스크> (보조기억장치)

• 적은 비용으로 방대한 데이터를 저장할 수 있다.

• 여러장의 디스크가 쌓여져 있는 형태이다.
  

• 각 디스크는 sector(트랙)으로 나누어져 있다.
  

• 이 특정 sector를 통해 데이터를 찾게 되는데, 디스크의 회전 시간과 sector 탐색 시간까지 합치면 너무 오래 걸린다.

• 화일에 저장되어 있는 데이터를 하드 디스크에서 찾을 때, 하나씩 찾으면 오래 걸린다.

• 그래서 데이터(레코드)들은 블록 단위로 화일에 저장해놓고, 블록 단위로 데이터를 한번에 buffer에 올려놓고 필요한 만큼만 찾아서 사용한다.

• 레코드는 데이터 베이스에서 튜플을 의미한다.

• 레코드들을 블록화 하는것을 블로킹이라고 한다.

• 블로킹 할때, 블록의 자리가 남을 경우 레코드를 일부 나누어 여러개의 블록에 저장을 하면 spanned(신장 조직)이라고 한다.

• 레코드를 나누어 저장하지 않고 블록을 남겨두면 비신장 조직이라고 한다.

<레코드 저장 방식>

1. 비순서 화일(heap file, pile file) :

• 삽입은 빠르다.
• 찾는건 느리다.

2. 순서 화일(sequential file) :

• 순서 필드의 값에 따라 정렬된다.(순서 필드를 뭐로 하느냐에 따라)
• 삽입과 삭제는 순서를 맞춰야하므로 비용이 많이든다.
• 하지만 이진 탐색을 하면 O(log n)시간이 필요하므로 선형 탐색보다 빠르다.
• 레코드 삭제시 빈 공간을 채워야 한다.
• 접근은 인덱스를 사용한다.

3. 해싱 화일(해시 화일, 직접 화일) :

• 특정 필드값을 사용하여 레코드 그룹을 접근할 때 사용.
• 해시키를 정하여 그것을 특정 수로 나누어 나머지를 공통으로 묶는다.
• 이 묶음은 블록이 아닌 버켓이라고 부르고, 블록과 달리 크기 지정이 가능하다. 이 전체를 해시 테이블에 저장한다.
• cpu로 빠르게 해시값을 계산해 위치를 바로 찾기 때문에 시간은 O(1)이 걸린다.
• 크기가 정해져 있어 추가로 삽입될 경우 충돌이 발생할 수 있다.
• 그래서 해시 테이블을 70% ~ 90%로 채운다.
• 해싱의 오버플로우 후 해결법 :
  • Open addressing(개방 주소 지정) : 충돌지점부터 이후의 영역을 순서대로 탐색해 빈 공간을 찾는다.
  • 체인(Chaining) : 오버플로우 버켓을 만들어 새로운 것을 저장하고, 원래 버켓의 pointer에 주소를 저장해준다.
  • 다중 해싱 : 해시 함수를 여러개 가지고 있고, 첫번째 해시 함수에서 충돌이 일어나면 두번째 해시 함수 값으로 저장한다.

-> 정적 해싱이기 때문에 일어나는 일이다. (공간이 한정적)

동적 및 확장 해싱 화일

• 오버플로우에 주로 이 방법을 사용한다.
• 데이터가 늘어나면 버켓을 늘리고, 데이터가 적으면 버켓을 줄이는 방법
• 해시값(비트)으로 버켓을 지정하는 기존 방식에 더해, 비트수로 1bit -> 2개, 2bit -> 4개, 3bit -> 8개 ... 이렇게 디렉토리 수(버켓의 주소를 저장하는)를 지정한다. 이렇게 동적으로 데이터를 저장하는 방식이다.