9~10주차 - B트리 및 해시 테이블
B트리(다진 검색 트리)
정의
- 디스크의 접근 단위: 블록(페이지)
- 디스크에 한번 접근하기 위해서는, 수십만의 명령어를 처리하는 시간과 비슷함
- 검색트리가 디스크에 있으면 트리의 높이를 줄이는 것이 중요함
- 다진 검색 트리가 균형을 유지하게 하여, 디스크 접근 횟수를 줄이는 것
특징
- 하나의 노드가 기존 이진 트리와 다르게, 자식 노드를 여러 개 가질 수 있음
삽입
- x: 삽입할 키, t가 트리의 루트 노드일 때, x를 삽입할 리프 노드 r를 찾아 r에 삽입함
- 이때 오버 플로우가 발생 할 경우, r의 형제 노드 중, 여유가 있는 노드에서 처리함
- 만약, 여유가 있는 노드가 없을 경우, r를 2개로 분할 및 가운데 키를 부모 노드로 넘김
- 이 과정에서 부모 노드 p에 오버플로우가 발생할 경우, p에서 다시 오버플로우를 해결한다
해시 테이블
개요
- 사전을 구현하기 위한 기술
- 현재 기준에서 가장 좋은 검색 성능을 제공(\(Θ(1)\))
용도
- 공개키 암호 알고리즘
- 컴파일러의 심볼테이블
- DB의 저장 스킴
- 데이터 동기화 검증
- 개인 정보 보호 인터넷 주소 암호화(Yahoo)
- 매우 빠른 응답을 요구하는 서비스
- 119 호출과 호출번호 관련 정보 검색
- 주민등록 시스템
저장 검색의 복잡도
- 배열
- \(O(n)\)
- 이진 탐색 트리
- 평균적으로 \(Θ\)
- 레드 블랙 트리
- 최악의 경우에는 \(Θ(log n)\)
- 해쉬 테이블
- 평균 \(Θ(1)\)
특징
- 값의 저장 위치가 원소의 값에 의해 결정됨
- 평균 상수 시간에 삽입, 검색, 삭제가 가능함
- 매우 빠른 응답을 요구하는 서비스에 유용
- 최소 원소 검색 등의 연산은 지원하지 않음
- 정렬을 지원하지 않으므로, rank도 불가능함
해쉬 함수
특징
원소가 해쉬 테이블에 균일하게 정렬되어야 한다
계산이 간단해야함
대표적 방법
나누기(Division)
\(h(x) = x mod m\)
m: 테이블의 크기
곱하기(Multiplication)
충돌
- 해시 테이블에서 하나의 주소에 2개 이상 원소가 배정되려고 하는것
해결 방법
체이닝(Chaining)
- 같은 주소의 원소를 하나의 linked list로 관리하는 것
- 추가 linked list가 필요함
- linked list로 생성할때, 새로 삽입된 원소는 리스트의 제일 앞 부분에 삽입함
- 단점
- 연결 리스트의 구조를 필요로 함
- 체인의 길이가 증가하면 탐색 시간이 \(O(n)\)으로 증가함
- 연결 리스트의 운영 비용이 비쌈
개방 주소 방법(Open Addressing)
- 충돌이 발생하더라도 테이블 공간에서 해결하는 것
- 빈 공간이 발생할때까지 해시값을 계속 생성하는 것
추가 공간이 필요하지 않음
3가지 방법
Linear probing(선형 조사)
충돌 발생시 충돌이 발생하지 않을때까지 한칸씩 이동하는 방식
배열의 끝까지 이동시 처음 인덱스로 돌아와 다시 탐색함
수식: \(h_i(x) = (h(x) + i) mod m\)
단점
Primary Clusting(1차 군집)1에 취약함
Quadratic probing(이차원 조사)
수식: \(h_x(x) = h(x) + i^2\)
i: 충돌 횟수
단점
- Secondary Clustering(2차 군집)2에 취약함
Double Hashing(더블 해싱)
2개의 해싱을 이용해 처리하는 방식
수식:
\(h(x) = x mod (테이블 크기)\)
\(f(x) = (x mod h(x)) + 1\)
\(h_i(x) = (h(x) + i * f(x)) mod (테이블 크기)\)
주의 사항
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.