[자료구조] 자료구조 해싱

목차

■ 다른 레코드 참조없이 목표 레코드 직접 접근 키값과 레코드 주소 사이의 관계 예측
■ 충돌(collision)
■ 해싱에서의 충돌해결
■ 오버플로우 해결 방법
■ 오버플로우 처리 방법

본문내용

■ 다른 레코드 참조없이 목표 레코드 직접 접근
키값과 레코드 주소 사이의 관계 예측

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

▲ 확장성 해싱
• 충돌 문제에 대처하기 위해 제안된 기법
• 특정 레코드 검색 - 1~2번의 디스크 접근
• 기본키 사용
• 2단계 구조 : 디렉토리와 버켓
• 디렉토리
◦ 정수값 d를 포함하는 헤더와 버켓들을 지시하는 2d 개의 포인터로 구성
- d = 디렉토리 깊이(depth)
◦ 디스크에 저장
• 모조키(pseudokey)
◦ 확장성 해싱 함수: 키값 → 일정 길이의 비트 스트링(모조키)
◦ 모조키의 처음 d 비트를 디렉토리 접근에 사용
• 버켓 - 정수값 d'(≤d)가 저장된 헤더 존재
◦ d' = 버켓 깊이 = 버켓에 저장된 레코드들의 모조키들이 처음부터 d' 비트까지
모두 동일

참고 자료

없음