8장직접화일 v 직접화일의개념 u 임의접근화일 (random access file) 임의의레코드키값으로그레코드를접근할수있는화일 직접화일 (direct file), 직접접근화일 (direct access file) 다른레코드를참조하지않고특정레코드접근이가능 순차접근화일 u 직접화일의종류 인덱스된화일 (indexed file) 인덱스를이용해레코드를접근 인덱스된순차화일 (indexed sequential file) 인덱스를이용한임의접근 / 순차접근을모두지원 상대화일 (relative file) 키와화일내레코드의상대적위치사이에정해진관계를이용해레코드를접근 해시화일 (hash file) 키값을레코드주소로변환하여레코드를접근 협의의직접화일 2
상대화일 (relative file) u 레코드의키와화일내레코드의위치 ( 상대레코드번호 ) 사이에설정된관계를이용해레코드를접근 u 상대레코드번호 (relative record number, RRN) 화일이시작되는첫번째레코드를기준으로레코드들에 0,, 2, 3,, N-을지정 이 RRN을상대주소 (relative address) 라고함 레코드의논리적순서와물리적순서는무관 레코드들이키값에따라물리적으로정렬되어있을필요도없음 3 상대화일 (relative file) 4
사상함수 (mapping function) u 사상함수 A : 키값 주소 레코드기록시 : 키값 레코드가저장될주소 레코드검색시 : 키값 레코드가저장되어있는주소 모든레코드에직접접근이가능 상대화일은메인메모리, 디스크등직접저장장치 (DASD: Direct Access Storage Device) 에저장하는것이효율적 u 사상함수 (A) 의구현방법 직접사상 (direct mapping) 디렉터리검사 (directory lookup) 계산 (computation) 을이용한방법 e.g., 해싱 5 직접사상 (direct mapping) u 절대주소 (absolute address) 를이용 레코드의실제주소 ( 절대주소 ) 를키값으로사용 화일에레코드가처음저장될때레코드의절대주소, < 실린더번호, 면번호, 블록번호 > 가결정 u 장점 키값 주소변환과정이간단하고, 처리시간이거의걸리지않음 u 단점 물리적저장장치에전적으로의존 물리적데이타독립성이결여 6
디렉터리검사 (directory lookup) u 상대화일접근을위해 < 키값, 상대주소 > 쌍을엔트리로갖는테이블, 즉디렉터리 (directory) 를유지 u 레코드검색 디렉터리에서키값을검색하여그키값에대응되는레코드번호 ( 상대주소 ) 로저장된레코드를접근 u 장점 검색이빠름 u 단점 레코드삽입시간이많이걸림 화일구조유지를위해화일과디렉터리재구성이필요하게됨 7 디렉터리를통한상대화일접근 8
v 해싱 (hashing) u 계산 (computation) 을이용한사상함수구현법 u 일반적으로, 주소공간 (address space) >> 키값공간 (key value space) 3 자리의주민등록번호예 가능한주민등록번호와 : 이되는주소의수 : 0 3 실제유효주민등록번호의수 : 약 0 8 (= 억 ) 이하 모든가능한주민등록번호에빈레코드주소를할당한다면? 막대한저장공간낭비 0 3 >> 0 8 억개미만의레코드공간을갖는화일을만드는것이효율적 u 해싱 (hashing) 해싱함수 (hashing function) 를이용하여키값을주소로변환하여, 이변환된주소에레코드를저장하는것 해시주소 (hashed address) 해싱함수가키값으로부터변환한주소 해시화일 (hash file) 해싱기법으로운영되는화일 9 해싱함수 u 해싱함수 (hashing function) 키공간을유효주소공간으로사상 (mapping) h( 키값 ) 주소, 주소 유효주소공간 해싱함수는키값들을한정된주소공간으로균등하게분산시키는것이가장중요 0
해시화일설계시고려사항 u 해시화일 (hash file) 해싱기법으로운영되는화일 u 설계시고려사항 버킷 (bucket) 크기 하나의주소를가진저장구역에저장할수있는레코드의수 2 적재율 총저장용량에대한실제로저장되는레코드수의대한비율 3 해싱함수 레코드키값으로부터주소를생성하는방법 4 오버플로해결방법 주어진주소공간이만원이된경우의해결방법 버킷 u 버킷 (bucket) 하나의주소를가진한저장구역 이버킷에지정된주소를버킷주소 (bucket address) 레코드저장이나검색시지시하는저장공간 ( 주소 ) 하나이상의레코드저장가능 같은버킷안의모든레코드는같은버킷주소를가짐 화일을구성하는버킷수가이화일을위한해싱함수의주소공간 (address space) 이됨 u 버킷크기 버킷에저장할수있는레코드수 통상적으로한번의접근으로버킷내에있는모든레코드들을전송할수있는크기로결정 저장장치의물리적특성과연관 2
버킷 u 충돌 (collision) 두개의상이한레코드가똑같은버킷으로해싱되는경우 같은주소로해싱되어충돌된키값들을동거자 (synonyms) 라함 버킷이만원인경우에는충돌이문제가됨. 즉오버플로 (overflow) 가발생 오버플로를해결하기위한추가적인작업은해싱기법의오버헤드가됨. u 버킷크기를크게하면 장점 오버플로발생확률이감소 단점 저장공간의효율성이감소 버킷내레코드탐색시간이증가 3 적재밀도 (loading density) () u 적재밀도 (loading density) (= 패킹밀도 (packing density) ) 적재밀도 = = 화일저장공간의총용량 K c * N 저장된레코드수 < N : 버킷의수 c : 버킷의크기 K : 화일에저장된레코드수 4
적재밀도 (loading density) (2) u 적재밀도가높으면 삽입 / 검색시접근시간이길어짐. 왜냐하면이미여러레코드가지정된주소에저장되어있을확률이높아다른주소를검색해야되는경우가발생 u 적재밀도가낮으면 공간효율이떨어짐 u 실험적으로, 적재밀도가 70% 이상이되면충돌가능성이높음. 30% 정도의자유공간을예비하는것이바람직함 u 예 ) 학생레코드검색시스템 학생수최대 60,000명, 자유공간 30%, 버킷크기 2 버킷수 = 60,000/2*0.7 = 7,43 5 해싱함수 (hasing function) u 해싱함수 (h, 주소변환함수 ) h : 키 버킷주소 해싱함수계산시간 << 디스크의버킷접근시간 모든주소에대해균일한분포를갖는것이좋음 u 주소변환과정 키가숫자가아닌경우, 키를정수값 (A) 으로변환키 A 2 변환된정수 A 를주소공간의자리수크기의정수 B 로변환 A B 3 얻어진정수 B를주소공간의실제범위에맞게조정 B 조정인수 주소 6
() 제산잔여 잔여 (divide and remainder) 해싱 (divide and remainder) 해싱 u h(key) ) = key mod d = 키값 mod 제수 0 d- u 제수 (d) 직접주소공간의크기를결정 (0 d-) d > 화일의크기 제수는충돌가능성이가장적은것으로선택 소수 (prime number) 20 보다작은소수를인수로갖지않는비소수이면좋은성능기대 7 제산잔여해싱의성능 () u 적당한성능을위한적재율최대허용치는 0.7 0.8 n 개의레코드.25n 주소공간 (80% 의경우 ) u ( 예 ) 레코드 4000 개, 적재율 80% 주소공간 = 4,000 / 0.8 = 5,000 개의주소공간이필요 제수 : 5003 20 이하의소수인자를갖지않는수중 5000 에가장가까운수를선택한경우 8
제산잔여해싱의성능 (2) u 제수 5003 인제산잔여해싱예 9 (2) 중간제곱 (Mid-square) 해싱 키값을제곱 2 중간에서 n개 ( 주소공간 ) 의수를취함 u 예 ) 레코드가 4000 개인경우 최소 4 자리의주소공간이필요 키를제곱한수에서 4자리수를취함 주소공간이아주큰경우, 적절한조정인수를곱해주소공간을조절 20
중간제곱해싱 u 중간제곱잔여해싱예 뒤에서부터 7~0 자리수를주소로취함 2 (3) 중첩 (Folding) 해싱 키값을주소의크기와같은자릿수를갖는몇개의부분으로나눔 2 접어서합을구함 u 예 : 주소크기 (4 자리 ), 키값 (23456789) 2345 6789 2 9 3 0 3 8 2 0 4 7 2 0 5 6 주소 22
중첩해싱 23 (4) 숫자추출 (digit extraction) 방법 u 키값이되는숫자의출현분포를이용 균등하게분산사용된숫자위치들을주소자리수만큼선정 u 키들의모든자릿수에대한빈도테이블을만들어분석 u 예 9- 자리레코드키값을분석하여 4 개의균등한숫자위치로 9 번째, 7 번째, 5 번째, 2 번째위치가선정되었다고가정 주어진레코드키값 : 54603278 변환된레코드주소 : 834 24
(5) 숫자이동 (shifting) 변환 키를중앙을중심으로양분 2 주소길이만큼겹치도록안쪽으로각각이동 (shift) 하여합산 3 주소범위에맞도록조정 ( 조정인수사용 ) 키 : 주소길이 d d 2 d 3 d 4 d 5 d 6 d 7 d 8 예키 : 주소 : 2 3 4 5 6 7 8 5 2 6 3 7 4 8 6 9 2 u 주소공간 : 5000 변환된레코드주소 : 692 * 0.5( 조정인수 ) = 3456 25 (6) 진수변환 (radix conversion) 키값의진수 (base) 를다른진수로변환 2 초과하는높은자리수를절단 3 주소범위에맞도록조정 ( 조정상수사용 ) u 예 ) 키값 : 7248 주소공간 : 7000 조정인수 : 0.7 진수 : u 변환주소 5 + 7 4 + 2 3 + 2 + 4 + 8 0 = 266373 6373 조정 : 6373 * 0.7 = 446 26
v 충돌과오버플로 u u u 키값공간이주소공간보다크기때문에충돌발생이불가피 오버플로 (overflow) 하나의홈주소 (home address) 또는홈버킷 (home bucket) 으로충돌된동거자들을한버킷에모두저장할수없는경우 홈주소 : 해싱함수가생성한버킷주소 해결방법. 선형조사 (linear probing) 2. 독립오버플로구역 (separate overflow area) 3. 이중해싱 (double hashing) 4. 동거자체인 (synonym chaining) 5. 버킷체인 (bucket chaining) 이하, 버킷크기 = 로가정 27 () 선형조사 (linear probing) u 오버플로발생시, 홈주소에서부터차례로조사해서가장가까운빈공간을찾는방법 u 해당주소가공백인지아닌지를판별할수있게플래그 (flag) 를이용 insertlinear(key) addr h(key); home-addr addr; while (addr is full) do { addr (addr + ) mod N; if (addr = home-addr ) { print ("file is completely full"); return; } } insert the key at addr; set the addr is full; end insertlinear() 28
선형조사이용시의저장 / 검색 / 삭제 u 저장 원형탐색 : 빈저장공간조사는홈주소에서시작하여화일끝에서끝나는것이아니라다시화일시작으로돌아가홈주소에도착할때종료 ( 화일이만원 ) u 검색 레코드저장시에선형조사방법을사용했다면검색시에도선형조사방법을사용해야함 탐색키값을가진레코드가없거나홈주소에서멀리떨어져있는경우, 많은조사필요 u 삭제 삭제로생긴빈공간으로검색시선형조사가단절될수있음 삭제표시 (tombstone) 가필요 삭제된자리에삭제표시를해서선형조사가단절되지않게함 29 선형조사의단점 () () 어떤레코드가화일에없다는것을판단하기위해조사해야할주소의수가적재율이높아질수록많아짐 적당한적재율유지필요 (2) 환치 (displacement) 한레코드가자기홈주소를동거자가아닌다른오버플로된레코드가차지함으로인해다른레코드의홈주소에저장되는것 환치는또다른환치를유발 탐색할주소수의증가는삽입 / 검색시간증가를야기 대응책으로는처음화일을생성할때 2-패스해시화일생성 (two-pass hash file creation) 방법을이용 30
선형조사의단점 (2) u 2-패스해시화일생성 (two-pass hash file creation). 첫번째패스 모든레코드를해시함수를통해홈주소에저장 오버플로된동거자들은바로저장하지않고별도로임시화일에저장 2. 두번째패스 첫번째패스가모두끝나면임시화일에저장해둔오버플로동거자들을선형조사를이용해전부적재 - 패스화일생성에비해훨씬많은레코드들이원래의자기홈주소에저장됨 화일을생성하기전에레코드키값들을미리알면효율적 화일이생성된뒤에레코드들이추가될때는환치발생가능성이있음 3 (2) 독립오버플로구역 (separate overflow area) u 별개의오버플로구역을할당하여홈주소에서오버플로된모든동거자들을순차로저장하는방법 u 장점 동거자가없는레코드에대해서는한번의홈주소접근만으로레코드를검색 -패스로상대화일을생성 환치문제가없음 u 단점 오버플로된동거자를접근하기위해서는오버플로구역에있는모든레코드들을순차적으로검색 2 i- i i+ n 레코드 오버플로플래그 0 0 0 0 독립오버플로구역 2 m 다음가용공간 32
(3) 이중해싱 (double hashing) u 오버플로된동거자들을오버플로구역으로직접해시 오버플로구역에서의순차탐색을피할수있음 2차해싱함수 (second hashing function) 를이용 오버플로된동거자를해시하는함수 u 해싱과정. 차해싱함수에의해상대화일로해시 2. 오버플로가발생하면오버플로구역으로해시 오버플로구역주소 = (차해시주소 + 2차해시주소 ) mod ( 오버플로구역크기 ) 3. 오버플로가재차일어나면선형탐색을이용 33 (4) 동거자체인 (synonym chaining) u 각주소마다링크를두어오버플로된동거자레코드들을연결하는방법 오버플로가일어나면선형조사나오버플로구역을이용해서저장한뒤에링크로연결 동거자에대한접근은링크로연결된동거자들만조사 u 독립오버플로구역에사용할수도있고원래의상대화일에사용할수도있음 u 장점 : 홈주소에서의충돌감소 독립오버플로구역사용시환치문제가없음 u 단점 : 각주소가링크필드를포함할수있도록확장해야함 34
동거자체인예 u 동거자체인과독립오버플로구역예 동거자오버플로구역 레코드 링크 레코드 링크 - - 2-2 i- i i+ - 3 4 - - n - m - 35 5) 버킷체인 (bucket chaining) u 동거자체인과비슷 u 홈버킷에서동거자오버플로가일어나면별개의버킷을할당받아오버플로된동거자를저장하고홈버킷에이버킷을링크로연결 u 장점 : 재해싱이불필요 독립오버플로구역사용시환치문제가없음 u 단점 : 각주소가링크필드를포함할수있도록확장해야함 최악의경우한레코드를탐색하기위해서는그홈버킷에연결된모든오버플로버킷을조사해야됨 36
버킷체인의성능 u 레코드탐색 어떤다른방법보다도평균조사수가적음 동거자오버플로구역 레코드 레코드 링크 레코드 링크 - - 2 2 i- 3 - - - I - i+ n - m- m - - 버킷체인 37 v 테이블이용해싱 해싱 (table-assisted assisted hashing) u 저장장치에한번의접근으로레코드검색을보장 레코드삽입시간은많이걸리지만검색은매우빠름 해싱함수는각레코드에대해일련의 < 버킷주소 i, k-비트시그너쳐 i > 쌍을생성 (i=, 2, 3, ) <addr, sign>, <addr2, sign2>, <addr3, sign3>, 각버킷에는하나의엔트리 (k- 비트시그너쳐 ) 로된버킷테이블을유지 화일접근시에이버킷테이블은전부메인메모리에상주 38
테이블이용해싱 u 해싱함수가생성한버킷주소와 5-비트시그너쳐예 키 White Blue Lilac Red Green 버킷주소 85 87 89 9 93 85 86 87 88 89 85 90 95 0 5 85 92 99 6 3 85 86 87 88 89 5-비트시그너쳐 000 000 000 0 000 000 000 0000 0000 000 000 000 0000 000 0 000 000 0000 000 00 39 테이블이용해싱을통한삽입 () u 레코드삽입예 버킷크기 : 3 레코드삽입순서 : White, Blue, Lilac, Red, Green, 각레코드의홈버킷 : 85 u 3 번째 Lilac 을삽입하면버킷 85 는만원이됨 버킷크기가 3이기때문 u 4 번째 Red 를삽입할때오버플로가발생. 그러면이버킷 85 에대한 4 레코드시그너쳐값들을정렬 Red ( 시그너쳐 0000 = 2) White ( 시그너쳐 000 = 5) Blue ( 시그너쳐 000 = 6) Lilac ( 시그너쳐 0000 = 8) 분리시그너쳐값 u 시그니쳐값 8을분리시그너쳐값으로선정하고버킷 85 에대한버킷테이블엔트리로저장 버킷에는항상분리시그너쳐값보다작은레코드만저장 40
테이블이용해싱을통한삽입 (2) u 이분리시그너쳐값보다작은 Red, White, Blue 는버킷 85 에다시저장 u 그러나 Lilac 은그의두번째버킷주소 90 에저장 u 버킷테이블엔트리즉, 시그너쳐값은초기치 에서버킷이오버플로되는경우에만갱신 예 : White, Blue, Lilac, Red, Green을삽입한경우 Red, White, Blue는버킷 85에저장 : 테이블엔트리는 0000 Lilac 은버킷 90에저장 : 테이블엔트리는그대로 u Green 을삽입하면 Green의홈버킷은 85, 시그너쳐는 3(000) 버킷 85는만원이기때문에시그너쳐정렬을통해 Green은버킷 85에삽입 오버플로된 Blue는재삽입리스트에첨가시켜대기 버킷 85에대한테이블엔트리는 8(0000) 에서 6(000) 으로갱신 4 테이블이용해싱을통한검색 u 검색이아주빠르기때문에 log-in 용 ID 를확인하는화일조직에효율적임 검색시해싱함수는검색할레코드키로부터일련의 < 버킷주소 i, 시그너쳐 i >, i=, 2, 3, 을생성 u 다음조건을만족하는가장작은 i를선정시그너쳐 i < 버킷 i의테이블엔트리, i=, 2, 3, 버킷 i에서레코드를검색 u 예 : White 검색시, 해싱함수가생성한 < 버킷주소, 시그너쳐 > 를테이블엔트리와검사해서검색할버킷주소를결정 해싱함수 : <85, 000>, <87, 000>, <89, 000>, 시그너쳐 (85, 000) < 버킷 85의테이블엔트리 (0000) 따라서, 검색할버킷주소는 85 42
v 확장성직접화일 화일 () u 화일레코드수의변화가큰경우에대한해결방안 u K : 어느한시점에서화일에저장된레코드수 Kmin K Kmax SPAN = Kmax / Kmin SPAN이클때문제가됨 화일크기가고정되어있을때 K Kmin : 공간이용률은낮음 K Kmax : 적재밀도가높음 저장과검색시간이길어짐 해결방안은재해싱 (rehashing) 많은시간소요 재해싱동안접근제한 43 확장성직접화일 (2) u 확장성화일 (extendible file) 높은 SPAN 값을가진화일에대한해싱기법 버킷크기는일정 버킷수는가변 오버플로버킷은사용하지않음 삭제는간단 검색은 -2회의접근만필요 u 확장성화일의유형 가상해싱 (virtual hashing) 동적해싱 (dynamic hashing) 확장성해싱 (extendible hashing) 선형해싱 (linear hashing) 44
() 가상해싱 (Virtual Hashing) u 여러개의해싱함수를사용 u 해싱함수는제산잔여기법을기초 h 0 : 주소 = 키 mod N N : 버킷의수, C : 버킷크기 u 오버플로우가되면 버킷의 C 레코드와삽입하려는레코드를합한 C+개의레코드를새로운해싱함수를사용해서재해싱 재해싱함수 h i h i : 주소 = 키 mod (2 i * N), i = 0,, 2,... h : 주소 = 키 mod 2N h 2 : 주소 = 키 mod 4N 45 가상해싱예 () u ( 예 ) 버킷수 N=00, 버킷크기 C=4 레코드 3, 03, 203, 303을첫번째해싱함수 h 0 : 주소 = 키 mod 00 을이용해삽입 버킷 3 = [3, 03, 203, 303] 으로만원 다음레코드 403 을삽입할때오버플로가발생. 따라서두번째해싱함수 h ( 키 mod 2x00) 을이용해버킷 3 과 03 으로분할 46
가상해싱예 (2) 다음레코드 603, 803 을삽입할때, 버킷 3 은오버플로가됨. 세번째해싱함수 h 2 ( 키 mod 4x00) 을이용해버킷 3 과 203 으로분할 u 추가로필요한기법 각버킷에적용된해싱함수를유지하는기법 검색할키값에적용할해싱함수 h k 를알수있는기법 레코드 603을검색할때해싱함수 h 2 즉주소 = 키 mod 4x00을찾아서적용하여주소 203을구해야한다. 47 (2) 동적해싱 (Dynamic Hashing) u 화일구성 크기가 C인 N개의버킷 (bucket) 과 각버킷을지시하는인덱스 (index) 로구성 버킷은저장장치에할당되고인덱스는메인메모리에상주 u 예 : N=20 이고 C=3 일때초기동적해시화일 초기에인덱스는하나의레벨 ( 레벨 0) 48
동적해시화일에서의레코드삽입 삽입 () u 해싱함수 (H 0 ) 로레코드를저장할버킷을결정 해싱함수 H 0 는키값을레벨 0의인덱스 ( N) 로변환 레코드를저장할버킷은이인덱스엔트리로접근 버킷이만원이아니면레코드를저장하고만원이면버킷을분할하고 C+ 레코드를나누어분산저장 이때이인덱스노드는다음하위레벨의두인덱스를위해왼쪽 (old), 오른쪽 (new) 서브트리를갖는이진트리가됨 레코드삽입으로버킷이계속분할되면인덱스는 N개의이진트리로된포리스트가됨 u 버킷분할과레코드분산방법 분산저장해야될레코드의버킷이왼쪽인지오른쪽인지는비트함수 B로결정 비트함수 B : 키값을임의의길이의비트스트링 (bit string) 으로변환 49 동적해시화일에서의삽입 삽입 (2) 인덱스가분기되는레벨이 i 이면비트스트링의 i+ 째비트를이용하여이비트가 0 이면왼쪽 이면오른쪽으로분기 해싱함수 H 0 와비트함수 B 에대한예 키 57 95 88 205 3 25 6 30 H 0 ( 키 ) 2 2 B( 키 ) 000 000 000 000 0 000 0000 000 50
동적해시화일에서의삽입예 () ( 예 ) 레코드 57, 95, 88, 205, 3 을삽입한뒤의초기화일 5 동적해시화일에서의삽입예 (2) ( 예 ) 레코드 25 를삽입할때오버플로가됨. 비트함수 B가생성한비트스트링의첫번째비트를이용하여버킷 을분할한뒤의화일 52
동적해시화일에서의삽입예 (3) ( 예 ) 레코드 30, 6 을삽입할때오버플로가발생. 함수 B가생성한비트스링의 2 번째비트를이용하여버킷 을분할한뒤의화일 53 동적해시화일에서의검색 u 레코드검색버킷의결정절차 해싱함수 H 0 로인덱스레벨 0 의포리스트를식별 주어진레코드키값에대한함수 B의비트스트링값으로인덱스레벨 부터분기하여검색할버킷을결정 54
비트함수 (bit function) u 비트함수 B의설계예 레코드의키 ( 또는키에대한어떤함수 H ) 를모조난수생성기 (pseudo-random number generator) 의초기값으로사용하여정수를생성 2 생성된각정수를하나의비트로변환 0과 이똑같은확률로생성될수있도록변환 55 (3) 확장성해싱 (Extendible hashing) u 확장성해싱함수 (extendible hashing function) h는키값을일정길이의비트스트링즉모조키 (pseudokey) 로변환 예 : h(k) 00000000 u 확장성해시화일은디렉터리와버킷으로구성. 디렉터리 (directory) 일반적인인덱스에해당 버킷에대한 2 d 개의포인터로구성. 정수 d는전역깊이 (global depth) 로디렉터리의크기를나타냄. 포인터들은같은버킷을가리킬수도있음. 2. 버킷 (bucket) 레코드들을실제로저장하는공간 각버킷은지역깊이 (local depth), p를표시 이버킷깊이 p는그버킷에저장된모든레코드들의모조키들이첫번째비트부터공통으로가지고있는비트스트링길이를말함. 56
확장성해시화일 화일 () u 초기확장성해시화일의구축 N개의버킷으로시작한다고할때, 전역깊이 d = ëlog (N-)û + d는디렉터리엔트리수를나타내는지수 디렉터리는 2 d 개의엔트리를포함 2 d 개의버킷을가리킬수있는포인터 57 확장성해시화일 (2) 58
확장성해시화일에서의검색 u 레코드검색 레코드에대해해싱함수 h가생성한모조키의처음 d 비트를디렉터리에대한인덱스로사용 접근한디렉터리엔트리로레코드가저장되어있는목표버킷을접근하여검색 u 키값 k를가진레코드검색예 ) h(k) 00000000 2) d=3이기때문에모조키의처음 3 비트를이용하여디렉터리의 6번째엔트리 (0) 를접근 3) 이엔트리는키값 k를가지고있는레코드가저장되어있는 4번째버킷에대한포인터 이버킷의 p 값 은저장된레코드들의공통모조키비트수가 이라는것즉, 모든레코드들의모조키가 로시작한다는것을나타냄 59 확장성해시화일에서의저장 u 레코드저장 저장할레코드에대해해싱함수가생성한모조키의처음 d 비트를이용해디렉터리를접근하여포인터가지시하는버킷에레코드를저장 u 만일그버킷이만원이고버킷깊이가 p인경우. 새로운버킷을할당 2. 버킷크기가 c라할때 c+ 레코드들을각각자기모조키의 (p+) 번째비트에따라두버킷에분산저장 3. 기존버킷과새로할당한버킷의깊이 p를모두 (p+) 로설정하고 만일디렉터리깊이가 d (p+) 이면디렉터리의해당포인터엔트리만조정 만일디렉터리깊이가 d< (p+) 이면디렉터리깊이 d 값을 증가시키고디렉터리크기를 2 배로확장한다음포인터엔트리를조정 60
d (p+) 인경우의예 u 모조키가 로시작하는버킷 4가만원인상태에서모조키가 0 으로시작하는레코드를삽입하는경우 빈버킷을할당하고버킷 4를분할하여모조키 로시작하는레코드들을이새버킷으로이동 디렉터리인덱스 0과 의포인터값은새버킷을지시하도록변경 분할된두버킷의깊이 p를 2로설정 :d :p 6 d < (p+) 인경우의예 () u 모조키가 000 으로시작하는버킷 이만원인상태에서모조키가 000 로시작하는레코드를삽입 디렉터리깊이 3을 증가시켜디렉터리를 2배로확장 빈버킷을할당하고모조키가 000로시작하는레코드들을이새버킷으로이동 디렉터리인덱스 000의포인터값은새버킷을지시하도록변경 분할된두버킷의깊이 p를 4로설정 디렉터리의다른모든포인터엔트리를조정 62
d < (p+) 인경우의예 (2) 63 확장성해시화일에서의삭제 u 삭제할레코드를검색과정으로찾아삭제 u 버킷에하나만있는레코드를삭제하는경우 버디버킷을검사하여, 두버디에있는레코드들이한버킷에들어갈수있으면합병 버디버킷 (buddy bucket) : 두버킷이똑같은버킷깊이 (p) 를가지고있고그버킷에있는레코드모조키들의처음 (p-) 비트들이모두동일한버킷 이때버킷의새로운깊이값은 p- 모든버킷들의깊이값이디렉터리깊이값보다작게되면디렉터리의깊이를하나감소 (d d-) 디렉터리크기는반으로줄어듦 포인터엔트리들을적절히재조정 64
(4) 선형해싱 (linear hashing) u 디렉터리를사용하지않는확장성해싱방식 u 주소공간이확장될때해시값의비트 (bits) 를사용 예 : 버킷주소공간이 4이면 2-비트주소를생성하는 2-비트해싱함수를이용 u 오버플로를위해주소공간을확장해야될때는항상선형으로확장 주소확장방법은한번에 2배로하지않고첫번째버킷부터차례 ( 선형 ) 로분할해가면서마지막버킷분할이끝나면그다음 2배확장을위해다시처음버킷에서부터시작하는사이클식임. 65 선형해싱예 () u 초기에 2-비트해싱함수 h 2 로 2-비트주소를생성 u 레코드삽입으로버킷 b에첫번째오버플로발생 새버킷 A를할당해서첫번째버킷 a를분할. 레코드분할을위해 3-비트해싱함수 h 3 를사용 버킷 b의실제오버플로레코드들은버킷 w를할당해서분할하고버킷 b와링크로연결 버킷 a와새버킷 A의주소는 3-비트해싱함수로접근 66
선형해싱예 (2) u 버킷 d에두번째오버플로발생 새버킷 B를할당해서두번째버킷 b와 w를분산저장. 레코드분할을위해 3-비트해싱함수 h 3 를사용 버킷 d는버킷 x를할당해서분할하고링크로연결 u 버킷 x에세번째오버플로발생 새버킷 C를할당해서세번째버킷 c를분할 버킷 x는버킷 y를할당해서분할하고링크로연결 67 선형해싱예 (3) u 버킷 B에네번째오버플로발생 새버킷 D를할당해서네번째버킷 d와 x, y를분산저장 버킷 B는버킷 z를할당해서분할하고연결 이제모든버킷이 3- 비트해싱함수를사용하게되었음. 따라서다음사이클에분할될버킷을가리키는포인터는다시첫번째버킷 a 를가리키도록설정 그리고새로운버킷을생성하여화일을확장할때는 4- 비트해싱함수 h 4 를사용함. 68
선형해싱에서의검색 u 두개의해싱함수를이용해접근 d-비트의기본주소를가진버킷에대해서는 d-비트해싱함수 h d (k) 를이용해서접근 확장버킷에대해서는 (d+)-비트해싱함수 h d+ (k) 를이용해서접근 따라서레코드의검색을위해서는어떤해싱함수를사용해야되는지알아야함 u 키값 k를가진레코드를포함하고있는버킷주소 (address) 를찾기위한프로시저 if (h d (k) p) address = h d (k); else address = h d+ (k); p : 다음에분할할버킷을가리키는포인터 69