Discrete Mathematics

Size: px

Start display at page:

Download "Discrete Mathematics"

강하 엽
4 years ago
Views:

1 자료처리 () 2005 년봄학기 문양세컴퓨터과학과강원대학교자연과학대학

2 임의접근파일 (Random Access File) 임의접근파일 (random access file) 임의의레코드에그레코드의키값을사용하여그키값을가지는레코드에랜덤하게 ( 직접적으로 ) 접근할수있는파일 (= 직접파일 (direct file), 직접접근파일 (direct access file)) 다른레코드를참조하지않고도, 개개의레코드에접근가능 ( 순차접근파일 ) 인덱스활용 인덱스된파일 (indexed file): 별도로관리되는인덱스를이용하여레코드에직접접근 인덱스된순차파일 (indexed sequential file): 인덱스를이용한임의접근 / 순차접근을모두지원 (B + - 트리 ) 해싱 (hashing) 활용 상대파일 (relative file): 레코드의키와레코드의위치사이의설정관계를활용 ( 예 : 키값 = 10 위치 ( 주소 ) = 10 x 100 bytes = 1000) 해시파일 (hash file) - 키값을사용하여레코드의저장주소생성 - 협의의의미에서의직접파일 Page 2

3 상대파일 (Relative File) (1/4) 레코드의키와레코드의위치 ( 상대적인레코드번호 ) 사이에설정된관계를통해레코드에접근 상대레코드번호 (relative record number) 파일이시작되는첫번째레코드를 0번으로지정, 이것을기준으로다음레코드들에 1, 2, 3,, N-1의순서를지정 (= 상대주소 (relative address)) 레코드의논리적순서와물리적순서는무관, 즉, 레코드들이키값에따라물리적으로정렬되어있을필요는없음 Page 3

4 상대파일 (Relative File) (2/4) 사상함수 (mapping function) A: 키값 주소 // A(key) = address 레코드기록시 : 키값 레코드가저장될주소 레코드검색시 : 키값 레코드가저장되어있는주소 모든레코드에직접접근가능 주기억장치의데이터구조에서활용이가능함 ( 실제, 교환기의 DBMS 에서는이러한간략하면서 Powerful 한액세스방법을사용함 ) 사상함수의구현방법 (will be explained in the next slides) 직접사상 (direct mapping) 디렉토리검사 (directory lookup) 계산 (computation) 을이용한방법 해싱 Page 4

5 상대파일 (Relative File) (3/4) 직접사상 (Direct Mapping) 절대주소 (absolute address) 이용 키값은그자체가레코드의실제주소임 레코드가파일에처음저장될때레코드의주소에해당하는 < 실린더번호, 디스크번호, 블록번호 >, 즉절대주소가결정됨 장점 : 간단하며처리시간이거의걸리지않음 단점 : 물리적저장장치에의존적 ( 특수한경우를제외하고는, 잘사용되지않음 ) Page 5

6 상대파일 (Relative File) (4/4) 디렉토리검사 (Directory Lookup) < 키값, ( 상대 ) 주소 > 의쌍을엔트리로하는테이블 ( 디렉토리 ) 을유지 검색절차 : 디렉토리에서키값검색 키값에대응되는레코드번호 ( 상대주소 ) 구함 레코드접근 장점 : 빠른검색 단점 : 삽입비용이크며, 종종파일과디렉토리재구성필요 구현예 < 키값, 레코드번호 > 쌍을엔트리로갖는배열 디렉토리엔트리는키값으로정렬 순차접근은가능하나의미는없음 Page 6

7 해싱개요 (1/2) 계산 (computation) 을이용한상대파일구성법 일반적으로, 주소공간 (address space) >> 키값공간 (key value space) 주민등록번호 (13 자리 ) 의예 가능한주소의수 : ( 개 ) 실제필요한주소의수 : 약 10 8 (=1 억 )( 개 ) 이하 주민등록번호각각마다빈레코드주소를할당한다면? 막대한공간낭비 ( >> 10 8 ) 1 억개의레코드공간을갖는파일을만드는것이효율적 해싱 (hashing) 해싱함수 (hashing function) 를이용하여키값을해시주소 (hashed address) 로변환하고, 변환된주소에레코드를저장 장점 : 레코드의주소를구해직접접근 빠른접근시간 순차파일에서의레코드탐색시간 = O(N), N = 레코드개수 해싱에서의레코드탐색시간 = O(1) Page 7

8 해싱개요 (2/2) 해싱함수 (Hashing Function) 키공간을주소공간으로사상 (mapping) h( 키값 ) = 주소, 주소 유효주소공간 (effective address space) 키값들을한정된주소공간으로균등하게분산시키는것이핵심 Page 8

9 해싱사용시고려사항 버킷크기 (bucket size): 하나의주소를가진저장구역 (= 버킷 ) 에저장할수있는레코드수적재밀도 (loading density): 총저장용량에대한실제로저장되는레코드수의비율해싱함수 (hashing function): 레코드키값으로부터레코드가저장된위치 ( 주소 ) 를생성하는방법오버플로우 (overflow) 해결방법 : 주어진주소공간이만원 (full) 이된경우의해결방법 Page 9

10 버킷크기 (1/2) 버킷 (bucket): 하나의주소를가진하나의저장구역 하나이상지정된개수의레코드저장함 동일버킷내의레코드들은모두동일한버킷주소를가짐 한파일을구성하는구성하는버킷수가그파일의주소공간이됨 버킷크기 (bucket size) 통상적으로한번의접근 (I/O Access) 으로버킷내에있는모든레코드들을전송할수있는크기로결정 저장장치의물리적특성과연관 일반적으로한개의블록 ( 혹은페이지 ) 크기로설정됨 Page 10

11 버킷크기 (2/2) 충돌 (collision) 두개의상이한레코드가동일한버킷으로해싱되는경우 동거자 (synonyms): 같은주소로해싱되어충돌된키값들을일컬음 버킷이만원일때는충돌이문제가됨 오버플로우 (overflow) 발생 버킷크기를크게하면 오버플로우가감소하는장점이있으나, 저장공간의효율이감소되고, 버킷내레코드탐색시간이증가하는단점이있음 Page 11

12 적재밀도 (1/2) 적재밀도 (loading density) (= 패킹밀도 (packing density)) 적재밀도 = 저장된레코드수 파일저장공간의총용량 = K c x N < 1 N : 버킷의수 c : 버킷의용량 ( 하나의버킷에저장될수있는레코드개수 ) (c x N = 파일에저장가능한총레코드수 ) K : 파일에저장된레코드수 Page 12

13 적재밀도 (2/2) 적재밀도가높으면, 삽입시접근수가증가함 ( 이미레코드가저장된주소에해싱될경우가많기때문 ) 검색시접근수가증가함 ( 원치않는레코드가저장된주소에해싱될경우가많기때문 ) 적재밀도가낮으면, 공간효율이떨어짐실험결과에따르면, 적재밀도 > 70% 이면충돌이너무잦음 30% 정도의예비공간이필요함예 ) 학생레코드검색시스템 학생수가최대 60,000명, 예비공간 30%, 버킷크기 12 적정버킷수 = 60,000 / 0.7 / 12 = 7143 Page 13

14 해싱함수 (Hashing Function) 해싱함수 ( 변환함수 ): 키 버킷주소 해싱함수계산시간 << 보조기억장치 ( 예 : 디스크 ) 의버킷접근시간 모든주소에대한균일한분포를가지는것이가장중요한요소임 주소변환과정 단계 1: 키가숫자가아닌경우 ( 예를들어, 스트링인경우 ), 키를정수값 (A) 으로변환키 A 단계 2: 변환된정수 A를해싱함수를사용하여주소공간의정수 B로변환 A B (B : 균일분포로변환 ) 단계 3: 얻어진정수 B를주소공간의실제범위에맞게조정 B 조정상수 주소 ( 실제목표주소로변환 ) 예 ) kim 단계 1: k 11, i 9, m 13, kim 단계 2: h(11973) = % 1000 = 973 (0 h(key) 999) 단계 3: 973 x 0.5 = 486 (0 address 499) Page 14

15 나머지함수 (Modular Function) (1/2) 나머지함수 = 제산잔여 (divide and remainder) 주소 = key value mod divisor (h(k) = k % d) 0 h(k) divisor 1 Divisor ( 제수 ) Divisor 자체가직접주소공간의크기를결정 (0 ~ divisor - 1) 충돌가능성이가장작은것으로선택 소수 (prime number) 20 보다작은소수를인수로갖지않는비소수 ( 예 : 에가까우면서 20 이하의소수를인수로갖지않는비소수 ) 적당한성능을위한적재밀도는 0.7 ~ 0.8 n 개의레코드 1.25n 주소공간 (1/1.25 = 80% 인경우 ) 적재밀도와주소공간을고려하여 divisor 를결정함 Page 15

16 나머지함수 (Modular Function) (2/2) Divisor 를결정과이에따른해싱의예 레코드개수가 4,000개, 적재밀도 = 80% 주소공간 = 4,000 / 0.8 = 5,000개주소공간이필요 Divisor = 5,003 (20 이하의수를인자로갖지않는수중에서 5,000에가장가까운수를선택한경우 ) Divisor 가 5003 인경우의예 Page 16

17 중간제곱 (Mid-Square) 해싱 키값을제곱하고, 중간에서 n개 ( 주소공간 ) 의수를취함예 ) 레코드가 4,000개인경우 최소네자리의주소공간이필요 키를제곱한수에서네자리수를취함 주소공간이작거나큰경우, 적절한상수를곱해서주소값을조절함 중간제곱해싱예 ( 뒤에서부터 7~10 자리수취함 ) Page 17

18 중첩 (Folding) 해싱 키값을주소공간과같은자리수를가지는몇개의부분으로나누고, 이들을접어서 (folding 해서 ) 그합을구함 예 ) 주소크기 (4 자리 ), 키값 ( ) 주소 키값 주소 ** 충돌 ** ** 충돌 ** Page 18

19 숫자추출 (Digit Extraction) 방법 숫자분석 (Digit Analysis) 방법이라고도함 키값을구성하는각 digit 의분포를이용 키들의모든자릿수에대한빈도테이블을만들고, 어느정도균등한분포를갖는자릿수를주소라사용 예 ) 주민등록번호의경우 (YyMmDd 에서, y, m, d 는 Y, M, D 에비해균등한성질을가짐 ) 키값을구성하는각 digit 의분포를미리알고있을경우에유용 예제 : 키값의 9 th, 7 th, 5 th, 3 rd 자리로주소를구성 h( ) = 9753 h( ) = 1357 h( ) = 2400 Page 19

20 숫자이동 (Shifting) 방법 키값을중앙을중심으로양분한뒤, 주소길이만큼겹치도록안쪽으로각각 Shift 하여해쉬값을구한후, 주소범위에맞도록조정 ( 조정상수사용 ) 키 : 주소길이 d1 d2 d3 d4 d5 d6 d7 d8 주소 : 주소공간이 5,000 인경우, 6,912 x 0.5 = 3,456 (= 실제주소 ) Page 20

21 진수변환 (Radix Conversion) 키값의진수를다른진수로변환 초과하는높은자리수는절단 주소범위에맞도록조정 ( 조정상수사용 ) 예제 : 10 진수를 11 진수로변환 키값 = 주소공간 = 7000 h(172148) = 1 x x x x x x 11 0 = 조정상수적용 : 6373 x 0.7 = 4461 Page 21

22 충돌과오버플로우 (1/2) ( 키값공간 > 주소공간 ) (e.g., 주민번호 = > 주소공간 = 10 8 ) 충돌 (collision) 불가피 오버플로우 (overflow) 동일한주소 (home address) 로충돌된동거자 (synonyms) 들을한버킷에모두저장할수없는경우 해싱에서는해싱함수의선택과함께, 오버플로우처리가주된이슈임 Page 22

23 충돌과오버플로우 (2/2) 오버플로우해결방법 개방주소법 (open addressing): 오버플로우된동거자를저장할공간을상대파일내의공간에서해결 체인법 (chaining): 오버플로된동거자를위한저장공간을상대파일밖의지정된공간에서해결, 즉독립된오버플로우구역을유지 선형조사 (linear probing) // 개방주소법 독립오버플로우구역 (separate overflow area) // 체인법 이중해싱 (double hashing) // 체인법 동거자체인 (synonym chaining) // 체인법 버킷주소법 (bucket addressing) // 체인법, 개방주소법 Page 23

24 선형조사 (Linear Probing) (1/5) 오버플로우발생시, home address 부터차례로조사하여가장가까운빈공간을찾는방법 해당주소가공백인지아닌지를판별할수있어야함 플래그 (flag) 활용 0 h(x) = i i-1 i h(y) = i i+1 i+2 n 레코드 record or not record or not (x) (y) record or not record or not 플래그 T/F T/F T T T/F T/F Page 24

25 선형조사 (Linear Probing) (2/5) 저장 ( 삽입 ) 원형 (circular) 탐색 : 빈주소를조사하는과정은 home address 에서시작하여파일끝에서끝나는것이아니라다시파일시작으로돌아가는방식 (C 의경우 % 연산을사용하여구현 ) 검색과정에서빈공간이발생하면해당공간에레코드를저장 검색 레코드저장시, 선형조사를사용했다면검색에서도선형조사를사용해야함 키값을가진레코드가없거나 home address 에서먼경우, 많은조사필요 삭제 삭제로인해만들어진빈공간으로검색시선형조사가단절될수있음 삭제표시 (tombstone) 이용 : 삭제된자리에삭제표시를해서선형조사가단절되지않도록해야함 Page 25

26 선형조사 (Linear Probing) (3/5) 장점 구현이 ( 매우 ) 용이함 충돌이적은경우 ( 해슁함수가 Good 혹은저장공간이많은경우 ) 에빠른성능을보임 단점 충돌이많을경우, 레코드의검색 ( 특히, 어떤레코드가파일에없다는것을판단 ) 하기위해많은시간이소요 특히, 적재밀도가높을수록시간이많이걸림 검색시간을줄이기위해서, 적당한적재밀도의유지가필요함 삽입 / 삭제를반복하면서환치 (displacement) 가발생할수있음 next page Page 26

27 선형조사 (Linear Probing) (4/5) 환치 (displacement) 자기주소를동거자가아닌레코드가차지함으로인해, 자기주소가아닌다른레코드의주소에저장되는것 다른환치를유발 (A 는 B 의주소에저장되고, B 는 C 의주소에저장되고, ) 탐색할주소수증가 삽입 / 검색시간의증가를야기함 대응책 : 2- 패스해시파일생성 (two-pass hash file creation) Page 27

28 선형조사 (Linear Probing) (5/5) 2- 패스해시파일 첫번째패스 - 모든레코드를해시함수를통해 home address에저장 - 충돌이일어나는동거자들은바로저장하지않고별도의임시파일에저장 두번째패스 - 임시파일에저장해둔동거자들을선형조사를이용하여파일에모두저장 첫번째패스생성에비해훨씬많은레코드들이원래자기홈주소에저장됨 파일생성이전에레코드키값들을미리알수있는경우에효율적임 파일이생성된후에레코드들이추가될때는환치 (displacement) 발생 Page 28

29 독립오버플로우구역 별개의오버플로우구역 (separate overflow area) 을할당하여, 오버플로우된모든동거자들을순차로저장하는방법 장점 동거자가없는레코드에대해서는한번의주소접근만으로레코드를검색 환치문제를제거 단점 오버플로우된동거자를접근하기위해서는오버플로우구역에있는모든레코드들을순차적으로검색 i+1 n i-1 i 레코드 overflow flag 독립오버플로구역 1 2 m 다음가용공간 Page 29

30 이중해싱 (double hashing) 오버플로우된동거자들을오버플로우구역으로직접해싱 오버플로우구역에서의순차검색을피할수있음 이차해시함수 (second hash function): 오버플로우된동거자들을해슁하는함수 해싱과정 일차해시함수에의해상대파일로해슁 오버플로우가발생하면오버플로우구역으로이차해슁 오버플로우구역에서다시충돌이일어나면선형조사를이용 장단점 오버플로우구역에서순차검색을피할수있어, 충돌시검색이빠름 두개의해쉬함수를유지해야하며, 충돌이빈번한경우오버플로우구역에서환치와같은선형조사의문제점이다시발생함 Page 30

31 동거자체인 (Synonym Chaining) (1/2) 각주소마다링크를두어오버플로우된레코드들을연결하는방법 오버플로우가일어나면선형조사나오버플로우구역을이용해서저장후, 처음해시주소에동거자를포함하고있는주소에대한링크를둠 동거자에대한액세스는링크로연결된동거자들만조사해보면됨 독립오버플로우구역에사용할수도있고, 원래의상대파일에적용할수도있음 장점 Home address 에서의충돌이감소됨 충돌시순차검색을피할수있어, 검색시간이단축됨 단점 각주소가링크필드를포함하도록확장해야함 Page 31

32 동거자체인 (Synonym Chaining) (2/2) 동거자체인 + 독립오버플로우구역예 동거자오버플로우구역 레코드 링크 레코드 링크 i-1 i i+1-1 n -1 m -1 Page 32

33 버킷주소법 (1/3) 버킷에복수개의레코드저장공간을관리하여, 해싱함수는키값을레코드주소가아닌버킷주소로사상함 하나의해시주소에가능한최대수의동거자를저장할수있는공간을할당함 특정해시주소를갖는모든동거자들은그주소의버킷에순차적으로저장함 ( 일반적으로 ) 한레코드를검색하기위하여조사해야될레코드수는최대로버킷사이즈에한정됨 ( 오버플로우구역탐색, 파일전체탐색불필요 ) 문제점 공간의낭비 : 각해시주소에대한동거자의수가다양하고그차이가아주클때 - 버킷크기는해시주소에대한최대동거자수로정하는것이보통 이경우공간낭비가심함 버킷크기설정 - 파일생성전에데이터를분석할수없을때, 설정이어려움 - 버킷크기가충분치않으면오버플로우발생 충돌해결기법필요 Page 33

34 버킷주소법 (2/3) 버킷주소법에서의충돌해결 여유공간을가진가장가까운버킷을사용하는방법 환치등의선형조사와동일한단점 버킷체인 (bucket chaining) 홈버킷에서오버플로우가발생하면, 별도의버킷을할당한후해당동거자를저장하고홈버킷에이버킷을링크로연결 장점 : 재해싱불필요 단점 : 한레코드를탐색하기위해서는최악의경우그홈버킷에연결된모든오버플로우버킷을조사해야함 Page 34

35 버킷주소법 (3/3) 성공적탐색 동거자오버플로우구역 어떤다른방법보다도평균조사수가더작음 1 2 레코드 레코드 링크 레코드 링크 -1 실패탐색 i 성공적탐색과비슷하거나더작은조사수를보임 ( 독립오버플로우구역과버킷주소법을사용하는경우 ) I i+1-1 m-1-1 n -1 m -1 Page 35

36 Advanced Hashing Techniques 테이블이용해슁 : Signature 를사용한신속한해싱방법 확장성직접파일 : 레코드개수가지속적으로증가하는경우를위한, 해슁파일의동적관리가주목적임 가상해싱 (Virtual Hashing) 동적해싱 (Dynamic Hashing) 확장해싱 (Extendible Hashing) 선형해싱 (Linear Hashing) Page 36

37 테이블이용해싱 (1/3) 한번의디스크접근으로검색을보장하는방법 해싱테이블 : 키 < 버킷주소의순열, k-비트시그너쳐 (signature) 의순열 > 생성 디렉토리테이블 : < 버킷주소, k-비트시그너쳐 > 로구성 해싱테이블과디렉터리테이블 : 주기억장치에유지 레코드삽입과삭제는시간이많이소요되나, 검색은매우빠름 예 )k = 5 일때, 버킷주소와시그너쳐의순열 ( 해싱테이블 ) 키버킷주소 5- 비트시그너쳐 White Blue Lilac Red Green Page 37

38 테이블이용해싱 (2/3) 삽입의예 버킷크기 = 3, 각레코드의홈버킷 = 85, 레코드삽입순서 = White, Blue, Lilac, Red, Green 네번째 Red 를삽입할때, 오버플로우가발생함 - Red( 시그너쳐 = 2), White( 시그너쳐 = 5), Blue( 시그너쳐 = 6), Lilac ( 시그너쳐 = 8) - 시크너쳐값의크기 ( 순서 ) 에의해, Red, White, Blue 는 85 번버킷에저장 - Lilac 은 90 번버킷에저장 ( 앞서의해싱테이블을보면버킷 85 다음에버킷 90 임 ) 레코드를버킷에저장할때마다디렉토리테이블을유지함 디렉토리테이블 - 엔트리 = ( 버킷번호 ( 주소 ), 시그너쳐값 ) - 시그너쳐값은초기치 (11111) 에서버킷오버플로우가발생한경우에만 ( 오버플로우가처음발생한키의시그너쳐값으로 ) 변경 - Red, White, Blue 는버킷 85 에저장 = (85, 01000) 오버플로우가발생한 Lilac 의시그너쳐값 - Lilac 은버킷 90 에저장 = (90, 11111) 버킷주소 시그너쳐 Page 38

39 테이블이용해싱 (3/3) 검색 : 아주효율적임 검색할키 ( 예 : White) 로부터다음정보를생성함 ( 해싱테이블참조 ) - 버킷 1(= 85), 시그너쳐 1(= 00101) - 버킷 2(= 87), 시그너쳐 2(= 01001) - 버킷 3(= 89), 시그너쳐 3(= 10100) - 다음을만족하는가장작은 i 를구함 - 시그너쳐 i < 버킷 i 의분리값 ( 시그너쳐 ), i = 1, 2, 3, - 검색레코드는버킷 i 에존재 디렉토리테이블 버킷주소 시그너쳐 예 ) White 검색시, 시그너처 1(00101) < 테이블버킷 85(= 01000), 따라서, 검색할버킷번호는 85 임 Page 39

40 확장성직접파일 (1/2) 현재까지는레코드개수 ( 의최대치 ) 가고정 ( 한정 ) 된경우를다룸레코드수의변화가큰경우는? 확장성직접파일 K: 어느한시점에서파일에저장된레코드개수 Kmin K Kmax ( 최소 Kmin개에서최대 Kmax개의레코드를가짐 ) SPAN = Kmax Kmin (SPAN이클때, 즉, 변화가많을때문제가됨 ) K Kmin: 공간이용률낮음 K Kmax: 적재밀도가높음 ( 저장과검색시간이오래걸림 ) - 해결방안 : 재해싱 ( 많은시간이소요됨, 재해싱동안액세스못함 ) Page 40

41 확장성직접파일 (2/2) 확장성파일 : 높은 SPAN 값을가진파일에대한해싱기법 가상해싱 (virtual hashing) 동적해싱 (dynamic hashing) 확장해싱 (extendible hashing) 선형해싱 (Linear hashing) Page 41

42 가상해싱 (Virtual Hashing) (1/3) 여러개의관련된해싱함수를사용 해싱함수 : 나머지함수 (modular function) 를사용 h 0 : 주소 = 키 mod N (N = 2 0 N) 버킷의수 = N, 버킷크기 = C 오버플로우가발생하면, 관련된버킷을분할 상이한함수를사용하여, C+1개의레코드를재해싱 재해싱함수 h j : 주소 = 키 mod (2 j x N), j = 0, 1, 2,... - h 1 : 주소 = 키 mod 2 1 N - h 2 : 주소 = 키 mod 2 2 N Page 42

43 가상해싱 (Virtual Hashing) (2/3) 가상해싱의예 버킷수 N = 100, 버킷크기 C = 4 버킷 3 = [3, 103, 203, 303] 으로만원 (full) 첫번째해싱함수h 0 = key mod 100 버킷 3 (100 [0 ~ 99]) 새레코드 403 삽입시, 오버플로우발생 다음해싱함수 h 1 = key mod 200 을이용하여버킷분할 버킷 3 (200 [0 ~ 99]) 버킷 103 (200 [100 ~ 199]) Page 43

44 가상해싱 (Virtual Hashing) (3/3) 가상해싱의예 ( 계속 ) 새로운레코드 603, 803 삽입시, 버킷 3 오버플로우발생 다음해싱함수 h 2 = key mod 400 을이용하여버킷분할 버킷 3 (400 [0 ~ 99]) 버킷 103 (200 [100 ~ 199]) 버킷 203 (400 [200 ~ 299]) 어떤함수를적용? 각버킷에적용된해싱함수를유지해야함 검색할키값에적용할해싱함수 h k 를알수있어야함 Page 44

45 동적해싱 (Dynamic Hashing) (1/8) 파일구성 크기가 C 인 N 개의버킷 ( 디스크블록 / 페이지 ) 각버킷을지시하는인덱스 ( 주기억장치 ) 동적해싱의예 N = 20, C = 3 일때, 초기동적해시파일 초기에는인덱스가한레벨 ( 레벨 0) 임 Page 45

46 동적해싱 (Dynamic Hashing) (2/8) 두개의해싱함수사용 해싱함수 H 0 : 레벨 0 인덱스엔트리의한주소로변환 (Binary Tree 의루트식별 ) - H 0 (key) = index value (1 ~ N) - 버킷이계속분할되면, 인덱스는 N개 Binary Tree의 Forest가됨 비트함수 B: 키값을임의길이의 Bit String 으로변환 - 각인덱스트리내에서의분기결정 - 해싱함수로 Binary Tree를결정하고, Binary Tree 내에서의검색은비트함수를활용 저장절차 키를레벨 0 인덱스엔트리의한주소로변환 ( 해싱함수 H 0 를이용 ) 인덱스엔트리의포인터를통해버킷에접근한후레코드를저장 버킷이만원인경우, 버킷을새로할당하여 ( 이미저장된레코드들 + 새로저장할레코드 ) 를분할저장 Page 46

47 동적해싱 (Dynamic Hashing) (3/8) 검색절차 H 0 (key) 함수에의한값 (1 ~ N) 으로 Forest 에서 Binary Tree 의루트를식별하고, B(key) 함수에의한 Bit String 값으로인덱스레벨 1 부터분기를결정함 Page 47

48 동적해싱 (Dynamic Hashing) (4/8) 동적해싱파일의삽입예 버킷분할 : 분할되는버킷이레벨 I 이면, B(key) 의 I+1 번째비트를사용 - 0: 왼쪽 ( 이전 ) 버킷 - 1: 오른쪽 ( 신규 ) 버킷 H 0 와 B에대한예 key H 0 (key) B(key) Page 48

49 동적해싱 (Dynamic Hashing) (5/8) 동적해싱파일의삽입예 ( 계속 ) 레코드 157, 95, 88, 205, 13 을삽입후의초기파일 Page 49

50 동적해싱 (Dynamic Hashing) (6/8) 동적해싱파일의삽입예 ( 계속 ) 레코드 125 를추가로삽입하여버킷이분할된후의파일 Page 50

51 동적해싱 (Dynamic Hashing) (7/8) 동적해싱파일의삽입예 ( 계속 ) 레코드 301, 6 을추가로삽입한후의파일 Page 51

52 동적해싱 (Dynamic Hashing) (8/8) 동적해싱의고려사항 함수 B 의설계 - 레코드의키 ( 또는키에대한어떤함수 H 1 ) 를유사난수생성기 (pseudo random number generator) 의초기값으로사용하여정수를생성 ( 예 : rand(srand(key));) - 생성된각정수를하나의비트로변환 ( 예 : 정수의이진표현에대한패리티비트를사용 ) 인덱스노드들이메인메모리에광범위하게분산되는경우 트리순회과정에서 Page Fault 발생으로추가적인디스크액세스발생가능성있음 인덱스 Forest 가커져서하위레벨인덱스가디스크에저장되어야하는경우 레코드접근시간이오히려증가할수있음 개선책 : 오버플로우버킷을두어버킷분할지연 ( 저장공간효율 ) Page 52

53 확장해싱 (Extendible Hashing) (1/7) 디렉토리와버킷의두단계를가지며, 디렉토리는 2 n 으로증가하는반면에버킷은선형적으로증가함 두단계구성 디렉토리 ( 인덱스에해당 ): 전역깊이 (global depth)(=d) 와버킷에대한 2 d 개의엔트리 (= < 해쉬값, 포인터 >) 로구성되며, 각포인터가반드시상이해야하는것은아님 버킷의집합 ( 레코드저장 ): 레코드들이저장되는공간으로서, 지역깊이 (local depth)(=p) 로구성됨 깊이를나타내는 d 와 p 에대해서는뒤쪽슬라이드의예제를참조할것 2 n Directory key 1 key 2 key 3 key 2 n-1 key 2 n Set of buckets Page 53

54 확장해싱 (Extendible Hashing) (2/7) 확장해싱함수 (Extendible Hashing Function) h: 키 유사키 (pseudo key, 고정길이의 Bit String) 예 ) h(white) = 버킷깊이 : 버킷안의각레코드들의유사키가공통으로가지는처음 Bit String 길이 초기파일 N 개의버킷일때, d = log 2 (N-1) + 1, 디렉토리는 2 d 개의엔트리를가짐 Page 54

55 확장해싱 (Extendible Hashing) (3/7) 확장해싱파일에서의삽입연산 유사키의처음 d비트를이용하여디렉토리액세스하고, 해당버킷을찾아삽입 만약, 해당버킷이만원이면, 1 새로운단말 ( 버킷 ) 을할당 2 버킷깊이가 p이면, 유사키의 (p+1) 번째비트의값에따라 C+1개의레코드를분할 3 d, p+1의값에따라 - d p+1 ( 디렉토리깊이가분할된버킷의깊이를수용하는경우 ): 포인터들을분할, 이전의버킷과새로운버킷모두 p+1의버킷깊이를가짐 - d < p+1 ( 디렉토리깊이가분할된버킷의깊이를수용치못하는경우 ): 디렉터리의크기를두배로늘림 (directory doubling), d d+1 Page 55

56 확장해싱 (Extendible Hashing) (4/7) 확장해싱파일의예 레코드의유사키가시작하고있는 Bit String Page 56

57 확장해싱 (Extendible Hashing) (5/7) d p+1: 버킷만분할 레코드의유사키가시작하고있는 Bit String Page 57

58 확장해싱 (Extendible Hashing) (6/7) d < p+1: 버킷분할및디렉토리확장 레코드의유사키가시작하고있는 Bit String Page 58

59 확장해싱 (Extendible Hashing) (7/7) 확장해싱파일에서의검색연산 유사키의처음 d비트를디렉토리에대한인덱스로사용하여디렉토리에서찾아레코드를접근 디렉토리검색 (Binary Search) 후, 버킷내에서순차검색 확장해싱파일에서의삭제연산 삭제될버킷이버디버킷 (buddy bucket) 을가지고있고, 그두버킷의레코드들이한버킷안에들어갈수있다면, 하나의버킷으로병합한후, 빈버킷을회수하고, 디렉토리엔트리를재조정함 버디버킷 (buddy bucket): 해당버킷과같은깊이값 (p) 을가지고있고, 그유사키들의처음 (p-1) 비트들이모두같은버킷 ( 분할되기이전에한버킷에속했던버킷 ) Page 59

60 선형해싱 (Linear Hashing) 디렉토리를사용하지않는확장성해싱방식 주소공간이확장될때, 해시값을비트 (bits) 를사용 예 : 주소공간이 4인경우, 2 비트주소를생성하는해싱함수를이용 주소공간이 4개의버킷으로구성된것이지 4개의디렉토리노드가버킷을가리키는것이아님에주의 Why linear?: Overflow 가일어날경우, 버킷개수가 linear 하게 ( 하나씩 ) 증가됨 Page 60

61 선형해싱의예 (1/3) 초기상태 삽입과정중버킷 b 에오버플로우발생 첫버킷인버킷 a를분할, 새버킷A를할당 오버플로우레코드들은오버플로우체인 w를할당받아저장 ( 레코드분산을연기하는개념임 ) 버킷 a와새버킷a의주소는3 비트로변경 Page 61

62 선형해싱의예 (2/3) 버킷 d 에오버플로우발생 두번째버킷인 b 를분할, 새버킷 B 를할당 오버플로우버킷 x 생성 버킷 x 에오버플로우발생 세번째버킷인버킷 c 를분할, 새버킷 C 를할당 오버플로우버킷 y 생성 Page 62

63 선형해싱의예 (3/3) 버킷 B 에오버플로우발생 네번째버킷인버킷 d를분할, 새버킷D를할당 오버플로우버킷 z 생성 다음에분할될버킷을가리키는포인터는다시버킷 a를가리킴 모든버킷이 3비트해싱함수를사용하게됨 ( 새로운버킷을생성하여접근하기위해서는 4-비트해싱함술 h 4 () 를이용하는새로운사이클에들어갈준비가된것임 Page 63

64 선형해싱에서의검색 두개의해싱함수사용 현재주소길이를가진버킷에대해서는 h d (k) 사용 확장버킷에대해서는 h d+1 (k) 를사용 레코드의검색을위해해당레코드에어떤해싱함수를적용해야하는지를알아야함 키값k를가지는레코드를포함하는버킷의주소 (address) 를찾기위한프로시저 if (h d (k) p) address = h d (k); else address = h d+1 (k); p = 다음분할될버킷을가리키는포인터 Page 64

65 선형해싱의특징 액세스하고유지해야될디렉토리가없음 오버플로우체인은 ( 실제로 ) 많이길어지지않음 오버플로우가일어날때마다분할을통해주소공간을점차확장하기때문 버킷크기를 50이라할때, 한번검색연산에필요한평균디스크접근수는거의1로밝혀짐 ( 실험결과 ) 저장공간활용도는확장해싱이나동적해싱보다는낮음 ( 평균 60%) Page 65

66 Homework #3 하기두가지사항에대해서각각 0.5 페이지씩 ( 총 1 페이지내 ) 요약하여제출할것 1) 주민등록번호, 2) 이름을키로사용하기위해서가장적합하다고생각하는해싱함수를각각제시하고, 그근거를기술할것 해싱과인덱스 ( 트리 ) 를비교하여, 두방법의장단점을요약할것 Due Date: 5/26( 목 ) Page 66

Microsoft PowerPoint Hash Structures.ppt

Microsoft PowerPoint Hash Structures.ppt 자료처리 () 2006 년봄학기문양세강원대학교컴퓨터과학과 임의접근파일 (Random Access File) 임의접근파일 (random access file) 임의의레코드에그레코드의키값을사용하여그키값을가지는레코드에랜덤하게 ( 직접적으로 ) 접근할수있는파일 (= 직접파일 (direct file), 직접접근파일 (direct access file)) 다른레코드를참조하지않고도,