8장 직접 화일

 직접 화일의 개념 임의 접근 화일(random access file) 직접 화일의 종류 임의의 레코드 키 값으로 그 레코드를 접근할 수 있는 화일 직접 화일(direct file), 직접 접근 화일(direct access file) 다른 레코드를 참조하지 않고 특정 레코드 접근이 가능 ↔ 순차 접근 화일 직접 화일의 종류 인덱스된 화일(indexed file) 인덱스를 이용해 레코드를 접근 인덱스된 순차 화일(indexed sequential file) 인덱스를 이용한 임의 접근/순차 접근을 모두 지원 상대 화일(relative file) 키와 화일 내 레코드의 상대적 위치 사이에 정해진 관계를 이용해 레코드를 접근 해시 화일(hash file) 키 값을 레코드 주소로 변환하여 레코드를 접근 협의의 직접 화일

▶ 상대 화일 (relative file) 레코드의 키와 화일 내 레코드의 위치(상대 레코드 번호) 사이에 설정된 관계를 이용해 레코드를 접근 상대 레코드 번호(relative record number, RRN) 화일이 시작되는 첫 번째 레코드를 기준으로 레코드들에 0, 1, 2, 3, …, N-1을 지정 이 RRN을 상대 주소(relative address)라고 함 ※ 레코드의 논리적 순서와 물리적 순서는 무관 ※ 레코드들이 키 값에 따라 물리적으로 정렬되어있을 필요도 없음

▶ 상대 화일 (relative file)

▶ 사상 함수 (mapping function) 레코드 기록 시 : 키 값 → 레코드가 저장될 주소 레코드 검색 시 : 키 값 → 레코드가 저장되어있는 주소 모든 레코드에 직접 접근이 가능 → 상대 화일은 메인 메모리, 디스크 등 직접 저장 장치(DASD: Direct Access Storage Device)에 저장하는 것이 효율적 사상 함수(A)의 구현 방법 직접 사상(direct mapping) 디렉터리 검사(directory lookup) 계산(computation) 을 이용한 방법 e.g., 해싱 A : 키 값 → 주소

▶ 직접 사상(direct mapping) 절대 주소 (absolute address)를 이용 레코드의 실제 주소(절대 주소)를 키 값으로 사용 화일에 레코드가 처음 저장될 때 레코드의 절대 주소, <실린더 번호, 면 번호, 블록 번호>가 결정 장점 키 값 →주소 변환 과정이 간단하고, 처리 시간이 거의 걸리지 않음 단점 물리적 저장장치에 전적으로 의존 물리적 데이타 독립성이 결여

▶ 디렉터리 검사(directory lookup) 상대 화일 접근을 위해 <키 값, 상대 주소> 쌍을 엔트리로 갖는 테이블, 즉 디렉터리(directory)를 유지 레코드 검색 디렉터리에서 키 값을 검색하여 그 키 값에 대응되는 레코드 번호(상대 주소)로 저장된 레코드를 접근 장점 검색이 빠름 단점 레코드 삽입 시간이 많이 걸림 화일 구조 유지를 위해 화일과 디렉터리 재구성이 필요하게 됨

▶ 디렉터리를 통한 상대 화일 접근

 해싱(hashing) 계산(computation)을 이용한 사상 함수 구현법 일반적으로, 주소 공간(address space) >> 키 값 공간(key value space) 13 자리의 주민등록번호 예 가능한 주민 등록 번호와 1:1이 되는 주소의 수 : 1013 실제 유효 주민 등록 번호의 수: 약 108 (=1억) 이하 모든 가능한 주민등록 번호에 빈 레코드 주소를 할당한다면? → 막대한 저장 공간 낭비 ∵ 1013 >> 108 1억 개 미만의 레코드 공간을 갖는 화일을 만드는 것이 효율적 해싱(hashing) 해싱 함수(hashing function)를 이용하여 키 값을 주소로 변환하여, 이 변환된 주소에 레코드를 저장하는 것 해시 주소(hashed address) 해싱 함수가 키 값으로부터 변환한 주소 해시 화일(hash file) 해싱 기법으로 운영되는 화일

▶ 해싱 함수 해싱 함수 (hashing function) 키 공간을 유효 주소 공간으로 사상(mapping) 해싱 함수는 키 값들을 한정된 주소 공간으로 균등하게 분산시키는 것이 가장 중요

▶ 해시 화일 설계 시 고려사항 해시 화일(hash file) 설계 시 고려 사항 해싱 기법으로 운영되는 화일 ① 버킷(bucket) 크기 하나의 주소를 가진 저장 구역에 저장할 수 있는 레코드의 수 ② 적재율 총 저장 용량에 대한 실제로 저장되는 레코드 수의 대한 비율 ③ 해싱 함수 레코드 키 값으로부터 주소를 생성하는 방법 ④ 오버플로 해결 방법 주어진 주소 공간이 만원이 된 경우의 해결 방법

▶ 버킷 버킷(bucket) 버킷 크기 하나의 주소를 가진 한 저장 구역 이 버킷에 지정된 주소를 버킷 주소(bucket address) 레코드 저장이나 검색 시 지시하는 저장 공간(주소) 하나 이상의 레코드 저장 가능 같은 버킷 안의 모든 레코드는 같은 버킷 주소를 가짐 화일을 구성하는 버킷 수가 이 화일을 위한 해싱 함수의 주소 공간(address space)이 됨 버킷 크기 버킷에 저장할 수 있는 레코드 수 통상적으로 한 번의 접근으로 버킷 내에 있는 모든 레코드들을 전송할 수 있는 크기로 결정 저장 장치의 물리적 특성과 연관

▶ 버킷 충돌(collision) 버킷 크기를 크게하면 두 개의 상이한 레코드가 똑같은 버킷으로 해싱되는 경우 같은 주소로 해싱되어 충돌된 키 값들을 동거자 (synonyms)라 함 버킷이 만원인 경우에는 충돌이 문제가 됨. 즉 오버플로 (overflow)가 발생 오버플로를 해결하기 위한 추가적인 작업은 해싱 기법의 오버헤드가 됨. 버킷 크기를 크게하면 장점 오버플로 발생 확률이 감소 단점 저장 공간의 효율성이 감소 버킷 내 레코드 탐색 시간이 증가

▶ 적재 밀도(loading density) (1) 적재 밀도(loading density) (=패킹 밀도(packing density) ) N : 버킷의 수 c : 버킷의 크기 K : 화일에 저장된 레코드 수 적재 밀도 = 저장된 레코드 수 화일 저장 공간의 총 용량 = K < 1 c * N

▶ 적재 밀도(loading density) (2) 적재 밀도가 높으면 삽입/검색 시 접근 시간이 길어짐. 왜냐하면 이미 여러 레코드가 지정된 주소에 저장되어 있을 확률이 높아 다른 주소를 검색해야 되는 경우가 발생 적재 밀도가 낮으면 공간 효율이 떨어짐 실험적으로, 적재밀도가 70% 이상이 되면 충돌 가능성이 높음. 30% 정도의 자유 공간을 예비하는 것이 바람직함 예) 학생 레코드 검색 시스템 학생 수 최대 60,000명, 자유 공간 30%, 버킷 크기 12 버킷 수 = 60,000/12*0.7 = 7,143

▶ 해싱 함수(hasing function) 해싱 함수 계산시간 << 디스크의 버킷 접근 시간 모든 주소에 대해 균일한 분포를 갖는 것이 좋음 주소 변환 과정 ① 키가 숫자가 아닌 경우, 키를 정수 값(A)으로 변환 키 → A 변환된 정수 A를 주소 공간의 자리 수 크기의 정수 B로 변환 A → B ③ 얻어진 정수 B를 주소 공간의 실제 범위에 맞게 조정 B  조정 인수 → 주소

(1) 제산 잔여(divide and remainder) 해싱 h(key) = key mod d = 키 값 mod 제수 → 0 ∼ d-1 제수(d) 직접 주소 공간의 크기를 결정(0 ∼ d-1) d > 화일의 크기 제수는 충돌 가능성이 가장 적은 것으로 선택 소수(prime number) 20보다 작은 소수를 인수로 갖지 않는 비 소수이면 좋은 성능 기대

▶ 제산 잔여 해싱의 성능(1) 적당한 성능을 위한 적재율 최대 허용치는 0.7 ∼ 0.8 n 개의 레코드 → 1.25n 주소 공간(80%의 경우) (예) 레코드 4000개, 적재율 80% 주소 공간 = 4,000 / 0.8 = 5,000 개의 주소 공간이 필요 제수 : 5003 20 이하의 소수 인자를 갖지 않는 수 중 5000에 가장 가까운 수를 선택한 경우

▶ 제산 잔여 해싱의 성능(2) 제수 5003인 제산 잔여 해싱 예

(2) 중간 제곱 (Mid-square) 해싱 ① 키 값을 제곱 ② 중간에서 n개(주소 공간)의 수를 취함 예) 레코드가 4000개인 경우 최소 4 자리의 주소 공간이 필요 키를 제곱한 수에서 4자리 수를 취함 ※ 주소 공간이 아주 큰 경우, 적절한 조정 인수를 곱해 주소 공간을 조절

▶ 중간 제곱 해싱 중간 제곱 잔여 해싱 예 뒤에서부터 7~10자리 수를 주소로 취함

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

▶ 중첩 해싱

(4) 숫자 추출(digit extraction) 방법 키 값이 되는 숫자의 출현 분포를 이용 균등하게 분산 사용된 숫자 위치들을 주소 자리 수만큼 선정 키들의 모든 자릿수에 대한 빈도 테이블을 만들어 분석 예 9-자리 레코드 키 값을 분석하여 4개의 균등한 숫자 위치로 9번째, 7번째, 5번째, 2번째 위치가 선정되었다고 가정 주어진 레코드 키 값: 546032178 변환된 레코드 주소: 8134

(5) 숫자 이동(shifting) 변환 ② 주소 길이만큼 겹치도록 안쪽으로 각각 이동(shift)하여 합산 ① 키를 중앙을 중심으로 양분 ② 주소 길이만큼 겹치도록 안쪽으로 각각 이동(shift)하여 합산 ③ 주소 범위에 맞도록 조정 (조정 인수 사용) 주소 공간 : 5000 변환된 레코드 주소: 6912 * 0.5(조정 인수) = 3456

(6) 진수 변환(radix conversion) ① 키 값의 진수(base)를 다른 진수로 변환 ② 초과하는 높은 자리 수를 절단 ③ 주소 범위에 맞도록 조정 (조정 상수 사용) 예) 키 값: 172148 주소공간: 7000 조정 인수: 0.7 진수: 11 변환주소 1 115 + 7  114 + 2  113 + 1  112 + 4  111 + 8  110 = 266373 조정 : 6373 * 0.7 = 4461

충돌과 오버플로 키 값 공간이 주소 공간보다 크기 때문에 충돌 발생이 불가피 오버플로(overflow) 해결 방법 하나의 홈 주소(home address) 또는 홈 버킷(home bucket)으로 충돌된 동거자들을 한 버킷에 모두 저장할 수 없는 경우 홈 주소: 해싱 함수가 생성한 버킷 주소 해결 방법 선형 조사(linear probing) 독립 오버플로 구역(separate overflow area) 이중 해싱(double hashing) 동거자 체인(synonym chaining) 버킷 체인(bucket chaining) ※ 이하, 버킷 크기 = 1로 가정

선형 조사 (linear probing) 오버플로 발생시, 홈 주소에서부터 차례로 조사해서 가장 가까운 빈 공간을 찾는 방법 해당 주소가 공백인지 아닌지를 판별할 수 있게 플래그(flag)를 이용 insertLinear(key)       addr ←  h(key);      home-addr ←  addr;      while (addr is full) do {         addr ←  (addr + 1) mod N;         if (addr = home-addr ) {            print ("file is completely full");            return;         }      }      insert the key at addr;      set the addr is full; end insertLinear()

▶ 선형 조사 이용시의 저장/검색/삭제 저장 검색 삭제 원형 탐색 : 빈 저장 공간 조사는 홈 주소에서 시작하여 화일 끝에서 끝나는 것이 아니라 다시 화일 시작으로 돌아가 홈 주소에 도착할 때 종료 (화일이 만원) 검색 레코드 저장 시에 선형 조사 방법을 사용했다면 검색 시에도 선형 조사 방법을 사용해야 함 탐색 키 값을 가진 레코드가 없거나 홈 주소에서 멀리 떨어져있는 경우, 많은 조사 필요 삭제 삭제로 생긴 빈 공간으로 검색 시 선형 조사가 단절될 수 있음 → 삭제 표시(tombstone)가 필요 삭제된 자리에 삭제 표시를 해서 선형 조사가 단절되지 않게 함

▶ 선형 조사의 단점 (1) (1) 어떤 레코드가 화일에 없다는 것을 판단하기 위해 조사해야 할 주소의 수가 적재율이 높아질수록 많아짐 적당한 적재율 유지 필요 (2) 환치(displacement) 한 레코드가 자기 홈 주소를 동거자가 아닌 다른 오버플로된 레코드가 차지함으로 인해 다른 레코드의 홈 주소에 저장되는 것 환치는 또 다른 환치를 유발 탐색할 주소 수의 증가는 삽입/검색 시간 증가를 야기 대응책으로는 처음 화일을 생성할 때 2-패스 해시 화일 생성(two-pass hash file creation) 방법을 이용

▶ 선형 조사의 단점 (2) 2-패스 해시 화일 생성(two-pass hash file creation) 첫 번째 패스 모든 레코드를 해시 함수를 통해 홈 주소에 저장 오버플로된 동거자들은 바로 저장하지 않고 별도로 임시 화일에 저장 두 번째 패스 첫 번째 패스가 모두 끝나면 임시 화일에 저장해 둔 오버플로 동거자들을 선형 조사를 이용해 전부 적재 1-패스 화일 생성에 비해 훨씬 많은 레코드들이 원래의 자기 홈 주소에 저장됨 화일을 생성하기 전에 레코드 키 값들을 미리 알면 효율적 화일이 생성된 뒤에 레코드들이 추가될 때는 환치 발생 가능성이 있음

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

(3) 이중 해싱(double hashing) 오버플로된 동거자들을 오버플로 구역으로 직접 해시 오버플로 구역에서의 순차 탐색을 피할 수 있음 2차 해싱 함수(second hashing function)를 이용 오버플로된 동거자를 해시하는 함수 해싱 과정 1차 해싱 함수에 의해 상대 화일로 해시 오버플로가 발생하면 오버플로 구역으로 해시 오버플로 구역 주소 = (1차 해시 주소 + 2차 해시 주소) mod (오버플로 구역 크기) 오버플로가 재차 일어나면 선형 탐색을 이용

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

▶ 동거자 체인 예 동거자 체인과 독립 오버플로 구역 예

5) 버킷 체인(bucket chaining) 동거자 체인과 비슷 홈 버킷에서 동거자 오버플로가 일어나면 별개의 버킷을 할당받아 오버플로된 동거자를 저장하고 홈 버킷에 이 버킷을 링크로 연결 장점 : 재 해싱이 불필요 독립 오버플로 구역 사용시 환치 문제가 없음 단점 : 각 주소가 링크 필드를 포함할 수 있도록 확장해야 함 최악의 경우 한 레코드를 탐색하기 위해서는 그 홈 버킷에 연결된 모든 오버플로 버킷을 조사해야 됨

▶ 버킷 체인의 성능 레코드 탐색 어떤 다른 방법보다도 평균 조사 수가 적음 버킷 체인

 테이블 이용 해싱(table-assisted hashing) 저장장치에 한번의 접근으로 레코드 검색을 보장 레코드 삽입 시간은 많이 걸리지만 검색은 매우 빠름 해싱 함수는 각 레코드에 대해 일련의 <버킷 주소i, k-비트 시그너쳐i> 쌍을 생성(i=1, 2, 3, …) <addr1, sign1>, <addr2, sign2>, <addr3, sign3>, … 각 버킷에는 하나의 엔트리(k-비트 시그너쳐)로 된 버킷 테이블을 유지 화일 접근 시에 이 버킷 테이블은 전부 메인 메모리에 상주

▶ 테이블 이용 해싱 해싱 함수가 생성한 버킷 주소와 5-비트 시그너쳐 예 키 버킷 주소 5-비트 시그너쳐 White Blue 해싱 함수가 생성한 버킷 주소와 5-비트 시그너쳐 예 키 버킷 주소 5-비트 시그너쳐 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 …

▶ 테이블 이용 해싱을 통한 삽입(1) 레코드 삽입 예 3 번째 Lilac을 삽입하면 버킷 85는 만원이 됨 버킷 크기: 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에 대한 버킷 테이블 엔트리로 저장 버킷에는 항상 분리 시그너쳐 값보다 작은 레코드만 저장

▶ 테이블 이용 해싱을 통한 삽입(2) 이 분리 시그너쳐 값보다 작은 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=1, 2, 3, …을 생성 다음 조건을 만족하는 가장 작은 i를 선정 시그너쳐i < 버킷 i의 테이블 엔트리, i=1, 2, 3, … 버킷 i에서 레코드를 검색 예: White 검색 시, 해싱 함수가 생성한 <버킷 주소, 시그너쳐>를 테이블 엔트리와 검사해서 검색할 버킷 주소를 결정 해싱 함수: <85, 00101>, <87, 01001>, <89, 10100>, … 시그너쳐 (85, 00101) < 버킷 85의 테이블 엔트리(01000) 따라서, 검색할 버킷 주소는 85

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

▶ 확장성 직접 화일 (2) 확장성 화일(extendible file) 확장성 화일의 유형 높은 SPAN 값을 가진 화일에 대한 해싱 기법 버킷 크기는 일정 버킷 수는 가변 오버플로 버킷은 사용하지 않음 삭제는 간단 검색은 1-2회의 접근만 필요 확장성 화일의 유형 가상 해싱(virtual hashing) 동적 해싱(dynamic hashing) 확장성 해싱(extendible hashing) 선형 해싱(linear hashing)

(1) 가상 해싱(Virtual Hashing) 여러 개의 해싱 함수를 사용 해싱 함수는 제산 잔여 기법을 기초 h0 : 주소 = 키 mod N N : 버킷의 수, C : 버킷 크기 오버플로우가 되면 버킷의 C 레코드와 삽입하려는 레코드를 합한 C+1개의 레코드를 새로운 해싱 함수를 사용해서 재 해싱 재 해싱 함수 hi hi : 주소 = 키 mod (2i * N), i = 0, 1, 2, ... h1 : 주소 = 키 mod 2N h2 : 주소 = 키 mod 4N

▶ 가상 해싱 예(1) (예) 버킷 수 N=100, 버킷 크기 C=4 레코드 3, 103, 203, 303을 첫 번째 해싱 함수 h0: 주소 = 키 mod 100 을 이용해 삽입 버킷 3 = [3, 103, 203, 303]으로 만원 다음 레코드 403을 삽입할 때 오버플로가 발생. 따라서 두 번째 해싱 함수 h1(키 mod 2x100)을 이용해 버킷 3과 103으로 분할

▶ 가상 해싱 예(2) 추가로 필요한 기법 세 번째 해싱 함수 h2(키 mod 4x100)을 이용해 버킷 3과 203으로 분할 다음 레코드 603, 803을 삽입할 때, 버킷 3은 오버플로가 됨. 세 번째 해싱 함수 h2(키 mod 4x100)을 이용해 버킷 3과 203으로 분할 추가로 필요한 기법 각 버킷에 적용된 해싱 함수를 유지하는 기법 검색할 키 값에 적용할 해싱 함수 hk를 알 수 있는 기법 레코드 603을 검색할 때 해싱 함수 h2 즉 주소= 키 mod 4x100을 찾아서 적용하여 주소 203을 구해야 한다.

(2) 동적 해싱(Dynamic Hashing) 화일 구성 크기가 C인 N개의 버킷(bucket)과 각 버킷을 지시하는 인덱스(index)로 구성 버킷은 저장장치에 할당되고 인덱스는 메인 메모리에 상주 예: N=20이고 C=3일 때 초기 동적 해시 화일 초기에 인덱스는 하나의 레벨(레벨 0)

▶ 동적 해시 화일에서의 레코드 삽입(1) 해싱 함수(H0 )로 레코드를 저장할 버킷을 결정 버킷 분할과 레코드 분산 방법 해싱 함수 H0는 키 값을 레벨 0의 인덱스(1 ∼ N)로 변환 레코드를 저장할 버킷은 이 인덱스 엔트리로 접근 버킷이 만원이 아니면 레코드를 저장하고 만원이면 버킷을 분할하고 C+1 레코드를 나누어 분산 저장 이때 이 인덱스 노드는 다음 하위 레벨의 두 인덱스를 위해 왼쪽(old), 오른쪽(new) 서브트리를 갖는 이진 트리가 됨 레코드 삽입으로 버킷이 계속 분할되면 인덱스는 N개의 이진 트리로 된 포리스트가 됨 버킷 분할과 레코드 분산 방법 분산 저장해야 될 레코드의 버킷이 왼쪽인지 오른쪽인지는 비트 함수 B로 결정 비트 함수 B : 키 값을 임의의 길이의 비트 스트링(bit string)으로 변환

▶ 동적 해시 화일에서의 삽입(2) 인덱스가 분기되는 레벨이 i이면 비트 스트링의 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 …

▶ 동적 해시 화일에서의 삽입 예(1) (예) 레코드 157, 95, 88, 205, 13을 삽입한 뒤의 초기 화일

▶ 동적 해시 화일에서의 삽입 예(2) (예) 레코드 125를 삽입할 때 오버플로가 됨. 비트 함수 B가 생성한 비트 스트링의 첫 번째 비트를 이용하여 버킷1을 분할한 뒤의 화일

▶ 동적 해시 화일에서의 삽입 예(3) (예) 레코드 301, 6을 삽입할 때 오버플로가 발생. 함수 B가 생성한 비트 스링의 2 번째 비트를 이용하여 버킷1을 분할한 뒤의 화일

▶ 동적 해시 화일에서의 검색 레코드 검색 버킷의 결정 절차 해싱 함수 H0로 인덱스 레벨 0 의 포리스트를 식별 주어진 레코드 키 값에 대한 함수 B의 비트 스트링 값으로 인덱스 레벨 1부터 분기하여 검색할 버킷을 결정

▶ 비트 함수(bit function) 비트 함수 B의 설계 예 ① 레코드의 키(또는 키에 대한 어떤 함수 H1)를 모조 난수 생성기(pseudo-random number generator)의 초기 값으로 사용하여 정수를 생성 ② 생성된 각 정수를 하나의 비트로 변환 0과 1이 똑같은 확률로 생성될 수 있도록 변환

(3) 확장성 해싱(Extendible hashing) 확장성 해싱 함수(extendible hashing function) h는 키 값을 일정 길이의 비트 스트링 즉 모조키(pseudokey)로 변환 예: h(k) → 101000010001 확장성 해시 화일은 디렉터리와 버킷으로 구성 디렉터리(directory) 일반적인 인덱스에 해당 버킷에 대한 2d 개의 포인터로 구성. 정수 d는 전역 깊이(global depth)로 디렉터리의 크기를 나타냄. 포인터들은 같은 버킷을 가리킬 수도 있음. 버킷(bucket) 레코드들을 실제로 저장하는 공간 각 버킷은 지역 깊이(local depth), p를 표시 이 버킷 깊이 p는그 버킷에 저장된 모든 레코드들의 모조키들이 첫 번째 비트부터 공통으로 가지고 있는 비트 스트링 길이를 말함.

▶ 확장성 해시 화일(1) 초기 확장성 해시 화일의 구축 N개의 버킷으로 시작한다고 할 때, 전역 깊이 d = log (N-1) +1 d는 디렉터리 엔트리 수를 나타내는 지수 디렉터리는 2d 개의 엔트리를 포함 2d 개의 버킷을 가리킬 수 있는 포인터

▶ 확장성 해시 화일 (2)

▶ 확장성 해시 화일에서의 검색 레코드 검색 키 값 k를 가진 레코드 검색 예 레코드에 대해 해싱 함수 h가 생성한 모조키의 처음 d 비트를 디렉터리에 대한 인덱스로 사용 접근한 디렉터리 엔트리로 레코드가 저장되어 있는 목표 버킷을 접근하여 검색 키 값 k를 가진 레코드 검색 예 1) h(k) → 101000010001 2) d=3이기 때문에 모조키의 처음 3 비트를 이용하여 디렉터리의 6번째 엔트리(101)를 접근 3) 이 엔트리는 키 값 k를 가지고 있는 레코드가 저장되어있는 4번째 버킷에 대한 포인터 이 버킷의 p 값 1은 저장된 레코드들의 공통 모조키 비트 수가 1이라는 것 즉, 모든 레코드들의 모조키가 1로 시작한다는 것을 나타냄

▶ 확장성 해시 화일에서의 저장 레코드 저장 만일 그 버킷이 만원이고 버킷 깊이가 p인 경우 저장할 레코드에 대해 해싱 함수가 생성한 모조키의 처음 d 비트를 이용해 디렉터리를 접근하여 포인터가 지시하는 버킷에 레코드를 저장 만일 그 버킷이 만원이고 버킷 깊이가 p인 경우 새로운 버킷을 할당 버킷 크기가 c라 할 때 c+1 레코드들을 각각 자기 모조키의 (p+1) 번째 비트에 따라 두 버킷에 분산 저장 기존 버킷과 새로 할당한 버킷의 깊이 p를 모두 (p+1)로 설정하고 만일 디렉터리 깊이가 d ≥ (p+1)이면 디렉터리의 해당 포인터 엔트리만 조정 만일 디렉터리 깊이가 d< (p+1)이면 디렉터리 깊이 d 값을 1 증가시키고 디렉터리 크기를 2 배로 확장한 다음 포인터 엔트리를 조정

d ≥ (p+1) 인 경우의 예 모조키가 1로 시작하는 버킷 4가 만원인 상태에서 모조키가 10으로 시작하는 레코드를 삽입하는 경우 빈 버킷을 할당하고 버킷 4를 분할하여 모조키 11로 시작하는 레코드들을 이 새 버킷으로 이동 디렉터리 인덱스 110과 111의 포인터 값은 새 버킷을 지시하도록 변경 분할된 두 버킷의 깊이 p를 2로 설정 :d :p

d < (p+1) 인 경우의 예(1) 모조키가 000으로 시작하는 버킷1이 만원인 상태에서 모조키가 0001로 시작하는 레코드를 삽입 디렉터리 깊이 3을 1 증가시켜 디렉터리를 2배로 확장 빈 버킷을 할당 하고 모조키가 0001로 시작하는 레코드들을 이 새 버킷으로 이동 디렉터리 인덱스 0001의 포인터 값은 새 버킷을 지시하도록 변경 분할된 두 버킷의 깊이 p를 4로 설정 디렉터리의 다른 모든 포인터 엔트리를 조정

d < (p+1) 인 경우의 예(2)

▶ 확장성 해시 화일에서의 삭제 삭제할 레코드를 검색 과정으로 찾아 삭제 버킷에 하나만 있는 레코드를 삭제하는 경우 버디 버킷을 검사하여, 두 버디에 있는 레코드들이 한 버킷에 들어갈 수 있으면 합병 버디 버킷(buddy bucket) : 두 버킷이 똑같은 버킷 깊이(p)를 가지고 있고 그 버킷에 있는 레코드 모조 키들의 처음 (p-1) 비트들이 모두 동일한 버킷 이 때 버킷의 새로운 깊이 값은 p-1 모든 버킷들의 깊이 값이 디렉터리 깊이 값보다 작게 되면 디렉터리의 깊이를 하나 감소(d ← d-1) 디렉터리 크기는 반으로 줄어듦 포인터 엔트리들을 적절히 재조정

(4) 선형 해싱(linear hashing) 디렉터리를 사용하지 않는 확장성 해싱 방식 주소 공간이 확장될 때 해시 값의 비트(bits)를 사용 예: 버킷 주소 공간이 4이면 2-비트 주소를 생성하는 2-비트 해싱 함수를 이용 오버플로를 위해 주소 공간을 확장해야 될 때는 항상 선형으로 확장 주소 확장 방법은 한번에 2배로 하지 않고 첫 번째 버킷부터 차례(선형)로 분할해 가면서 마지막 버킷 분할이 끝나면 그 다음 2배 확장을 위해 다시 처음 버킷에서부터 시작하는 사이클 식임.

▶ 선형 해싱 예 (1) 초기에 2-비트 해싱 함수 h2로 2-비트 주소를 생성 레코드 삽입으로 버킷 b에 첫 번째 오버플로 발생 새 버킷 A를 할당해서 첫 번째 버킷 a를 분할. 레코드 분할을 위해 3-비트 해싱 함수 h3를 사용 버킷 b의 실제 오버플로 레코드들은 버킷 w를 할당해서 분할하고 버킷 b와 링크로 연결 버킷 a와 새 버킷 A의 주소는 3-비트 해싱 함수로 접근

▶ 선형 해싱 예 (2) 버킷 d에 두 번째 오버플로 발생 버킷 x에 세 번째 오버플로 발생 새 버킷 B를 할당해서 두 번째 버킷 b와 w를 분산 저장. 레코드 분할을 위해 3-비트 해싱 함수 h3를 사용 버킷 d는 버킷 x를 할당해서 분할하고 링크로 연결 버킷 x에 세 번째 오버플로 발생 새 버킷 C를 할당해서 세 번째 버킷 c를 분할 버킷 x는 버킷 y를 할당해서 분할하고 링크로 연결

▶ 선형 해싱 예 (3) 버킷 B에 네 번째 오버플로 발생 새 버킷 D를 할당해서 네 번째 버킷 d와 x, y를 분산 저장 버킷 B는 버킷 z를 할당해서 분할하고 연결 이제 모든 버킷이 3-비트 해싱 함수를 사용하게 되었음. 따라서 다음 사이클에 분할될 버킷을 가리키는 포인터는 다시 첫 번째 버킷 a를 가리키도록 설정 그리고 새로운 버킷을 생성하여 화일을 확장할 때는 4-비트 해싱 함수 h4를 사용함.

▶ 선형 해싱에서의 검색 두 개의 해싱 함수를 이용해 접근 d-비트의 기본 주소를 가진 버킷에 대해서는 d-비트 해싱 함수 hd(k)를 이용해서 접근 확장 버킷에 대해서는 (d+1)-비트 해싱 함수 hd+1(k)를 이용해서 접근 따라서 레코드의 검색을 위해서는 어떤 해싱 함수를 사용해야 되는지 알아야 함 키 값 k를 가진 레코드를 포함하고 있는 버킷 주소 (address)를 찾기 위한 프로시저 if (hd(k) ≥ p)     address = hd(k); else      address = hd+1(k); p : 다음에 분할할 버킷을 가리키는 포인터