8장 직접 파일.

Presentation on theme: "8장 직접 파일."— Presentation transcript:

1 8장 직접 파일

2  직접 화일의 개념 각 레코드를 직접 접근 키 값과 물리적 주소 사이에 예측 가능한 관계가 존재
R : 키 값 → 주소(보조 기억 장치: DASD) ┗━(사상 함수) 장점 빠른 직접 접근 → 대화식의 처리 목표 레코드 외에는 접근할 필요 없음 다른 레코드에 영향없이 검색, 삽입, 수정, 삭제 가능

3 ▶ 직접 파일의 예 은행 온라인 시스템 고객 계좌 화일 트랜잭션 형식 트랜잭션 유형 I : 해당 계좌의 이자액
C, D : 금액, 날짜를 해당 계좌 번호의 레코드에 반영, 직접 화일에 재수록 계좌 번호 날짜 지출 예입 잔액 적요 계좌 번호 트랜잭션 번호 금액 날짜

4  해싱 레코드 : 주소 해싱 함수(hashing function) 애트리뷰트(기본키) -> 화일내의 레코드
가능한 주소 공간>>실제 주소공간>레코드의 수 논리적 - 물리적 독립성 키 값들은 주소 공간에 독립적 키 값은 그대로두고 해쉬 함수만 조정 해싱 함수(hashing function) 키 공간을 주소 공간으로 사상 hash(키) -> 주소 주소 ⊂ 유효 키 공간

5 ▶ 해싱의 특성 해싱(hashing) 레코드 검색 키에서 변환되어 나온 주소에 레코드를 저장하는 과정
키 -> 주소 -> 레코드 접근 순차화일 : 레코드 탐색시간 ∝ 레코드수 해싱 : 레코드 탐색시간 NOT ∝ 레코드수

6 ▶ 설계 요소 버켓 크기 적재율 저장된 화일의 레코드 수 ----------------------- 버켓의 총용량 해싱 함수
화일에서 같은 주소에 포함될 수 있는 레코드 수 적재율 저장된 화일의 레코드 수 버켓의 총용량 해싱 함수 주소 생성을 위한 변환 절차 오버플로우 해결 기법 버켓의 오버플로우

7  버켓 크기 버켓 하나의 물리적 레코드 : 한번의 접근으로 채취 가능한 레코드수 충돌(Collision)
같은 해싱 주소를 가지는 화일의 한 구역 하나의 물리적 레코드 : 한번의 접근으로 채취 가능한 레코드수 충돌(Collision) 두개의 레코드가 동일 버켓으로 해싱 동거자(synonym) - 동일 주소로 해싱된 두 키 충돌 vs. 버켓에서의 탐색 시간

8  적재 밀도(Packing Density)
화일이 full -> 논리적 접근수 증가 빈공간 증가 -> 기억장소의 비효율 홈 버켓 해싱 함수에 의해 생성된 주소 화일의 레코드 수 적재밀도 = 홈 버켓의 총 용량 70% 이상이면 충돌 급증

9 ▶ 오버플로우 확률 N : 홈버켓수 C : 버켓 용량 K : 화일에 저장된 레코드 수 K
적재밀도 = < 1 CN 예 : 30% 예비 화일 공간 목표 레코드 수 : 60,000 버켓 크기 : 12 홈 버켓수 = (60,000/12)·(10/7) = 7,143 -> 오버플로우 비율 : 2.13 % (뒤에 표 참조) 1,278 오버플로우 레코드에 대한 대비

10 ▶ 예상 파일 오버플로 버켓크기 적재 밀도(%) 50 55 60 65 70 75 80 85 90 95 2 10.27 11.90
13.56 15.25 16.94 18.65 20.35 22.04 23.71 25.37 3 5.92 8.29 8.75 10.30 11.92 13.59 15.30 18.05 18.81 20.58 5 2.44 3.36 4.45 5.68 8.07 8.58 10.21 11.93 13.73 15.60 8 0.83 1.33 2.01 2.87 3.94 5.20 6.65 8.26 10.03 12 0.24 0.47 0.84 1.38 2.13 3.11 4.33 5.79 8.48 9.36 17 0.06 0.15 0.32 0.63 1.12 1.85 2.84 4.12 5.69 8.53 23 0.01 0.04 0.12 0.28 0.58 1.08 1.86 2.96 4.40 6.18 30 0.11 0.29 1.22 2.14 3.45 5.16

11  해싱 함수 변환 함수 : 키 -> 버켓주소 해싱함수 계산시간 << 보조기억장치의 버켓 접근 시간
모든 주소에 대한 균일한 분포 주소 변환 과정 ① 키가 숫자가 아닌 경우 정수값(A)으로 변환 키 → A ② 변환된 정수값(A)을 주소 공간의 자리수 만큼의 정수값(B)으로 변환 A → B (균일 분포) ③ 얻어진 정수값(B)을 주소공간의 실제범위에 맞게 조정 B → 주소 ★ ② → 해싱함수

12 (1) 제산 잔여 해싱 주소 = 키값 mod 제수 = 키값 - 키값/ 제수 * 제수 → 0 ∼ 제수-1 제수
= 키값 - 키값/ 제수 * 제수 → 0 ∼ 제수-1 제수 직접 주소공간의 크기를 결정(0 ∼ 제수-1) 제수 > 화일의 크기 충돌 가능성이 가장 적은것으로 선택 소수 20보다 작은 소수를 인수로 갖지 않는 비소수

13 ▶ 제산 잔여 해싱의 적재율과 성능 적재율 실제 레코드의 수
= 적재할 수 있는 최대 레코드의 수 적당한 성능 최대허용치 0.7 ∼ 0.8의 적재율 n 레코드 -> 1.25n의 주소공간

14 ▶ 제산 잔여 해싱 예

15 (2) 중간 제곱 해싱 (Mid square hashing)
→ ┗━┛ 9412 * 0.7 = 6588 ( 0 < 주소 ≤ 7000 )

16 ▶ 중간 제곱 해싱 예

17 (3) 중첩(Folding) 키 값을 주소와 같은 자리수를 가지는 몇개의 부분으로 나눔 접어서 합을 구함 예)
주소 크기(4숫자), 키값( ) 1 2345 6789 1 2 3 4 5 6 7 8 9 1 주소

18 ▶ 중첩 해싱 예

19 (4) 숫자 분석 키 값이 되는 숫자의 분포 이용 키의 모든 자리수에 대한 빈도 테이블 주소로 사용될 숫자의 위치들을 선택
↖ 균일한 분포(같은빈도수)

20 (5) Exclusive-OR 변환 Ex-OR 0  0 = 0 1  0 = 1 0  1 = 1 1  1 = 0
0  0 = 0 1  0 = 1 0  1 = 1 1  1 = 0 키의 길이가 길때 제산잔여 방법을 적용하기 전에 수행 EX-OR : procedure (arg1, arg2) Retuen((arg1 OR arg2) AND (NOT(arg1 AND arg2))); END EX-OR; Addr = EX-OR(Keypart1, Keypart2); Ex-OR('RA', 'MA') = Ex-OR('MA', 'RA')

21 (6) 숫자 이동 변환 ① 중앙을 양분 ② 안쪽으로 shift ③ 주소 범위에 맞도록 조정 (조정 상수)
주소 공간 : 5000 6912 * 0.5 = 3456 : 실제 주소

22 (7) 진수 변환 ① 키 값의 진수를 다른 진수로 변환 ② 초과하는 높은 자리수를 절단 예) 172148 : 키 값
: 키 값 주소공간 : 7000 진수 : 11 1   113 + 1    110 = 보정 : 6373 * 0.7 = 4461

23  오버플로 해결 방법 오버플로 해결 방법 폐쇄 주소법 (체인법) 삽입할 레코드가 꽉 찬 버켓에 해싱될 때 개방 주소법
계산 접근법 탐색할 버켓의 주소를 동적으로 계산 폐쇄 주소법 (체인법) 자료구조 접근법 오버플로 버켓을 체인으로 홈 버켓에 연결

24 (1) 개방 주소법 선형 조사(탐색) 다음의 빈 공간을 순차적으로 탐색 Ai = f(i, 키) i = 0,1,2,...
ex) Ai = (i  step + hash(키)) mod N 원하는 레코드/빈 레코드까지 조사 문제점 기본 집중 - 비선형 함수 사용 2차 집중 - 이중 해싱 사용

25 ▶ 이중 해싱 재 해싱 첫 번째 해싱 함수의 결과에 두 번째의 해싱함수를 적용시킨다.
A0 = h1(키) A1 = A0 + h2(키) mod 화일의 크기 재 해싱된 주소는 메인 화일의 주소 (또는 오버 플로우 구역)가 될 수 있다. 주의: 적재 인자(load factor)가 크다.(≒ 80%) 이중 해싱이 선형조사보다 낫다.

26 ▶ 개방 주소법의 문제 레코드의 삭제 논리적 삭제 재해싱 삭제된 레코드를 공간으로 처리 이후의 오버플로 검색 실패 삭제 표시
이후의 레코드를 삭제후 재삽입

27 (2) 폐쇄 주소법 체인법 별도의 리스트 유지, 홈 버켓에서 연결 연합 리스트 디렉토리 방법 포인터 공간 문제
홈 버켓의 여분의 공간에 저장 포인터 공간 감소 검색 비용 증가 디렉토리 방법 오버플로 레코드의 키/포인터 저장

28  테이블 이용 해싱 보조기억장치를 한번 접근으로 검색 각 버켓을 위한 엔트리 테이블을 주기억장치에 유지
버켓 주소와 사인 순열 키 버켓 주소 사 인 White Blue Lilac Red Green … … … … … … … … …

29 ▶ 테이블 이용 해싱을 이용한 삽입 버켓 주소에 따라 삽입 오버플로의 경우
버켓 크기 = 3, RED 삽입할 때 RED (사인 = 2) WHITE (사인 = 5) BLUE (사인 = 6) LILAC (사인 = 8) 분리 사인 선택 (8 선택) => 테이블 엔트리 RED, WHITE, BLUE => 버켓85 LILAC => 버켓90, 사인=20(10100)

30 ▶ 테이블 이용 해싱을 이용한 검색 검색 키로부터 정보 생성 버켓1, 버켓2, 버켓3, ...
사인1, 사인2, 사인3, ... 다음을 만족하는 가장 작은 i 사인i < 테이블[버켓i] 검색 레코드는 버켓i에 존재

31  확장성 직접 화일 레코드수의 변화가 큰 경우 해결방안 재해싱 확장성 화일 긴 시간, 재해싱 동안 접근 곤란 가상 해싱
동적 해싱 확장 해싱

32 (1) 가상 해싱(Virtual hashing)
여러 개의 관련된 해쉬함수 사용 제산 잔여기법 사용 N : 버켓의 수 C : 버켓 크기 h0 : 주소 = 키 mod N 오버플로우: 관련된 버켓을 분할 hj : 주소 = 키 mod (2j * N), j = 0,1,2,.... C+1개의 레코드를 재해쉬

33 ▶ 가상 해싱(Virtual hashing) 예
N = 100, C = 5, 버켓 53 = [ 53, 353, 253, 2453, 52753] h0 : 주소 = 키 mod 100 → 새원소 23753, h1 : 주소 = 키 mod 200 버켓 53 = [53, 253, 2453] 버켓 153 = [353, 52753, 23753] 새원소 3453, 5453, 7453, h2 : 주소 = 키 mod 400 버켓 53 = [53, 2453] 버켓 253 = [253, 3453, 5453, 7453]

34 (2) 동적 해싱(Dynamic hashing)
해쉬된 주소로서 인덱스를 사용 두 단계의 조직 인덱스: 주 기억 장치 버켓 : 보조 저장 장치 두 개의 해쉬 함수 사용 h : 인덱스 레벨 0 B : 인덱스 레벨 > 0 분기를 결정 레코드는 인덱스의 포인터에 의해 접근됨 키 → 인덱스(1 ∼ N) 인덱스 : N개의 이진트리의 포리스트(forest) 인덱스 노드 내부노드(0, 부모, 왼쪽 자식, 오른쪽 자식) 외부노드(1, 부모, 레코드 수, 버켓 포인터)

35 ▶ 초기의 동적 화일

36 ▶ 버켓 분할 B함수 사용 : 키 → 이진 스트링 분할 되는 버켓이 레벨 I이면 B(키)의 I+1째 비트를 사용
∴ 0 왼쪽(이전) 버켓 1 오른쪽(새로운) 버켓 H0와 B에 대한 예 키 H0(키) B(키) 157 2 10100 … 95 1 00011 … 88 01100 … 205 10010 … 13 10111 … 125 10001 … 6 01000 … 301 00110 …

37 ▶ 5번의 삽입 후의 동적 화일

38 ▶ 분할 뒤의 화일

39 ▶ 함수 B의 구현 어떤 h1에 대해 h1: 키 → X0 Xi+1 ← (Xi * a + b) mod C Xi:정수
bi ← 패리티(Xi) 키 ↓ X0 → X1 → X2 → X3 → .... ↓ ↓ ↓ ↓ b b b b

40 (3) 확장성 해싱(Extendible hashng)
두 단계의 조직 디렉토리 : 정수 값(d)을 갖는 헤더와 리프에 대한 2d개의 포인터 리프의 집합 : 헤더를 가지는 버켓 하나의 해쉬함수 사용 h : 키 -- 모조키 (고정 길이의 비트 스트링) 리프의 헤더 : 버켓 레코드에 대한 공통 전위 비트의 개수

41 ▶ 확장성 해싱의 검색과 삽입 검색 모조 키의 처음 d비트를 디렉토리에 대한 인덱스로 사용하여 디렉토리에서 리프를 찾아 레코드를 접근 삽입 리프를 찾아(검색과 같은 방법) 삽입 리프가 가득 찼으면 ① 새로운 리프 할당 ② 리프의 헤더가 T이면, 모조키의 T+1 번째 비트의 값에 따라 C+1개의 레코드를 분할 ③ T, d의 값에 따라 d≥T+1 : 포인터들을 분할, 이전의 리프와 새로운 리프 모두 T+1의 헤더를 가짐 d<T+1 : 디렉토리의 크기를 두 배로, d←d+1

42 ▶ 확장성 해싱 화일

43 ▶ 리프 분할 뒤의 화일

44 ▶ 리프 분할 뒤의 화일