425. 해시 인덱스 (Hash Index)

⚠️ 이 문서는 트리 구조를 타고 내려가느라 걸리는 시간조차 아까울 때, **수학적인 해시 함수(Hash Function)를 사용하여 "입력값 = 저장된 방 번호"를 1:1로 매핑하여 $O(1)$의 압도적인 속도로 데이터를 찾아내는 '해시 인덱스'**를 다룹니다.

핵심 인사이트 (3줄 요약)

본질: 키 값을 넣으면 고정된 숫자를 뱉어내는 '해시 함수'를 통과시켜, 그 결과값(버킷 주소)에 데이터를 직접 때려 넣거나 찾아오는 구조다.

가치: ID = 5처럼 정확히 일치하는 값(동등 검색, Equality Search)을 찾을 때는 B-Tree보다 훨씬 빠르다. 메모리 기반 DB(Redis, Memcached)의 핵심 기술이다.

한계: 해시 함수는 규칙 없이 숫자를 흩뿌려버리므로, age > 20 같은 범위 검색(Range Search)이나 정렬(ORDER BY)에는 아예 써먹을 수가 없다.

Ⅰ. 개요: 묻지 말고 102번 방으로 가 (Context & Necessity)

B-Tree 인덱스(422번 문서)에서 '김철수'를 찾으려면 수문장(Root Node)부터 시작해서 "김은 왼쪽, 박은 오른쪽..." 이렇게 화살표를 3~4번 타고 내려가야 한다.

해시 인덱스는 이런 밀당을 싫어한다.

"김철수를 어디다 저장할까?"
'김철수'라는 글자를 해시 함수 믹서기에 넣고 돌린다. 결과로 102라는 숫자가 튀어나온다.
디스크의 102번 방(버킷)에 김철수 데이터를 넣는다. 끝이다.
나중에 "김철수 찾아줘!"라고 하면, 다시 믹서기에 돌려 102를 얻고 바로 102번 방 문을 열어버린다. (속도: 1번 만에 찾음, $O(1)$)

📢 섹션 요약 비유: B-Tree가 도서관 사서에게 "ㄱ구역 $\rightarrow$ 기구역 $\rightarrow$ 김철수" 순서대로 물어보며 찾아가는 것이라면, 해시 인덱스는 **'자판기 버튼'**과 같습니다. 102번 버튼을 누르면 그 자리에 있는 음료수(데이터)가 중간 과정 없이 곧바로 툭 튀어나옵니다.

Ⅱ. 해시 인덱스의 2대 핵심 요소

1. 해시 함수 (Hash Function)

어떤 길이의 글자를 넣든 일정한 길이의 숫자를 뱉어내는 수학 공식.
가장 중요한 조건은 "같은 글자를 넣으면 무조건 같은 숫자가 나와야 한다"는 것이다. 그래야 나중에 다시 찾을 수 있다.

2. 버킷 (Bucket)과 체이닝 (Chaining)

해시 함수가 뱉어낸 주소(예: 102번 방)를 버킷이라고 부른다.
해시 충돌(Hash Collision): 만약 '박민수'를 믹서기에 돌렸는데 우연히 똑같이 102가 나오면 어떻게 할까? 102번 방은 이미 김철수가 쓰고 있는데?
해결책 (체이닝): 102번 방에 김철수를 넣고, 그 뒤에 **밧줄(Linked List)**을 달아서 박민수를 엮어둔다. 나중에 102번 방에 와서 줄을 쭉 당겨보며 "박민수 있나?" 하고 하나씩 찾아본다.

Ⅲ. 치명적 단점: 범위 검색 절대 불가 ★

시험에 100% 출제되는 해시 인덱스의 아킬레스건이다.

SELECT * FROM Users WHERE id = 5; (해시 인덱스로 엄청 빨리 찾음)
SELECT * FROM Users WHERE id > 5; (해시 인덱스 사용 불가!)

왜 범위 검색이 안 될까? 해시 함수는 입력값이 1만 달라도 완전히 엉뚱한 주소를 뱉어낸다.

Hash(5) $\rightarrow$ 102번 방
Hash(6) $\rightarrow$ 999번 방 5번과 6번은 숫자상으로는 붙어있지만, 해시 함수를 통과하는 순간 하드디스크 상에서는 완전히 반대편에 저장된다(무작위 분산). 따라서 5보다 큰 것들을 모아서 가져오려면 결국 테이블 전체를 다 뒤져야(Full Scan) 한다.

┌──────────────────────────────────────────────────────────────┐
│           해시 인덱스(Hash Index) 충돌(Collision) 체이닝 시각화         │
├──────────────────────────────────────────────────────────────┤
│                                                              │
│ [ 👨‍💻 입력 데이터 ]                                             │
│  "김철수" ──(해시 함수)──▶ [ 주소: 01 ]                           │
│  "박민수" ──(해시 함수)──▶ [ 주소: 03 ]                           │
│  "이영희" ──(해시 함수)──▶ [ 주소: 01 ] (앗! 철수랑 주소가 겹쳤다!)      │
│                                                              │
│ [ 🪣 해시 테이블 (버킷) ]                                        │
│  버킷 00 : [ 비어있음 ]                                          │
│  버킷 01 : [ 김철수 데이터 ] ──(체이닝 밧줄)──▶ [ 이영희 데이터 ]       │
│  버킷 02 : [ 비어있음 ]                                          │
│  버킷 03 : [ 박민수 데이터 ]                                     │
│                                                              │
│ ★ 특징: 검색은 엄청 빠르지만, 한 버킷에 밧줄이 너무 길게 달리면 느려진다.   │
└──────────────────────────────────────────────────────────────┘

Ⅳ. 결론

"점(Point)을 찌를 때는 해시를, 선(Line)을 그을 때는 트리를 써라." MySQL의 InnoDB 같은 전통적인 디스크 기반 RDBMS는 기본적으로 B-Tree를 사용하고 해시 인덱스를 전면적으로 내세우지 않는다(범위 검색이 너무 중요하기 때문). 하지만 메모리에 데이터를 올려두고 Session_ID = 'abc'처럼 정확한 키값으로만 데이터를 넣고 빼는 Redis나 Memcached 같은 NoSQL(K-V Store)에서는 해시 인덱스가 우주에서 가장 훌륭한 자료구조가 된다. 시스템의 검색 패턴(Equality vs Range)을 분석하여 인덱스 엔진을 선택하는 것이 아키텍트의 기본이다.

📌 관련 개념 맵

대척점 자료구조: B-Tree 인덱스 (422번 문서 - 범위 검색 특화)
해시 충돌 해결법: Chaining (체이닝), Open Addressing (빈 방 찾아서 옆으로 가기)
관련 데이터베이스: Redis (Key-Value Store), Memory-Optimized Tables
보조 기술: Adaptive Hash Index (MySQL이 자주 찾는 B-Tree 잎사귀를 몰래 해시로 만들어주는 최적화 기술)

👶 어린이를 위한 3줄 비유 설명

해시 인덱스는 목욕탕의 '번호 열쇠표'와 같아요. 15번 열쇠를 받으면 그냥 15번 사물함으로 직진해서 문을 열면 되죠. (엄청 빠름)
근데 만약 15번 사물함 안에 이미 다른 아저씨 옷이 들어있으면 어쩌죠? (해시 충돌)
그럴 땐 당황하지 않고 아저씨 옷 위에 내 옷을 같이 포개서 넣어두는(체이닝) 방식이랍니다!