[파일 처리] 08 직접 화일

 

01. 직접 화일의 개념

 

1. 직접화일

1) 임의 접근 화일 = 직접 화일 

- 다른 레코드를 참조하지 않고도 개개 레코드에 접근 가능

- 인덱스된 화일, 인덱스된 순차 화일, 상대 화일, 해시 화일

 

2) 상대 화일

- 레코드의 키와 레코드의 위치 사이에 설정된 관계를 통해 레코드에 접근

- 상대 레코드 번호 : 화일이 시작되는 첫 번째 레코드를 1번으로 지정, 기준으로 번호 지정

> 사상 함수 

  -  A : 키 값 => 주소

  - 레코드 기록 시 : 키 값 => 레코드가 저장될 주소

  - 레코드 검색 시 : 키 값 => 레코드가 저장되어있는 주소

  - 모든 레코드에 직접 접근 가능(메인 메모리, 디스크등 직접 저장 장치에 저장하는 것이 효율적)

  - 사상함수 구현방법 : 디렉터리 검사, 계산을 이용한 방법

 

3) 디렉터리 검사

- <키값, (상대)주소> 쌍을 엔트리로 하는 테이블 유지

- 검색 절차 : 디렉터리에서 키 값 검색 => 키 값에 대응되는 레코드번호 구함 => 레코드 접근

- 장점 : 빠른 검색, 단점 : 삽입 비용큼, 화일과 디렉터리 재구성 필요

 

02. 해싱

1. 특징

- 계산을 이용한 상대 화일 구성법

- 키 값 공간 >> 주소 공간

- 해싱 : 해싱 함수를 이용해 키 값을 주소 변환하고, 키에서 변환된 주소에 레코드를 저장하는 과정

* 장점 : 레코드의 주소를 구해 직접 접근하므로 빠른 접근 시간을 가짐

 

2. 해싱 함수

- 키 공간을 주소 공간으로 사상 ( 키값 -> 주소, 주소 ⊂ 유효 주소 공간)

- 키 값들을 한정된 주소 공간으로 균등하게 분산 시키는 것이 핵심

 

3. 해싱을 이용한 화일 설계시 고려사항

1) 버킷 크기

ⓐ 버킷 : 하나의 주소를 가진 한 저장 구역

ⓑ 버킷 크기 : 통상적으로 한 번의 접근으로 버킷 내에 있는 모든 레코드들을 전송할 수 있는 크기로 결정

ⓒ 충돌 : 두개의 상이한 레코드가 똑같은 버킷으로 해싱되는 것(동거자), 오버플로

* 버킷의 크기를 크게하면? 오버플로 감소하지만 저장공간 효율 감소, 레코드 탐색시간 증가함

 

2) 적재율

- 적재 밀도(패킹밀도) = 실제 저장된 레코드 수/화일 저장 공간의 총 용량 = K/e*N <1

*N 버킷 수, e 버킷용량, K 화일에 저장된 레코드 수

- 적재 밀도가 높아지면 삽입시 접근수, 검색시 접근수 , 공간 효율 증가

 

3) 해싱함수 : 키 -> 버킷 주소

- 해싱함수 계산시간 << 보조기억장치의 버킷 접근 시간

- 모든 주소에 대한 균일한 분포를 가지는 게 좋음

- 주소 변환 과정 : 키->A(정수)->B(해싱함수) -> B*조정상수 -> 주소

ⓐ 제산 잔여 해싱 : 주소 = 키 값 mod 제수 -> 0~제수-1

*제수 : 직접 주소 공간의 크기를 결정(제수>화일의 크기), 충돌 가능성이 가장 적은 것으로 선택

ⓑ 중간 제곱 해싱 : 키 값을 제곱하고 중간에서 n의 수를 취함, 주소 범위에 맞도록 조정

ⓒ 중첩 해싱 : 키 값을 주소공간과 같은 자리 수를 가지는 몇 개의 부분으로 나눔, 접어서 합을 구함, 주소 범위 조정

ⓓ 숫자 추출 : 키 값이 되는 숫자의 분포 이용, 키들의 모든 자리수에 대한 빈도 테이블 만들고 균등한 분포 갖는 자릿수 주소로 이용( 키 값들을 미리 알아야함)

ⓔ 숫자 이동 변환 : 키를 중앙으로 양분한 후 주소 길이만큼 겹치도록 안쪽으로 각각 shift, 조정

ⓖ 진수 변환 : 키 값의 진수를 다른 진수로 변환, 초과시 절단, 조정

 

 

03 충돌과 오버플로

1. 충돌과 오버플로

- 키 값 공간 > 주소 공간 -> 충돌 불가피

- 오버플로 : 하나의 홈 주소로 충돌된 동거자들을 한 버킷에 모두 저장할 수 없는 경우

- 오버플로 해결 방법 : 개방 주소법(상대 화일에 저장), 체인법(상대 화일 밖에서 찾아 해결)

 

2. 오버플로 해결 방법

1) 선형조사

- 오버플로 발생시, 홈 주소에서부터 차례로 조사해서 가장 가까운 빈 공간을 찾는 방법 - 원형탐색

- 저장 : 원형탐색에서 빈 주소를 조사하는 과정은 홈 주소에서 시작하여 화일 끝으로 간 후, 화일 시작으로 돌아가 홈 주소에 다다를 때 끝남, 홈 주소로 돌아올 때까지 빈 공간 없으면 화일이 만원임

ⓐ 검색

- 레코드 저장 시에 선형 조사를 사용했다면 검색에서도 선형조사를 사용해야함

- 탐색 키 값을 가진 레코드가 없거나 홈 주소에서 멀 경우, 많은 조사 필요

ⓑ 삭제

- 삭제로 인해 만들어진 빈 공간으로 검색 시 선형 조사가 단절될 수 있음 -> 삭제 표시 이용

 

✅ 선형조사 단점

- 환치 : 한 레코드가 자기 홈 주소를 동거자가 아닌 레코드가 차지하여 다른 레코드의 홈 주소에 저장되는 것

> 대응 책 : 2-패스 해시 화일 생성

- 첫 번째 패스 

• 모든 레코드를 해시 함수를 통해 홈 주소에 저장
• 충돌이 일어나는 동거자들은 바로 저장하지 않고 별도로 임시 화일에 저장

- 두 번째 패스

• 임시 화일에 저장해 둔 동거자들을 선형 조사를 이용해 화일에 모두 적재

* 1패스 보다 더 적절하게 저장됨, 화일 생성 이전에 레코드 키값들을 미리 알 때 효율적임

* 하지만 화일이 생성된 후에 레코드들이 추가될 때는 환치가 발생함

 

2) 독립 오버플로 구역

- 별개의 오버플로 구역을 할당하여 홈 주소에서 오버플로된 모든 동거자들을 순차로 저장하는 방법

- 장점 : 동거자가 없는 레코드에 대해서 한번의 홈주소 접근만으로 레코드 검색, 1-패스로 상대화일 생성, 환치x

- 단점 : 오버플로된 동거자를 접근하기 위해서는 오버플로 구역에 있는 모든 레코드들을 순차적으로 검색

 

3) 이중 해싱

- 오버플로된 동거자들을 오버플로 구역으로 직접 해시 : 오버플로 구역에서 순차탐색 피함, 2차 해시 함수

- 해싱 과정 : 1차 해시함수에 의해 상대화일로 해시 -> 오버플로 발생시 오버플로 구역으로 해시 -> 또 충돌 선형탐색이용

 

4) 동거자 체인

- 각 주소마다 링크를 두어 오버플로된 레코드들을 연결하는 방법

- 독립 오버플로 구역에 사용할 수도있고, 원래의 상대 화일에 적용할 수도 있음

- 장점 : 환치 제거 / 단점 : 각 주소가 링크 필드를 포함하도록 확장해야함

 

3. 오버플로 처리 기법 성능 비교

- 성공적 탐색 성능 : 동거자 체인 > 이중 해싱 > 선형 조사

- 실패 탐색 : 동거자 체인이 월등히 우수

 

 

04 확장성 직접화일

1. 특징

- 레코드 수의 변화가 큰 경우 해결방안

- K : 어느 한 시점에서 화일에 저장된 레코드 수 (Kmin <= K <= Kmax)

- SAPN = Kmax/Kmin (SAPN이 클 때 문제가 된다 => 재해싱)

- 확장성 화일 : 높은 SPAN 값을 가진 화일에 대한 해싱 기법

 

2. 확장성 해싱

1) 두 단계의 조직

- 디렉터리 : 전역 깊이(d)와 버킷에 대한 2^d 개의 포인터로 구성

- 각 포인터가 반드시 상이해야 하는 것은 아님

- 버킷의 집합 : 레코드들이 저장되는 공간, 지역 깊이(p)로 구성 

 

2) 확장성 해싱 함수

- h : 키->모조키

- 버킷 깊이: 버킷 안 각 레코드들의 모조키가 공통으로 가지는 처음 비트 스트링 길이

① d>= p+1인 경우의 분할

- 기존 버킷이 p+1번째 비트에 따라 두 그룹으로 분할됨

* 버킷 깊이 갚은 공통으로 가지는 처음 비트스트링 길이 

② d< p+1인 경우 분할

- d(디렉토리)가 커진다 ( 2->4->8->16->,,,)

- d에 따라서 p도 두 그룹으로 분할되고 버킷 깊이 값도 커지게 된다. 

- 분할에 직접 연관되지 않은 버킷들은 디렉터리 확장 이전보다 두배의 포인터들이 지시하게 된다.

 

3) 확장성 해싱 화일의 연산

① 삽입

- 모조키의 처음 d비트 이용, 디렉터리 접근, 버킷 찾아 삽입

- 버킷이 만원이면, 새로운 리프 할당 -> 레코드 분할 -> d, p+1 값에 따라 분할

◼ d>=p+1 : 포인터들을 분할, 이전의 버킷과 새로운 버킷이 p+1의 버킷 깊이를 가짐

◼ d<p+1 : 디렉터리의 크기를 두배로 늘림 : d<-d+1

② 검색

- 모조키의 처음 d비트를 디렉터리에 대한 인덱스로 사용하여 디렉터리에서 찾아 레코드 접금

③ 삭제 : 삭제 버킷이 버디 버킷을 가지고 있고, 그 두 버킷의 레코드들이 한 버킷 안에 들어 갈수 있으면 병합

- 버디 버킷 : 버킷 깊이가 같은 버킷 중 모조키들의 처음 p-1비트들이 모두 같은 버킷

 

3. 동적 해싱

- 화일 구성 : 크기가 c인 n개의 버킷 

1) 삽입 : 인덱스 레벨 0부터 시작하여 오버플로우가 발생하면 버킷이 분할되어 인덱스레벨이 높아지는 방식

2) 저장

- 두개의 해싱함수 사용 : 해싱 함수 H0, 임의 함수 B(키 값을 임의 길이의 비트 스트링으로 변환)

- 저장 절차

ⓐ 키를 해싱함수를 이용하여 인덱스 엔트리의 한 주소로 변환

ⓑ 인덱스 엔트리의 포인터를 통해 해당 버킷에 레코드 저장

ⓒ 1 이상의 인덱스 레벨이 있으면 함수 B를 이용해 저장할 버킷 찾음

ⓓ 버킷이 만원인 경우, 버킷을 새로 할당하여 이미 저장된 레코드들 + 새로 저장할 레코드를 분할 저장

ⓔ 인덱스를 이진 트리로 바꾸어 두 버킷을 지시하게 함