8장 직접 파일

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

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

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

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

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

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

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

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

▶ 예상 파일 오버플로 버켓크기 적재 밀도(%) 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

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

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

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

▶ 제산 잔여 해싱 예

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

▶ 중간 제곱 해싱 예

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

▶ 중첩 해싱 예

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

(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')

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

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

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

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

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

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

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

 테이블 이용 해싱 보조기억장치를 한번 접근으로 검색 각 버켓을 위한 엔트리 테이블을 주기억장치에 유지 버켓 주소와 사인 순열 키 버켓 주소 사 인 White Blue Lilac Red Green 85 87 89 91 93 … 85 86 87 88 89 … 85 90 95 0 5 … 85 92 99 6 13 … 00101 01001 10100 10111 … 00110 00011 00110 10000 … 01000 10100 11000 10100 … 00010 11000 11110 10010 … 00011 00100 10001 00111 …

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

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

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

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

▶ 가상 해싱(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]

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

▶ 초기의 동적 화일

▶ 버켓 분할 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 …

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

▶ 분할 뒤의 화일

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

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

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

▶ 확장성 해싱 화일

▶ 리프 분할 뒤의 화일

▶ 리프 분할 뒤의 화일