1. 개요: DB에서 해시(Hash)의 개념
- 해시는 **키(key)를 해시 함수(Hash Function)에 통과시켜 계산된 주소(버킷)**에 데이터를 저장하는 방식.
- 해시 기반 저장 구조는 일반적으로 **빠른 단일 레코드 접근(=Point Access)**에 최적화됨.
- 주로 Heap, B-Tree 등 다른 인덱싱 기법에 비해 고속의 검색 성능이 필요한 경우 활용.
2. 해시 기반 저장 구조의 특징
| 항목 | 설명 |
|---|---|
| 접근 방식 | 키를 해시 함수에 넣어 계산된 주소로 직접 접근 (O(1)) |
| 인덱스 구조 | 고정 길이 또는 동적 길이의 버킷 구조 사용 |
| 적용 용도 | 주로 OLTP 시스템의 키 기반 조회, Cache 시스템, 분산 DB |
3. 해시 테이블 구조 요소
- 해시 함수 (Hash Function): 키 값을 일정 범위의 숫자(버킷 인덱스)로 변환
- 버킷 (Bucket): 해시 값에 따라 매핑된 실제 저장 공간
- 슬롯 (Slot): 하나의 버킷 내에 저장될 수 있는 실제 데이터 위치
- Directory (동적 해시에서): 해시 결과를 관리하는 메타 구조
4. 충돌(Collision) 및 해결 방식
4.1 충돌 발생 원인
- 서로 다른 키가 같은 해시 값을 가질 경우(해시 충돌)
- 해시 함수의 분포 불균형, 버킷 수 부족 등
4.2 해결 기법
(1) 체이닝(Chaining)
- 같은 버킷에 여러 개의 레코드 연결 (리스트 형태)
- 구현 간단하나, 성능은 리스트 길이에 따라 저하
(2) 오픈 어드레싱(Open Addressing)
-
충돌 발생 시 다른 버킷(빈 슬롯)을 찾아 삽입
- 선형 탐사(Linear Probing)
- 이차 탐사(Quadratic Probing)
- 더블 해싱(Double Hashing)
-
메모리 효율적이나 클러스터링 현상 발생 위험
5. 해시 인덱스(Hash Index) vs B-Tree 인덱스
| 항목 | 해시 인덱스 | B-Tree 인덱스 |
|---|---|---|
| 조회 속도 | 매우 빠름 (O(1)) | 빠름 (O(log n)) |
| 범위 조회 | 불가능 또는 비효율적 | 매우 효율적 |
| 메모리 사용 | 낮음 | 중간~높음 |
| 충돌 가능성 | 있음 (해결 필요) | 없음 |
| 재구성 필요 | 테이블 확장 시 필요 | 자동 균형 조정 |
6. 고급 해시 기법
(1) 동적 해싱 (Dynamic Hashing)
- 테이블 확장 가능
- 디렉토리 사용하여 해시 깊이 조정
- 대표: Extendible Hashing
(2) 선형 해싱 (Linear Hashing)
- 버킷을 순차적으로 분할하여 확장
- 디렉토리 구조 없음 → 메모리 사용 효율 높음
(3) 분산 해싱 / 일관 해싱(Consistent Hashing)
- 분산 데이터베이스, NoSQL, DHT에서 사용
- 노드 추가/삭제 시 데이터 재배치 최소화
- 대표 적용: Cassandra, DynamoDB, Redis Cluster
7. 활용 사례
| 시스템 | 해시 활용 방식 |
|---|---|
| Oracle | Hash Cluster, Partition Hash |
| MySQL | Memory 엔진의 Hash 인덱스 |
| Redis | 내부 구조가 해시 기반 |
| NoSQL | Key-Value DB 대부분 해시 기반 |
| 분산 DB | Consistent Hashing (노드 샤딩, 분산 저장) |
8. 기술사 수준 통찰 및 고려사항
- 해시는 특정 조건에서 매우 효율적이나 보편적인 인덱스로는 부적합.
- 범위 질의, 정렬, 다중 조건에서는 B-Tree나 Bitmap 인덱스가 더 적절.
- 충돌 처리에 따른 튜닝 필요: 해시 함수 설계, 버킷 크기 관리, 디렉토리 크기 조절 등.
- 파티셔닝 전략과 결합 시: 해시 파티셔닝이 테이블 샤딩에 효과적
- 해시 테이블 성능 문제는 주로 충돌률 증가와 재해싱 비용에서 발생
DevSecOps Pentest🚩