#2. Hash vs B+Tree
Hash와 트리의 결정적 차이
# 인덱스의 자료구조: Hash vs B+Tree
> 📘 **학습자료 2편 / 3편** | 연결 퀴즈: [**인덱스 기초1 풀러가기**](quiz.html?set=A)
> 인덱스는 정렬된 색인이라는 건 알았습니다. 그럼 어떤 자료구조에 담을까요? Hash와 B+Tree를 비교하며 InnoDB가 B+Tree를 선택한 이유를 알아봅니다.
> 📚 **이전 편**: [1편 - 인덱스, 왜 필요하고 왜 공짜가 아닌가]
> 1편에서는 인덱스가 조회를 빠르게 하는 대신 변경을 느리게 만드는 트레이드오프라는 점을 살펴봤습니다.
## 이 자료를 다 읽으면 알게 되는 것
- **Hash 인덱스**의 동작 원리와 강점·약점
- **B+Tree 인덱스**가 어떻게 만들어졌는지 (단계별 진화)
- 왜 **B+Tree의 리프 노드 양방향 연결**이 범위 검색에 좋은지
- 왜 **InnoDB는 B+Tree를 기본**으로 쓰는지
---
## 📑 목차
- [1. Hash 인덱스: 글자수로 매핑하기](#1-hash-인덱스-글자수로-매핑하기)
- [2. Hash의 약점 1: 정렬을 못 한다](#2-hash의-약점-1-정렬을-못-한다)
- [3. Hash의 약점 2: 범위 검색을 못 한다](#3-hash의-약점-2-범위-검색을-못-한다)
- [4. Hash의 약점 3: 해시 충돌](#4-hash의-약점-3-해시-충돌)
- [5. 그래서 B+Tree: 정렬된 트리 구조](#5-그래서-btree-정렬된-트리-구조)
- [6. B+Tree에서의 동등 검색과 범위 검색](#6-btree에서의-동등-검색과-범위-검색)
- [7. 정리: 왜 InnoDB는 B+Tree를 기본으로 쓰는가](#7-정리-왜-innodb는-btree를-기본으로-쓰는가)
- [핵심 요약](#핵심-요약)
- [다음 편 예고](#다음-편-예고)
---
## 1. Hash 인덱스: 글자수로 매핑하기
**해시 함수**란 어떤 입력을 받아 고정된 길이의 값으로 변환해주는 함수입니다. 직관적인 예시를 위해, **"과일 이름의 글자 수"** 를 해시 함수로 쓴다고 가정해봅시다.
- 키위 → 2글자
- 바나나 → 3글자
- 파인애플 → 4글자
해시 인덱스는 **(해시 키, 레코드 주소)** 를 한 쌍으로 저장합니다.
이제 사용자가 '파인애플' 정보를 찾는다고 해봅시다.
1. '파인애플'을 해시 함수에 넣는다 → 4
2. 해시 키 4번에 저장된 레코드 주소(5번지) 확인
3. 5번지로 가서 데이터 읽기
**탐색 시간복잡도가 O(1)** 입니다. 데이터가 1억 건이든 10억 건이든, 동등 비교(`=`)로 찾는 속도는 거의 일정합니다.
> 📌 **MySQL 공식 문서의 표현:**
> Hash 인덱스는 `=` 또는 `<=>` 연산자를 쓰는 **동등 비교에서만 사용 가능하지만, 매우 빠르다.**
---
## 2. Hash의 약점 1: 정렬을 못 한다
빠르긴 한데, 치명적인 약점이 있습니다.
해시 함수에는 **"역산 불가능성"** 이라는 성질이 있습니다. 해시값만 보고 원래 입력값을 추론할 수 없다는 뜻입니다. 또한 해쉬충돌을 피하는 것이 효율적이기 때문에, 대부분의 해쉬함수는 입력의 작은 변화에도 해시값은 완전히 달라집니다.
쉽게 말하면, **해시값은 원래 데이터의 "성질"을 전혀 반영하지 않습니다.**
위 그림처럼 키위(abc), 바나나(def), 파인애플(ghr)이라는 해시값만 보고는 원래 과일 이름을 가나다 순으로 정렬할 수 없습니다. 해시값에는 '키', '바', '파'라는 첫 글자 정보가 전혀 남아있지 않으니까요.
**실습으로 확인:**
```sql
SELECT * FROM hash_table ORDER BY value;
```
```sql
EXPLAIN SELECT * FROM hash_table ORDER BY value;
```
| id | select_type | table | type | key | rows | Extra |
|----|-------------|-------|------|-----|------|-------|
| 1 | SIMPLE | hash_table | **ALL** | null | 261921 | **Using filesort** |
`type = ALL`은 **풀 스캔**을 의미하고, `Extra: Using filesort`는 **인덱스를 활용 못해서 임시 테이블에서 따로 정렬했다**는 뜻입니다. 즉, 해시 인덱스는 정렬에 전혀 도움이 안 됐습니다.
> 💡 **EXPLAIN 핵심 컬럼 읽는 법**
> EXPLAIN 결과에서 일단 이 셋만 봐도 70%는 읽힙니다.
> - `type`: 어떤 방식으로 행을 읽었나 (`ALL`은 풀스캔, 나쁨 / `range`, `ref`, `const`는 인덱스 활용)
> - `key`: 실제로 사용한 인덱스 이름 (null이면 인덱스 안 씀)
> - `Extra`: 추가 정보 (`Using filesort`, `Using temporary` 등은 주의 신호)
---
## 3. Hash의 약점 2: 범위 검색을 못 한다
같은 이유로 `<`, `>`, `BETWEEN`, `LIKE` 같은 **범위 검색**도 불가능합니다.
해시값에 원래 값의 크기 정보가 없으니, "1보다 크고 5보다 작은 것"이라는 조건을 해시 인덱스로는 처리할 수 없습니다.
```sql
EXPLAIN SELECT * FROM hash_table WHERE value BETWEEN 1 AND 2;
```
| id | select_type | table | type | key | rows | Extra |
|----|-------------|-------|------|-----|------|-------|
| 1 | SIMPLE | hash_table | **ALL** | null | 261921 | Using where |
역시 `type = ALL`. 풀 스캔입니다.
> 💡 여기까지 읽었다면 Hash 인덱스의 약점을 충분히 이해한 것입니다. [**퀴즈로 확인해보세요!**](quiz.html?set=A)
---
## 4. Hash의 약점 3: 해시 충돌
서로 다른 입력이 우연히 같은 해시값을 가지는 경우를 **해시 충돌**이라고 합니다.
충돌이 일어나면 같은 해시 키 안에서 **추가로 어떤 게 진짜인지 구분**해야 하므로, O(1)이라던 동등 비교 성능도 떨어집니다.
---
## 5. 그래서 B+Tree: 정렬된 트리 구조
Hash가 동등 비교는 빠르지만 **정렬·범위 검색에 약하다**는 게 명확해졌습니다. 그래서 InnoDB가 선택한 것이 **B+Tree** 입니다.
B+Tree의 핵심 아이디어를 차근차근 따라가봅시다.
### Step 1. 정렬해두면 이분 탐색이 가능하다
1부터 100 중 하나의 숫자를 맞추는 게임을 떠올려봅시다.
가장 단순한 방법은 1부터 100까지 하나씩 물어보는 것이겠죠. 최악의 경우 100번이 필요합니다.
조금만 머리를 쓰면 **이분 탐색**으로 줄일 수 있습니다. "50보다 작아?", "75보다 커?"
이렇게 하면 최대 **log N 번** 안에 답을 찾습니다. 1억 개도 27번이면 끝납니다.
**단, 이 방식의 전제조건은 "데이터가 정렬되어 있어야 한다"는 것입니다.**
### Step 2. 정렬된 컬럼 사본 = 인덱스
users 테이블에서 나이가 17살인 사람을 빠르게 찾으려면, 나이 컬럼만 따로 떼어 정렬해두면 됩니다.
이 **"빠른 탐색을 위해 정렬해둔 컬럼 사본"** 이 바로 인덱스의 본질입니다.
### Step 3. 그럼 어떤 자료구조에 정렬해 담을까?
- **배열**: 새로운 값을 끼워넣을 때마다 뒷 데이터를 한 칸씩 미는 비용이 큼 ❌
- **링크드 리스트**: 삽입은 빠르지만, 탐색 자체가 O(N)이라 느림 ❌
- **트리**: 노드끼리 가리키며 절반씩 잘라낼 수 있음 ✅
하지만 아직 아쉬운 부분이 있습니다. 지금부터 트리를 하나씩 강화하며 탐색속도를 더 높여봅시다.
### Step 4. 한 노드에 여러 데이터를 넣자 → B-Tree
기본 트리는 한 노드에 데이터 하나입니다. 노드에 여러 개를 넣으면 어떨까요?
- 한 번 비교에 절반이 아니라 **3분의 1, 4분의 1씩** 더 좁힐 수 있습니다.
- 같은 2번 탐색으로 1-7만 보던 게, 이제는 1-13까지 커버됩니다.
이런 구조가 **B-Tree**입니다.
### Step 5. 리프 노드끼리 연결하자 → B+Tree
B-Tree에서 한 단계 더 나아간 것이 **B+Tree**입니다. 두 가지가 다릅니다:
1. **모든 실제 데이터는 가장 아래쪽 리프 노드에만 저장**됩니다. (위쪽 노드들은 길 안내만)
2. **리프 노드끼리 양방향으로 연결**되어 있습니다.
이 두 번째 특징이 **범위 검색의 게임 체인저**입니다.
---
## 6. B+Tree에서의 동등 검색과 범위 검색
**동등 검색 — 6을 찾는 과정:**
- 7 미만이니까 왼쪽
- 4 이상이니까 오른쪽
- 리프 노드 도달 → 6 찾음
시간복잡도는 **O(log N)**. Hash의 O(1)보다는 느립니다. **동등 비교만 놓고 보면 Hash가 더 빠른 게 맞습니다.**
**범위 검색 — 4부터 7까지 찾기:**
1. 가이드를 따라 **시작점 4를 찾는다**
2. 리프 노드는 양방향 연결되어 있으니, **거기서부터 옆으로 쭉 따라가며** 7이 나올 때까지 읽는다
이게 끝입니다. **시작점만 찾으면 나머지는 그냥 한 줄로 읽어내려가면 됩니다.**
**실습으로 확인** (10만 건 데이터, `WHERE value BETWEEN 1000 AND 5000`):
```
btree_table : 7ms 실행
hash_table : 12ms 실행
```
```sql
EXPLAIN SELECT * FROM btree_table WHERE value BETWEEN 1000 AND 5000;
```
| id | select_type | table | type | key | rows | Extra |
|----|-------------|-------|------|-----|------|-------|
| 1 | SIMPLE | btree_table | **range** | idx_value | 403 | Using where; Using index |
`type = range`. 인덱스를 활용해 범위 스캔을 했다는 뜻입니다.
```sql
EXPLAIN SELECT * FROM hash_table WHERE value BETWEEN 1000 AND 5000;
```
| id | select_type | table | type | key | rows | Extra |
|----|-------------|-------|------|-----|------|-------|
| 1 | SIMPLE | hash_table | **ALL** | null | 100000 | Using where |
해시 테이블은 `type = ALL` — 풀 스캔입니다.
---
## 7. 정리: 왜 InnoDB는 B+Tree를 기본으로 쓰는가
| | Hash 인덱스 | B+Tree 인덱스 |
|---|---|---|
| 동등 비교 (`=`) | **O(1) ⚡** | O(log N) |
| 범위 검색 (`BETWEEN`, `<`, `>`) | ❌ 불가 | ✅ 가능 |
| 정렬 (`ORDER BY`) | ❌ 불가 | ✅ 가능 |
| 해시 충돌 시 성능 | 저하 | 해당 없음 |
동등 비교에서는 Hash가 더 빠르지만, **현실의 쿼리는 범위 검색·정렬·LIKE를 정말 자주 씁니다.** 그래서 모든 쿼리 패턴에 균형 있게 잘 동작하는 **B+Tree가 표준**으로 자리 잡았습니다. InnoDB는 B+Tree만 지원합니다.
---
## 핵심 요약
이번 편에서 꼭 가져가야 할 한 가지:
> 🎯 **B+Tree의 리프 노드 양방향 연결이 핵심**
> 동등 비교만 놓고 보면 Hash(O(1))가 B+Tree(O(log N))보다 빠르지만, **정렬·범위 검색·LIKE 같은 현실 쿼리**까지 고려하면 B+Tree가 압승입니다.
체크리스트:
- [x] Hash 인덱스가 동등 비교에서 **O(1)** 인 이유를 설명할 수 있다
- [x] Hash 인덱스가 **정렬·범위 검색** 을 못하는 이유를 해시 함수의 성질로 설명할 수 있다
- [ ] B+Tree의 **리프 노드 양방향 연결** 이 왜 범위 검색에 결정적인지 설명할 수 있다
- [ ] `EXPLAIN` 결과에서 `type=range` 와 `type=ALL` 의 차이를 안다
> 📝 체크리스트를 다 채울 자신이 있다면? [**인덱스 기초1 퀴즈 도전하기**](quiz.html?set=A)
---
## 다음 편 예고
자료구조는 정해졌습니다. InnoDB의 인덱스는 모두 B+Tree입니다.
그런데 InnoDB에는 **역할이 다른 두 종류의 B+Tree 인덱스**가 있습니다.
> "PK로 만든 인덱스랑, `CREATE INDEX`로 만든 인덱스는 똑같은 B+Tree야?"
> "아니요. 사실 두 인덱스는 **리프 노드에 들어있는 내용이 다릅니다.**"
다음 편에서는 InnoDB의 **클러스터링 인덱스**와 **보조 인덱스**의 차이, 그리고 보조 인덱스로 조회할 때 일어나는 **두 번 탐색** 현상을 알아봅니다. (인덱스 면접의 단골 질문이기도 합니다.)
---
## Reference
- MySQL 공식 문서: [B-Tree and Hash Indexes](https://dev.mysql.com/doc/refman/8.4/en/index-btree-hash.html)
- 코딩애플 - [index가 뭔지 설명해보세요](https://youtu.be/iNvYsGKelYs?si=wL7XfjQ9rvDqMFHm)
- GeeksforGeeks - [Hash Functions and Types](https://www.geeksforgeeks.org/dsa/hash-functions-and-list-types-of-hash-functions)