LEE CHANWOO

📝 Blog 2024 version 1.5.2
🔖 JUN 29, 2024

6 분 소요

Database System

Hashing File

  • 다음 쿼리는 빠른 응답 시간이 필요합니다.
    SELECT name, address
      FROM Customers
     WHERE ID = 123456789
  • 다음 쿼리는 많은 equality test(e.g., index nested-loop join)가 필요한 조인 및 프로젝트 작업이 모두 필요합니다.
    SELECT C.name, P.name
      FROM Customers C, Purchase P
     WHERE C.ID = P.ID
  • 고객 테이블에 2 * 10^7 튜플이 있다고 가정합니다.
  • 구매 테이블에는 10^5 튜플이 있습니다.

  • 각 고객과 구매는 모두 100바이트이고 각 페이지 크기는 2,048입니다.

  • 해싱 인덱스는 품질 검색과 관계 연산자(조인, 프로젝션, …)를 효율적으로 지월할 수 있습니다.

Hashing

  • 해시 함수 h를 사용하여 검색 키의 주소를 결정합니다.
  • 각 버킷에는 검색 키 세트가 포함되어 있습니다. 버킷 모음을 해시 테이블이라고 합니다.
  • h(K): 검색 키 K를 포함하는 버킷의 주소

image

Overview

  • Loading Density(Factor)
  • Collisions/Overflows
  • Hashing Functions
  • Overflow Handling
  • Internal or External
  • Static or Dynamic

Loading Factor

  • Loading Factor(α) = r / (s * b)
    • r: 파일의 (검색) 키의 수
    • s: 버킷당 키 수
    • b: 버킷의 수

  • 예를 들어, r = 1,000, b = 750, s = 2라고 하면 α = 67% 입니다.

  • α가 높으면 공간 활용도가 높지만 검색 및 삽입에 많은 오버헤드가 발생합니다.
  • 실험에 따르면 α > 70% 이면 충돌이 증가합니다. 그래서 일반적으로 각 버킷에 20~30%의 빈 공간을 남겨둡니다.
  • 예를 들어, r = 60,000, s = 12; 버킷당 30%의 추가 공간을 가정합니다. 그런 다음 b = (60,000/12)/0.7 = 7,143버킷

Collision/Overflow

  • 두 개의 서로 다른 검색 키를 동일한 버킷에 해시하면 이 충돌을 호출합니다. 즉, k1 ≠ k2 일떄 h(k1) = h(k2)
  • 가득찬 버킷에 삽입하기 위해 일부 검색 키를 해시할 때 오버플로가 발생합니다.
  • 충돌이 발생하지 않으면 검색은 하나의 버킷 액세스뿐입니다!
  • 오버플로가 발생하면 다른 버킷을 검색해야 합니다. 최악의 경우 모든 버킷을 찾아야 합니다. (O(b))
  • 일반적으로 충돌/오버플로를 피할 수 없습니다.

Examples: Collision/Overflow

  • b = 26, s = 2, r = 10인 해시 테이블
  • 해시 함수 h : 검색 키의 첫 번째 문자 (a, b, c, …, z)
  • {atan, ceil, floor} : 충돌
  • {clock, ctime} : 오버플로

image

Hash Function

  • 좋은 해시 함수의 기준
    • 각 버킷에는 가능한 모든 검색 키 값 집합에서 동일한 수의 검색 키가 균일하게 할당됩니다.
    • 키 K를 무작위로 선택하면 h(K) = i일 확률은 모든 버킷 i에 대해 1/b입니다. 그런 다음, 임의의 K는 b 버킷 중 하나에 해시할 동일한 기회를 갖습니다.
  • 버킷 크기도 고려해야 하는데
    • s는 오버플로 체인의 발생을 최소화하기에 충분히 큽니다.
    • s는 버킷 점유가 작고 너무 많은 공간이 낭비될 정도로 커서는 안됩니다.
  • 잘못된 해시 함수는 많은(모든) 검색 키 값을 동일한 버킷에 매핑합니다.(삐뚤어진 분포(Skewed distribution)라고 함) 이렇게 하면 액세스 시간이 파일의 검색 키 수에 비례합니다.
  • 잘못된 해시 함수의 예
    • 전화번호: 처음 3자리는 좋지 않습니다.(마지막 3자리가 더 좋음)
    • 생년월일: 생년 보다는 생일이 좋다.
    • 사람이름: 첫 번째 알파벳은 좋지 않다.
    • 계좌잔액: 범위 1에서 10,000의 잔액을 10개의 버킷 [1, 1000], [1001, 2000], …, [9001, 10000]
      • 각 버킷에는 동일한 수의 다른 잔액 값이 있으므로 균일합니다.
      • 1에서 1000 사이의 잔액을 가진 키가 9001에서 10000사이의 잔액을 가진 레코드보다 더 일반적이기 때문에 무작위가 아닙니다.

Example: Hash Function

  • Modular Division(모듈러 산술)
    • h(K) = K % b, b: 버킷의 수 [0 .. b-1]
    • b의 선택은 매우 중요합니다. b가 짝수로 선택되면 매우 나쁩니다. b는 일반적으로 균등 분포를 위한 소수로 선택됩니다.
    • 예를 들어, r = 4,000개의 키, 버킷당 20%의 추가 공간, b = 5,000개의 버킷이 필요합니다. 마지막으로 b = 5,003을 선택합니다.
  • Mid-Square(중간 제곱법)
    • 검색 키 K를 제곱한 다음 제곱된 결과의 중앙에서 적절한 자릿수를 사용하여 K에 대한 버킷 주소를 얻습니다.
    • 중간 비트는 일반적으로 균등 분포를 보장합니다. 버킷 주소를 얻는 데 사용되는 자릿수는 해시 테이블 크기에 따라 다릅니다.
    • 예를 들어, K = 9452이고 b = 4000이면, 9452^2 = 89340304
      • 중간에서 4자리를 취합니다. 즉, 3403
  • Shift Folding
    • 검색 키 K를 마지막 부분을 제외하고 동일한 크기의 여러 부분으로 나눕니다.
    • 그런 다음 파트들을 더하여 K에 대한 버킷 주소를 얻습니다.
    • 예를 들어, K = 12320324120은 x1 = 123, x2 = 203, x3 = 241, x4 = 20, 다음을 더하여 버킷 번호 587을 얻습니다.
  • Rotation
    • 마지막 숫자를 검색 키 K의 앞으로 rotate한 다음 시프트 폴딩을 적용하여 K에 대한 버킷 주소를 얻습니다.
    • 이것은 키가 직렬로 할당될 때 유용합니다. 예를 들어, 6001 600101, 600102, 600103, 600104 → (rotate) → 160010, 260010, 360010, 460010, 그런 다음 시프트 폴딩을 사용하여 26, 36, 46, 56을 얻습니다.

Overflow Handling

  • Open Addressing
    • 오버플로가 발생하면 모든 버킷이 열립니다. 공간이 생길 때까지 버킷을 찾으십시오. 그뒤 새 검색 키를 삽입하십시오.
      • Linear Probe
      • Quadratic Probe
      • Double Hashing
  • Separate chaining
    • 오버플로가 발생하면 오버플로 버킷을 할당하여 동일한 충돌 검색 키의 연결 목록을 유지 관리합니다.
    • 새 검색 키를 삽입하려면 목록의 키만 검사하면 됩니다.

Linear Probe

  • 비어 있는 것을 찾을 때까지 다음 순서로 버킷을 검사합니다.
    • (h(x) + i) % b (for i = 0, 1, 2, . . . and i ≤ b – 1)
    • b: 해시 테이블의 버킷 수
  • 이 접근 방식은 매우 간단합니다. 그러나 이는 서로 다른 해시된 검색 키와 비교하여 불필요한 검색이 필요합니다.
  • 또한 클러스터를 생성할 수 있습니다.(= 동일한 해시 값 키의 연속 컬렉션) 이러한 클러스터는 더 많은 키를 삽입함에 따라 병합되는 경향이 있으므로 나중에 더 큰 클러스터로 이어집니다. 그들은 검색을 증가시킬 수 있습니다.
  • 예상 평균 시간
    • (2 – α)/(2 – 2α), 균등 해시 함수를 가정하여

Separate chaining

  • 각 버킷별로 연결되 키 목록을 유지합니다.
  • 각 목록에는 해당 버킷에 대한 모든 동의어가 있습니다.
  • 검색하려면 해시 값이 동일한 키만 검사해야 합니다.
  • 각 버킷에 대한 추가 공간(포인터)이 필요합니다.
  • 예상 평균 시간
    • 1 + α/2, 비균등 해시 함수를 가정하여

Exercise

  • Keys(K) = {54, 28, 26, 5, 30, 78, 52, 2, 80, 31, 29, }
  • 키 수 = 11, 버킷 수 = 26, 버킷 크기 = 1

  • h(K) = K % 26, loading factor(α) = 11/26 = 0.42

  • Linear Probe image

  • Separate chaining image

  • Linear Probe vs Chaining image

  • 키당 평균 버킷 액세스 수
  • 8개의 다른 해시 테이블
  • 33,575, 24,050, …
  • 두 가지 다른 해시 함수

Hashing File: External Hashing

이제 모든 데이터가 디스크에 있는 외부 해싱을 소개합니다. 각 버킷은 디스크 블록(페이지)에 해당합니다. 각 버킷에는 데이터 항목 모음이 포함되어 있습니다. (1) Static Hashing (2) Dynamic Hashing: Extendible Hashing, Linear Hashing

image

  • 참고 : 버킷 디렉토리를 사용할 필요는 없습니다. 선택 사항입니다.

Static Hashing

  • 기본 버킷이라고 하는 고정된 수의 M 순차 블록을 할당합니다.
  • 기본 버킷의 수는 변경되지 않습니다.
  • 기본 버킷이 가득 차면 오버플로 버킷이 할당됩니다.
  • 범위가 h인 해시 함수를 정의합니다. [0, …, M-1]

image

  • 키 K를 사용하여 레코드에 대한 검색(또는 삽입/삭제)을 수행하려면
    • 키 값에 해시 함수 h를 적용합니다.(즉, 계산h(K))
    • h(K) 번호로 기본 버킷 페이지에 액세스합니다.
    • 이 페이지에서 레코드를 검색(삽입/삭제)하거나 필요한 경우 버킷 h(K)의 오버플로 체인에 액세스합니다.
  • 기본 버킷은 순차적으로 할당되기 떄문에 오버플로 체인 접근이 필요하지 않다면
    • 검색: 단일 I/O
    • 삽입/삭제: 2개의 I/O(읽기/쓰기)

Problems: Static Hashing

  • 정적 해싱의 주요 문제는 버킷 수가 고정되어 있다는 것입니다.
  • 파일이 커지면 (α > 0.8), 충돌이 증가하면, 오버플로 체인이 길어지면서 성능이 저하될 수 있습니다.
  • 파일이 축소 되면 (α < 0.5), 기본 해시 버킷의 많은 공간이 (거의) 비어 있을 수 있습니다. 즉, 페이지 공간 낭비입니다.

  • 특히, 불균등한 데이터 분포는 오버플로 체인을 증가시켜 검색 성능을 심각하게 저하시킵니다.(ISAM file 처럼)

  • 정적 해싱을 위한 일반적인 해결책
    • 80% 점유: 처음에 페이지를 80% 가득 채움으로써 파일이 너무 커지지 않는 경우 오버플로 페이지를 방지할 수 있습니다.
    • Reorganization: 80% 점유율을 달성하고 오버플로가 발생하지 않도록 다른 해시 함수로 파일을 주기적으로 다시 해시합니다. 하지만 시간이 걸립니다.
      • 더 큰 해시 테이블을 만들고, 현재 테이블을 스캔하고, 키를 삽입해야 합니다.
      • 새로운 해시 함수를 사용하여 새 테이블로 전체 파일을 다시 해시하십시오
      • 또한 해시 인덱스는 rehashing 중에 사용할 수 없습니다.
  • 또 다른 해결책은 동적 해싱(Dynamic Hashing)입니다. 파일의 증가/축소를 수용하기 위해 해시 함수를 동적으로 수정할 수 있습니다.
    • Extendible Hashing(Fagin, et al.)
    • Linear Hashing(Litwin)

Extendible Hashing

버킷이 오버플로되면 버킷 수를 두 배로 늘려 파일을 재구성하겠습니까? 모든 버킷 페이지를 읽고 쓰는 데 비용이 많이 들기 때문에 이 아이디어는 좋지 않습니다!

또 다른 아이디어는 버킷에 대한 포인터 디렉토리를 사용하는 것입니다.

  • 일부 버킷이 오버플로되면 오버플로된 버킷만 분할하여 디렉터리 크기를 두 배로 늘립니다!
  • 디렉토리는 파일보다 훨씬 작으므로 두 배로 늘리면 훨씬 저렴합니다.
  • 데이터 항목의 하나의 버킷 페이지만 분할됩니다.
  • 오버플로 페이지가 필요하지 않습니다!
  • 확장 가능한 해싱은 (추가)디렉터리를 사용하여 버킷에 액세스합니다. 따라서 간접 참조 수준이 하나 더 도입됩니다.
  • 디렉토리에는 디렉토리 크기를 결정하는 global depth(d)가 있습니다. 또한 각 버킷에는 local depth가 있습니다.
  • 디렉토리에는 2^d 항목이 있으며 각 항목은 버킷에 대한 포인터를 저장합니다
  • 검색키 K가 주어지면 해시 함수를 다음과 같이 정의합니다.
    • K를 이진수로 변환
    • 끝에서 이 2진수의 마지막 d비트를 가져옵니다. 이 d비트의 수는 K의 버킷 주소입니다.

댓글남기기

참고