데이터베이스의 저장과 접근: 해싱

Computer Science/DataBase

J._.cobb 2022. 4. 27. 01:24

다른 레코드의 참조 없이 목표 레코드의 접근을 직접 지원
- 직접 파일(direct file)
키(key) 값과 레코드 주소(address) 사이의 사상(mapping) 관계를 함수로 설정
해싱 함수(hasing function)
- 키(key) 값으로부터 레코드 주소(address)를 계산
- 사상 함수(mapping function) : 키 → 주소
- 삽입, 검색에 모두 이용

버킷(bucket)
- 하나의 주소를 가지면서 하나 이상의 레코드를 저장할 수 있는 파일의 한 구역
- 버킷 크기: 저장 장치의 물리적 특성과 한번 접근 올 채취 가능한 레코드 수를 고려
버킷 해싱
- 키 → 버킷 주소
충돌(collision)
- 상이한 레코드들을 같은 주소(버킷)으로 변환
- 동거자(synonym)
- 버킷 만원
- 오버플로 버킷
- 한번의 I/O가 추가됨

충돌에 대처하기 위해 제안된 기법
레코드 검색은 최대 2번의 디스크 접근만 필요
모조 키(pseudokey)
- 확장성 해싱 함수: 키 값이 일정 길이의 비트 스트링, pseudokey로 변환
- pseudokey의 처음 d비트를 디렉터리의 인덱스로 사용
디렉터리(directory)
- 헤더에 현재의 디렉터리 깊이 d를 유지
  - d : 전역 깊이 (global depth)
- $2^d$ 개의 버킷들을 지시할 수 있는 포인터 엔트리로 구성
- 디스크에 저장
버킷
- 헤더에 현재의 버킷 깊이 p를 유지
  - p: 지역 깊이 (local depth)
- 각 버킷에 저장된 레코드들의 모조 키들은 처음 p 비트가 모두 동일
저장
- 저장할 레코드 모조 키의 처음 d 비트로 디렉터리를 접근
- 엔트리 포인터가 지시하는 버킷에 레코드를 저장
- 버킷의 오버플로우 처리
  - 새로운 버킷을 할당
  - 버킷의 깊이가 p인 오버플로우 된 버킷과 새로 할당된 버킷의 깊이를 모두 (p+1)로 설정
  - 오버플로우된 버킷에 있는 레코드들과 새로 저장할 레코드를 모조 키의 (p+1) 번째 값에 따라 기존의 오버플로우 된 버킷과 새로 할당한 버킷에 분산
  - 이때 만일 d<(p+1)이 되면 디렉터리 오버플로우가 발생
    - d값을 1증가시켜 디렉터리 크기를 2배로 확장
    - 2배로 증가된 디렉터리 엔트리 포인터들을 모두 조정

모조 키가 10으로 시작하는 레코드를 저장. 네 번째 버킷은 오버플로우
빈 버킷을 할당하고 버킷을 분할: 버킷의 깊이 p는 모두 2로 설정
- 오버플로우 된 버킷에는 모조 키 10으로 시작하는 레코드만 남김
- 새 버킷에는 모조키 11로 시작하는 레코드를 이동시켜 저장
디렉터리의 110과 111의 포인터 값이 새 버킷을 지시하도록 조정

출처