[Database System] Hashing File(2)
Database System
Extendible Hashing
Example
- 디렉토리는 버킷 포인터를 저장합니다. 디렉토리 크기 = 4 (d=2)
- 각 버킷은 데이터 레코드를 저장합니다. 각 버킷 크기 = 4
- 해시 함수 h(K)
- K를 이진수로 변환하고
- 끝에서 비트의 마지막 d(=global depth)를 가져옵니다.
Search
- 키가 K인 레코드를 찾으려면 h(K)를 계산하고 디렉토리에서 적절한 포인터를 따르십시오.
- 검색 5; h(5) : 101의 마지막 2자리 = 01; 버킷 B(01)에서 찾았습니다.
- 검색 19; h(19) : 010011의 마지막 2자리 = 11; 버킷 D(11)에서 발견됨
Insert
- 삽입 13; h(13) : 01101의 마지막 2자리 01
- 버킷 B(01)에는 빈 공간이 있으므로 삽입하기만하면 됩니다
- 삽입 20; h(20) : 10100의 마지막 2자리; 버킷 A에 공간이 없습니다.
- 버킷 A가 가득 찼으므로 분할(= 새 버킷 A’ 할당 및 재배포)
- 이 새로운 버킷 A’를 A의 분할 이미지라고 합니다
- 이렇게 하려면 끝에서 추가 3번째 비트를 추가해야 합니다. 3비트; 000, 100
- 또한 디렉토리 크기를 두배로 늘려야 합니다. 새 항목은 버킷 A에 000, 버킷 A’에 100
Directory Doubling
- 디렉토리 크기가 두 배가 되면 해시 함수도 변경해야 합니다. 예를 들어, 20 = 이진수 10100
- 마지막 2 비트(00)는 판별하기에 충분하지 않습니다!
- 마지막 3 비트는 버킷을 결정하는 데 필요합니다. 000, 100
- 디렉토리 이중화에는 다음 단계가 필요합니다.
- 새 버킷을 할당합니다.
- 이전 버킷과 새 버킷을 모두 작성합니다. (재배포)
- 디렉토리 크기를 두 배로 늘리고 포인터를 조정합니다.
- 디렉토리는 일반적으로 각 항목이 포인터이기 때문에 데이터 파일 자체보다 작습니다. 단순히 자신을 복사하여 두 배로 늘릴 수 있습니다. 두 배의 비용은 수용할 수 있습니다.
- 디렉토리가 두 배로 증가한다고해서 버킷 수도 두배가 되는 것은 아닙니다. 오버플로된 버킷만 나뉩니다.
Global/Local depth
- Global depth(d)
- 항목이 속한 버킷을 결정하는 데 필요한 최대 비트 수 입니다.
- 해시된 이진수에서 마지막 d 비트를 가져옵니다. 이 값은 디렉토리 헤더에 저장됩니다.
- 디렉토리가 두 배가 될 때 마다 global depth가 1씩 증가합니다.
- Local depth (l)
- 항목이 이 버컷에 속하는지 여부를 결정하는 데 사용되는 비트 수입니다.(버킷에 local depth가 l 이면 그 안의 모든 항목이 마지막 l 비트와 동일합니다.)
- 버킷이 분할될 때마다(분할로 인해 디렉토리가 두 배로 증가하는지 여부에 관계없이) local depth를 1씩 증가시킵니다.
- 즉, 이전 버킷의 local depth를 1씩 증가시키고 이 증가된 local depth를 새 버킷에 할당합니다.
- 처음에 모든 local depth는 global depth와 같습니다.
Directory Doubling
- 버킷 분할에 항상 디렉토리 이중화가 필요한 것은 아닙니다.
- 2개 이상의 디렉토리 항목이 공유하는 버킷이 분할될 때마다 디렉토리를 두 배로 늘릴 필요가 없습니다.
- 전역 및 로컬 깊이의 차이는 디렉터리 이중화에 영향을 미칩니다. 따라서 각 버킷에 대한 로컬 깊이를 유지하여 디렉터리 이중화가 필요한지 여부를 결정합니다.
- 로컬 깊이가 글로벌 깊이와 동일한 버킷이 분할되는 경우(local depth(l) > global depth(d)), 디렉토리는 두 배가 되어야 합니다.
- 9를 삽입하면 버킷 B가 분할되더라도 디렉토리가 두 배로 증가하지 않습니다. → 로컬 깊이만 증가
- 버킷 A 및 A’는 전역 깊이와 동일한 로컬 깊이를 가집니다. 그것들이 가득 차서 분할되며 디렉토리가 두 배가 되어야 합니다.
- 예를 들어, 64, 8, 128을 A에 삽입하거나 28, 60을 A’에 삽입합니다.
Search/Insert
- 검색 키 K로 레코드를 검색하려면
- K에 해시 함수를 적용하고(d개의 마지막 숫자를 취하여) 이 디렉토리 포인터가 가리키는 버킷을 찾습니다.
- 검색 키 K로 레코드를 삽입하려면
- 올바른 버킷을 검색하여 삽입하십시오.
- 오버플로우가 발생한다면,
- l <= d,
- 오버플로된 버킷을 분할하고 재배포합니다.
- l 을 1씩 증가
- l > d,
- 오버플로된 버킷을 분할하고 재배포합니다.
- l 과 d 모두 1씩 증가시킵니다.
- 디렉토리 크기를 두 배로 늘리고 포인터를 조정합니다.
- l <= d,
Delete
- 검색 키 K 로 레코드를 삭제하려면
- 올바른 버킷을 검색하여 제거하십시오.
- 버킷이 비어 있으면
- 버킷을 분할 이미지와 병합합니다.
- l 을 1 만큼 감소
- 각 디렉토리 포인터가 이전 버킷과 분할 이미지(새 버킷)을 모두 가리키는 경우 디렉터리 크기는 절반으로 줄어들고 d 는 1만큼 감소합니다.
- 병합하지 않을 때, 삭제 후 버킷이 비어 있으면 병합 비용을 절약하기 위해 빈 공간을 남겨 두십시오.
- 데이터 항목을 제거하여 버킷이 비어 이쓰면 분할 이미지로 병합(예: 32, 16 삭제 후 A’와 병합)
- 모든 버킷이 두 개의 디렉토리 요소를 가리키는 경우 디렉토리를 절반으로 줄여야 합니다(실제로는 필요하지 않지만)5
Exercise 1) 4, 5, 7을 삽입한 후 결과 표시 2) 그런 다음 4, 5, 7을 삭제한 후 결과를 표시합니다.
Directory Doubling
- 디렉토리에서 최하위 비트를 사용하는 이유는 무엇입니까?
- 복사를 통해서 이중화가 가능합니다!
Performance : Extendible Hashing
- 디렉토리가 메인 메모리에 맞는 경우(실제로 이러한 가능성이 매우 높음) 단일 액세스로 동등 검색에 응답할 수 있습니다. 그렇지 않으면 두 개의 I/O가 필요합니다.
- 일반적인 예로 데이터 항목당 100바이트이고 페이지 크기가 4KB인 100MB 파일에는 100만 데이터 항목이 포함되고 디렉토리에는 약 25,000개의 요소만 포함됩니다. (각 페이지/버킷에는 대략 40개의 데이터 항목이 포함되며 버킷당 하나의 디렉토리 요소가 있습니다.)
- 반면에 디렉토리는 커지고 커집니다.
- 블록당 레코드 수가 작으면 버킷 분할이 예상보다 빨리 발생할 수 있습니다.
- Skewed 데이터 분포는 빈번한 디렉토리 이중화로 이어질 수 있습니다. 좋지 않은 공간 활용!
Linear Hashing
- 선형 해싱에서 버킷의 수는 선형 방식으로 증가하고 감소합니다.
- 확장 가능한 해싱과 달리 선형 해싱은 디렉토리를 사용하지 않습니다.
- 충돌을 자연스롭게 처리하고 버킷 분할 시기를 결정하는 유연한 기준을 제공합니다.
- 선형 해싱을 사용하면 공간 활용도를 높이기 위해 오버플로 체인을 사용할 수 있습니다.
- 오버플로가 발생하면 항상 오버플로된 버킷이 분할되는 것은 아닙니다.
-
그러나 선형 해싱은 데이터 파일의 키 분포가 왜곡된 경우 성능이 저하될 수 있습니다. (확장 가능한 해싱보다 나쁠 수 있음)
- 주요 아이디어는 해시 함수 h0, h1, h2, … 각 함수의 범위는 이전 함수의 범위의 두 배 입니다. h1가 검색 키를 M 버킷 중 하나에 매핑하면 hi+1 이 2M 버킷 중 하나를 매핑합니다.
- 초기 해시 함수 h 와 초기 버킷 수 N이 주어지면 이러한 해시 함수 h0, h1, h2, … 는
- hi(K) = h(K) % (2i * N) for i = 0, 1, 2, …
- 예를 들어 N = 32 개의 버킷을 가정합니다.
- i = 0; h0(K) = h(K) % (2^0 * 32) ; 범위 [0 ~ 31]
- i = 0; h0(K) = h(K) % (2^1 * 32) ; 범위 [0 ~ 63]
- i = 0; h0(K) = h(K) % (2^2 * 32) ; 범위 [0 ~ 127]
Bucket Splits : Round Robin
- 주요 아이디어는 분할 라운드의 개념입니다. 버킷은 라운드 시작부터 첫 번째 버킷부터 마지막 버킷까지 하니씩 분할되므로 버킷 수가 두 배로 늘어납니다.
- 확장 가능한 해싱과 달리 삽입이 분할을 트리거할 때 키가 삽입되는 버킷이 반드시 분할되는 버킷은 아닙니다.
- 분할을 트리거한 새로 삽입된 데이터 항목을 정적 해싱으로 저장하기 위해 오버플로 페이지가 추가됩니다.
- 그러나 분할할 버킷이 라운드 로빈 방식으로 선택되기 때문에 결국 모든 버킷이 분할되어 체인 길이가 하나 또는 두 페이지 이상 되기 전에 오버플로 체인의 데이터 항목을 재배포합니다.
- 카운터 레벨은 현재 라운드 번호를 나타내는 데 사용됩니다. 처음에는 0으로 설정되어 있습니다.
- 다음은 분할할 버킷을 나타내는 데 사용됩니다. 처음에는 버킷 0으로 설정됨 (즉, 첫 번째 버킷)
- 라운드 레벨 시작 시 버킷 수를 NLevel로 표시합니다.
- NLevel = N * 2^Level 임을 쉽게 확인할 수 있습니다.
- hLevel로 라운드 레벨에서 해시 함수를 나타냅니다. 라운드 번호 레벨 동안 해시 함수 hLevel 및 hLevel+1만 사용됩니다.
- 버킷 분할은 분할할 다음 버킷을 표시하기 위해 Next를 1씩 증가시킵니다. Next가 마지막 버킷 위치 이상으로 증가하는 상황을 어떻게 처리할 수 있는가?
- Next > 2^Level * (N - 1) 이면 현재 해시 테이블의 모든 버킷이 hLevel+1 함수를 통해 해시됩니다.
- 라운드 로빈 방식으로 진행하면, Next > 2^Level * (N - 1) 인경우
- Level을 1씩 증가
- 0 옆으로 재 설정(해시 테이블 상단에서 다시 분할 시작)
- 일반적으로 오버플로된 버킷은 즉시 분할되지 않지만 라운드 로빈 분할로 인해 늦어도 다음 라운드에서 분할됩니다.
Example
- Level : 현재 라운드 번호; 처음에는 라운드 0
- Next : 분할할 버킷; 처음에는 버킷 0
- NLevel : 라운드 레벨의 버킷의 수; 처음에는 N0 = N = 4
- 각 버킷 크기는 4
- 해시 함수 hLevel
- h0(key) = key % 4
- h1(key) = key % 8
Insert
- 새로운 오버플로 페이지가 추가될 때마다 분할할 수 있습니다.
- Next 버킷이 분할되면 hLevel (즉, h(key) = key % 8) 이 Next 버킷과 분할 이미지 간에 항목을 배포하는 데 사용됩니다.
- 버킷을 분할한 후 Next는 1씩 증가합니다.
- 모든 삽입이 분할을 트리거하는 것은 아닙니다. 37*을 삽입한 후 해당 버킷에 공백이 있습니다. 분할이 필요하지 않습니다. Next는 증가하지 않습니다.
- 때때로 Next 버킷이 가득 차서 이 버킷에 새 항목이 삽입됩니다.
- 이 경우 분할도 필요하지만 오버플로 페이지는 필요하지 않습니다.
- 22, 66, 34를 삽입한 후 Next은 0라운드의 마지막 버킷인 버킷 3입니다.
- Next가 NLevel-1이고 분할이 트리거되면 버킷 수가 두 배로 늘어납니다. 레벨을 1씩 증가시키고 Next를 0으로 재설정하여 새 라운드를 시작합니다. 버킷 3의 오버플로페이지는 분할 후에 제거됩니다.
- 안 좋은 케이스도 있는데
- 19, 15, 3, 23, 27 을 삽입하게 되면
Exercise
- 4개의 버킷을 모두 분할 할 수 있는 최소 레코드 삽입 수는 얼마입니까? 이러한 삽입 후 Next의 값은 무엇입니까?
- 예를 들어, 63, 41, 73, 137, 18, 34, 66, 130을 삽입하십시오.
Search
- 주어진 검색 키 값 K로 레코드를 검색하기 위해 해시 함수 hLevel(K)을 적용하고 이것이 분할되지 않은 버킷 중 하나로 연결되면 간단히 그곳을 찾습니다.
- 분할 버킷 중 하나로 이어지는 경우 항목이 있을 수 있거나 이 버킷을 분할하여 이 라운드 초반에 새 버킷으로 이동되었을 수 있습니다.
- 두 버킷 중 항목이 포함된 버킷을 결정하기 위해 hLevel+1(K)을 적용합니다.
- 35* 검색
- 25* 검색
- 37* 검색
- hLevel / hLevel+1을 적용하여 올바른 버킷 검색
- 삽입할 버킷이 가득 차지 않으면 삽입하십시오. (Next의 값은 변경되지 않음)
- 삽입할 버킷이 가득 찬 경우
- 오버플로 페이지 추가
- 삽입
- Next 버킷 분할
- Next 증가
- 참고: 버킷은 라운드 로빈 방식으로 분할되므로 긴 오버플로 체인이 발생하지 않습니다!
Delete
- 44를 삭제하면,
- Level은 변경되지 않지만 Next는 1만큼 감소합니다.
- 33을 삭제하면,
- Level은 1만큼 감소하고 Next는 1만큼 증가합니다.
Performance : Linear Hashing
- 버킷에 오버플로 페이지가 없는 한 동등 검색은 단일 액세스로 응답할 수 있습니다.
- 실제로 균일한 배포를 위한 평균 비용은 약 1.2개의 디스크 액세스 입니다.
- 라운드 동안 모든 버킷은 차례로 분할됩니다. 좋은 해시 함수는 모든 버킷에 균일하게 키를 배포합니다.
- 버킷에 배포 후 오버플로 페이지가 있으면 오버플로 체인의 길이가 줄어듭니다.
- 대부분의 버킷에서 오버플로 체인의 길이는 0 입니다. 각 라운드에서 각 버킷에 최소한 한 번 이상의 재배포가 있기 때문입니다. 따라서 라운드 중 오버플로 페이지수는 1을 넘지 않을 것으로 예쌍됩니다. (대부분 1 이나 2)
- 실험 결과는 다음과 같습니다. 버킷 크기가 50인 경우 I/O는 약 1입니다.
Extendible vs Linear
Extendible
- 확장 가능한 해싱은 새 데이터가 추가될 때 전체 버킷을 분할하여 오버플로 페이지가 필요하지 않습니다.
- 왜곡된 데이터로 커질 수 있습니다. 메인 메모리에 맞지 않는 경우 추가 I/O
- 중복에는 오버플로 페이지가 필요할 수 있습니다.
- 버킷을 추적하기 위한 디렉토리는 주기적으로 두배로 증가합니다.
Linear
- 선형 해싱은 버킷을 라운드 로빈으로 분할하고 오버플로 페이지를 사용하여 디렉터리가 필요하지 않습니다.
- 오버플로 페이지는 길지 않을 것입니다.
- 중복을 쉽게 처리합니다.
- 균등 분포의 경우 디렉토리 액세스가 없기 때문에 품질 검색에 대한 평균 비용이 확장 가능한 해싱보다 낮습니다.
- 편향된 분포의 경우 (거의) 빈 버킷이 생성될 수 있습니다. 공간 활용은 확장 가능한 해싱보다 낮을 수 있습니다.(평균 60% : 평균 69%)
Hashing vs. B+ Trees
- 해시 파일은 동등 검색에 가장 적합합니다. 특히 ATM, 항공사 예약, 긴급 서비스 등의 실시간 애플리케이션.
- 그러나 해시 파일은 범위 쿼리를 지원하지 않는 반면 B+ 트리는 동등 검색과 범위 검색을 지원합니다.
- 일반적인 DBMS에서는 B+ 트리 및 해시 기반 인덱싱 구조에 대한 지원을 찾을 수 있습니다.
- 해시 인덱스는 쿼리 최적화 프로그램에 대한 관계형 연산자를 구현하는 데 사용할 수도 있습니다.
- B+ 트래 vs Hashing : O(logFN) vs O(1)
댓글남기기