화일처리 및 응용 공부 #19 (직접화일2)

한반가 2021. 6. 23. 13:30

레코드 삽입 예
- 버킷 크기 :3
- 레코드 삽입 순서 : white, blue, lilac, red, green ....
- 각 레코드의 홈 버킷 : 85
3번째 lilac을 삽입하면 버킷 85는 만원이 됨
- 버킷 크기가 3이기 떄문
4번쨰 red를 삽입할 때 오버플로 발생, 이 버킷 85에 대한 4레코드 시그니처 값들을 정렬
- red (시그니처 00010 = 2)
- white (시그니처 00101 =5)
- blue (시그니처 00110 = 6)
- lilac (시그니처 01000 =8) -> 분리 시그니처 값
시그니쳐 값 8을 분리 시그니처 값으로 선정하고 버킷 85에 대한 버킷 테이블 엔트리로 저장
- 버킷에는 항상 분리 시그니처 값보다 작은 레코드만 저장
이 분리 시그니처 값보다 작은 red, white, blue 는 버킷 85에 다시 저장
그러나 lilac은 그의 두번째 버킷주소 90에 저장
버킷 테이블 엔트리 즉, 시그니처 값은 초기치 11111에서 버킷 오버플로 되는 경우에만 갱신
-예 : white, blue, lilac, red, green을 삽입한경우
- red, white, blue는 버킷 85에 저장 : 테이블 엔트리는 01000
- lilac은 버킷 90에 저장 : 테이블 엔트리는 그대로 11111
green을 삽입 하면
- green의 홈 버킷은 85, 시그니처는 3 (00011)
- 버킷 85는 만원이기 때문에 시그니처 정렬을 통해 green은 버킷 85에 삽입
- 오버플로된 blue는 재 삽입 리스트에 첨가시켜 대기
- 버킷 85에 대한 테이블 엔트리는 8(01000)에서 6(00110)으로 갱신

검색이 아주 빠르기 때문에 log-in용 id를 확인하는 화일 조직에 효율적임
- 검색 시 해싱 함수는 검색할 레코드 키로부터 일련의 <버킷 주소i, 시그지처i>을 생성
다음 조건을 만족하는 가장 i를 선정
- 시그니처i < 버킷 i의 테이블 엔트리
  - 버킷 i에서 레코드 검색
예 : white 검색시, 해싱 함수가 생성한 <버킷주소, 시그니처>를 테이블 엔트리와 검사해서 검색할 버킷 주소를 결정
- 해싱함수 : <85, 00101>, <87, 01001>, <89, 10100>....
- 시그니처 (85, 00101) < 버킷 85의 테이블 엔트리 (01000)
- 따라서 검색할 버킷 주소는 85

화일 레코드 수의 변화가 큰경우에 대한 해결방안
k : 어느 한 시점에서 화일에 저장된 레코드 수
Kmin ≤ K ≤ Kmax
Span = Kmax/Kmin
- SPAN이 클때 문제가 됨
화일 크기가 고정되어 있을때
K ~ Kmin :공간 이용률 낮음
K ~ Kmax : 적재 밀도가 높음
- 저장과 검색 시간이 길어짐
- 해결 방안은 재 해싱
  - 많은 시간 소요
  - 재 해싱 동안 접근 제한

해시 함수(H0)로 레코드 저장할 버킷을 결정
- 해싱 함수 H0는 키 값을 레벨 0의 인덱스N 으로 변환
- 레코드를 저장할 버킷은 이 인덱스 엔트리로 접근
- 버킷이 만원이 아니면 레코드를 저장하고 만원이면 버킷을 분할하고 C+1레코드를 나누어 분산 저장
- 이때 이 인덱스 노드는 다음 하위 레벨의 두인덱스를 위해 왼쪽(old) 오른쪽(new) 서브트리를 갖는 이진트리가 됨
버킷 분할과 레코드 분산 방법
- 분산 저장해야될 레코드의 버킷이 왼쪽인지 오른쪽인지는 비트 함수 B로 결정
  - 비트함수 B : 키 값을 임의의 길이 비트 스트링으로 변환
- 인덱스가 분기되는 레벨이 i 이면 비트스트링 i+1째 비트를 이용하여 이 비트가 0 이면 왼쪽 1이면 오른쪽으로 분기