[FP] 08. 직접 화일

임의 접근 화일

임의 접근 화일 = 직접 화일 = 직접 접근 화일 <=> 순차 접근 화일

• 임의의 레코드 키 값으로 그 레코드에 접근할 수 있는 화일
• 다른 레코드를 참조하지 않고 특정 레코드 접근이 가능

직접 화일의 종류

• 인덱스된 화일 : 인덱스를 이용해 레코드를 접근
• 인덱스된 순차 화일 : 인덱스를 이용한 임의 접근과 순차 접근을 모두 지원
• 상대 화일 : 키와 화일 내 레코드의 상대적 위치(상대 레코드 번호) 사이에 정해진 관계를 이용해 레코드를 접근
• 해시 화일 : 키 값을 레코드 주소로 변환하여 레코드를 접근, 협의의 직접 화일

---

상대 화일

상대 레코드 번호 relative record number, RNN

• 화일이 시작되는 첫 번째 레코드를 기준으로 레코드들에 0, 1, 2, ... N-1을 지정, 상대 주소라고 함
• 레코드의 논리적 순서와 물리적 순서는 무관, 레코드들이 키 값에 따라 물리적으로 정렬되어있을 필요도 없음

사상 함수

• 키 값을 화일 주소로 사상시키는 함수 (A : 키 값 -> 주소)
• 레코드 기록 시, 사상 함수 A는 키 값을 레코드가 저장될 주소로 변환
• 레코드 검색 시, 사상 함수 A는 키 값을 레코드를 검색할 수 있는, 즉 저장되어있는 주소로 변환

---

사상 함수를 구현하는 방법

---

해싱 함수

해싱 함수 = 주소 변환 함수 = h : (키 값) → 주소

해싱 함수 계산 시간은 디스크의 버킷 접근 시간에 비교해 아주 작다. 

즉, 디스크 접근 시간을 최소화할 수 있다면 복잡한 해싱 함수를 쓸 가치가 있다.

각 해시 주소로 사상되는 레코드 수는 균등한 분포를 갖는 것이 좋다.

 

주소 변환 과정

1. 키가 숫자가 아닌 경우 키를 정수 값(A)로 변환 ( 키 값 -> A )
2. 정수 A를 주소 공간의 자리 수 크기의 정수 B로 변환 ( A -> B )
3. 정수 B를 주소 공간의 실제 범위에 맞게 조정 ( B x 조정 인수 -> 주소 )

---

충돌과 오버플로

키 값 공간이 주소 공간보다 크기 때문에 충돌 발생이 불가피하다.

홈 주소 : 해싱 함수가 생성한 버킷 주소

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

---

선형 조사

레코드 저장 시에 선형 조사로 했으면 검색 시에도 선형 조사 방법을 사용해야 함

• 오버플로 발생 시, 홈 주소에서부터 차례로 조사해서 가장 가까운 빈 공간을 찾는 방법
• 해당 주소가 공백인지 아닌지 판별할 수 있게 플래그(flag)를 이용
• 저장 : 빈 공간을 찾을 때, 홈 주소에서 시작하여 화일 끝에 도달하면 다시 화일 시작으로 돌아가 홈 주소까지 실시(원형 탐색)
• 검색 : 탐색 키 값을 가진 레코드가 없거나 홈 주소에서 멀리 떨어져 있는 경우, 많은 조사가 필요
• 삭제 : 삭제로 생긴 빈 공간을 검색 시, 선형 조사가 단절될 수 있음 -> 삭제 표시(tombstone)가 필요하다.

단점

1. 어떤 레코드가 없다는 것을 판단하기 위해 조사할 주소의 수가 적재율이 높으면 많아짐 (적당한 적재율 유지 필요)
2. 환치 : 한 레코드가 자기 홈 주소를 동거자가 아닌 다른 오버플로된 레코드가 차지함으로 인해 다른 레코드에 저장되는 것
   -> 환치는 또 다른 환치를 유발, 탐색할 주소 수의 증가는 삽입/검색 시간 증가를 야기
   -> 처음 화일을 생성할 때, 2-패스 해시 화일 생성 방법을 이용, 첫 번째 패스 때 모든 레코드를 해시 함수를 통해 
    홈 주소에 저장하고 오버플로된 동거자들은 임시 화일에 저장, 두 번째 패스 때 선형 조사를 이용하여 전부 적재
   -> 많은 레코드가 자기 홈 주소에 저장, 화일 생성 전 레코드 키 값을 알면 효율적, 화일 생성 후 추가되는 레코드는 환치 발생

---

독립 오버플로 구역

• 별개의 오버플로 구역을 할당하여 홈 주소에서 오버플로된 모든 동거자들을 순차로 저장하는 방법
• 장점 : 동거자가 없는 레코드는 한 번의 홈 주소 접근으로 레코드를 검색. 1-패스로 상대 화일 생성, 환치 문제가 없음
• 단점 : 오버플로된 동거자를 접근하기 위해서는 오버플로 구역에 있는 모든 레코드들을 순차적으로 검색해야 한다.

---

이중 해싱

• 오버플로된 동거자들을 오버플로 구역으로 직접 해시 : 오버플로 구역에서의 순차 탐색을 피할 수 있다.
• 1차 해싱 함수에 의해 상대 화일로 해시, 오버플로가 발생하면 오버플로 구역으로 해시, 또 일어나면 선형 탐색 이용
• 2차 해싱 함수를 이용한다.
• 오버플로 구역 주소 = (1차 해시 주소 + 2차 해시 주소) mod (오버플로 구역 크기)

---

동거자 체인

• 각 주소마다 링크를 두어 오버플로된 동거자 레코드들을 연결하는 방법
• 오버플로가 일어나면 선형 조사나 오버플로 구역을 이용해서 저장한 뒤에 링크로 연결
• 동거자에 대한 접근은 링크로 연결된 동거자들만 조사하면 된다.
• 독립 오버플로 구역에 사용할 수도 있고, 원래의 상대 화일에 사용할 수도 있다.
• 장점 : 홈 주소에서의 충돌 감소, 독립 오버플로 구역 사용 시 환치 문제가 없다.
• 단점 : 각 주소가 링크 필드를 포함할 수 있도록 확장해야 한다.

---

버킷 체인

• 홈 버킷에서 동거자 오퍼플로 발생 시, 별개의 버킷을 할당받아 오버플로된 동거자를 저장하고 홈 버킷에 이 버킷을 링크로 연결
• 장점 : 재해싱이 불필요, 독립 오버플로 구역 사용 시, 환치 문제가 없음 / 탐색 시 모든 방법 중 평균 조사 수가 적음
• 단점 : 각 주소가 링크 필드를 포함할 수 있도록 확장해야 한다. 최악의 경우 한 레코드를 탐색하기 위해 그 홈 버킷에 연결된 모든 오버플로 버킷을 조사해야 한다.

---

테이블 이용 해싱

저장 장치에 한 번의 접근으로 레코드 검색을 보장

레코드 삽입 시간은 많이 걸리지만 검색은 매우 빠르다.

해싱 함수는 각 레코드에 대해 일련의 <버킷 주소, k-비트 시그니처> 쌍을 생성한다.

각 버킷에는 하나의 엔트리(k-비트 시그니처)로 된 버킷 테이블을 유지

화일 접근 시에 이 버킷 테이블은 전부 메인 메모리에 상주

---

확장성 직접 화일

K가 어느 한 시점에서 화일에 저장된 레코드 수라고 가정, Kmin ≤ K ≤ Kmax

SPAN : Kmax / Kmin , SPAN이 크면 문제가 생긴다.

화일 크기가 고정되어 있을 때, K ≈ Kmin : 공간 이용률은 낮음 / K ≈ Kmax : 적재 밀도가 높음, 저장/검색 시간 길어짐

‘재해싱’으로 해결이 가능하지만 많은 시간이 소요되고 재해싱하는 동안 접근이 제한되는 문제가 발생

 

확장성 화일

• 화일 조직에서 저장되는 레코드의 수에 따라 버킷 수가 늘어났다, 줄어들었다 한다.
• 높은 SPAN 값을 가진 화일에 대한 해싱 기법
• 버킷 크기는 일정하다고 가정, 버킷 수는 가변, 오버플로 버킷은 사용X
• 삭제는 간단
• 검색은 1-2회의 접근만 필요