[1회차] DB 인덱스는 왜 빠르고, 언제 느려질까? - MySQL InnoDB의 B-Tree 구조와 UUID 기본 키 실험으로 이해하기

[github-actions[bot]]

🚀 발표 주제

DB 인덱스는 왜 빠르고, 언제 느려질까? - MySQL InnoDB의 B-Tree 구조와 UUID 기본 키 실험으로 이해하기

---

📅 발표일

2026-06-01

🙋 발표자

스타크

🗂️ 카테고리

💾 Database

📚 발표 자료

cs_study.pdf

🎥 발표 영상

업로드 예정

---

🎯 핵심 개념 요약

인덱스가 빠른 이유

인덱스 없이는 전체 행을 순차 탐색(O(n)), 인덱스가 있으면 정렬된 트리 구조로 절반씩 범위를 제거하며 탐색(O(log n))

MySQL InnoDB가 B+Tree를 선택한 이유

이진탐색트리는 노드당 키가 1개라 depth가 깊어지고 디스크 I/O가 많이 발생
B-Tree는 노드당 여러 키를 담아 depth를 낮췄지만, 범위 탐색 시 매번 루트부터 다시 내려와야 하는 단점 존재
B+Tree는 값을 리프 노드에만 저장하고, 리프 노드끼리 연결 리스트로 연결해 범위 탐색에 최적화

InnoDB의 두 가지 인덱스 구조

클러스터드 인덱스: 기본키 기준으로 정렬, 리프 노드에 행 전체 데이터 저장 → 조회 1회로 끝
세컨더리 인덱스: 리프 노드에 기본키 값만 저장 → 클러스터드 인덱스를 한 번 더 탐색하는 더블 룩업 발생

기본키 전략에 따른 성능 차이

AUTO_INCREMENT: 항상 오른쪽 끝에 순차 삽입 → 페이지 분할 없음, 삽입 성능 최적
UUID v4: 랜덤 삽입 → 페이지 분할 빈번, 캐시 히트율 저하, 데이터가 쌓일수록 삽입 비용 급증
UUID v7 / ULID: 시간 순서 기반 생성 → 삽입 패턴이 순차에 가까워 UUID v4 대비 성능 손실 적음

기본키 길이와 저장 공간

세컨더리 인덱스 리프 노드에는 기본키 값이 복사 저장됨 → 기본키가 길수록 세컨더리 인덱스 크기도 증가
CHAR(36) UUID → BINARY(16)으로만 바꿔도 인덱스 크기를 절반 가까이 절감 가능
같은 CHAR(36) 타입이라도 UUID v4는 랜덤 삽입으로 페이지 분할이 잦아 시간 순서 기반으로 생성되는 UUID v7보다 실제 데이터 점유 공간이 큼

결론

영속화 전 식별자가 필요한 경우, UUID v4보다 UUID v7 또는 ULID처럼 시간 순서 기반 전략을 선택하면 큰 성능 저하 없이 동일한 목적을 달성할 수 있음

---

🔗 미션과의 연결

미션에서 예약(Reservation) 엔티티의 equals/hashCode를 재정의하면서, 영속화 전에도 객체 동등성 비교가 가능한 식별자가 필요했다.
단순히 AUTO_INCREMENT 기본키를 사용하면 저장 전에는 ID가 null이라 두 객체를 비교할 수 없는 문제가 생긴다.

이때 UUID처럼 객체 생성 시점에 고유한 값을 미리 부여하는 방식을 떠올릴 수 있다.
하지만 완전한 랜덤 기반인 UUID v4를 기본키로 사용하면 B+Tree 인덱스에서 페이지 분할이 빈번하게 발생하고, 데이터가 쌓일수록 삽입 성능이 급격히 저하된다.

예를 들어 책의 ISBN처럼 외부에서 부여된 고유값을 기본키로 사용하는 것도 주의가 필요하다.
값의 길이가 길거나 생성 시간 기반의 순차성이 보장되지 않는 경우, 세컨더리 인덱스 크기 증가와 클러스터드 인덱스의 랜덤 삽입으로 인한 성능 저하가 발생하기 때문이다.

따라서 영속화 전 식별자가 필요한 상황이라면, 생성 시간을 기반으로 순서가 보장되는 UUID v7이나 ULID를 선택하는 것이 성능 저하 없이 동일한 목적을 달성할 수 있는 현실적인 방법이다.

📚 참고 자료

---

🙋‍♀️ 질문

Q1. B-Tree와 B+Tree의 차이가 무엇인가요?

Q2. UUID v4 삽입 성능이 데이터가 쌓인 이후에 더 크게 저하된 이유가 무엇인가요?

Q3. 세컨더리 인덱스로 범위 조회할 때 기본키 전략에 따라 성능 차이가 나는 이유가 무엇인가요?

[2Jaeheon]

B-Tree와 B+Tree의 차이가 무엇인가요?

리프노드들이 연결되어 있느냐, 연결되어 있지 않는냐의 차이라고 생각합니다.

UUID v4 삽입 성능이 데이터가 쌓인 이후에 더 크게 저하된 이유가 무엇인가요?

UUID로 데이터를 삽입하는 경우 UUID특성상 랜덤값이기 때문에 여러 위치에 분산 삽입이 됨.
데이터가 많아질수록 인덱스가 커지고 페이지가 가득 차며, 캐시 미스와 page split이 증가한다.

세컨더리 인덱스로 범위 조회할 때 기본키 전략에 따라 성능 차이가 나는 이유가 무엇인가요?

쿼리가 세컨더리 인덱스만으로 끝나는 경우에는 UUID 기본키는 세컨더리 인덱스를 크게 만들기 때문에 성능 차이가 남.
여기서 UUID v4처럼 크고 랜덤한 기본키를 사용하였을 때, 기본키가 UUID v4처럼 랜덤하면 클러스터드 인덱스 접근 위치가 흩어져 성능의 저하

추가 학습

분산 환경에서 ID 전략이 중요한 이유

분산 환경에서는 서버만 여러 대인 경우와 DB 쓰기 지점이 여러 개인 경우를 구분해야 한다.
서버가 여러 대여도 하나의 Primary DB가 ID를 발급한다면 AUTO_INCREMENT를 사용할 수 있다.

하지만 샤딩처럼 여러 DB가 각각 데이터를 저장하고 ID를 발급하면,
AUTO_INCREMENT는 각 DB 내부에서만 유일성을 보장하므로 전체 시스템에서는 ID 충돌이 발생할 수 있다.

예시:

Shard A: 서울 예약
Shard B: 부산 예약

Shard A: reservation id = 1
Shard B: reservation id = 1

각 DB 안에서는 정상인데, 전체 서비스 기준으로는 reservationId = 1이 중복

이를 해결하기 위해 UUID나 Snowflake ID 같은 전역 ID 전략을 사용할 수 있다.
UUID는 중앙 조정 없이 ID를 생성할 수 있어 분산 환경에 유리하지만,
UUID v4는 랜덤 값이므로 인덱스 삽입 성능에 불리할 수 있다.

Snowflake ID는 시간, 서버 ID, 순번을 조합해 전역적으로 유일한 숫자 ID를 만들며,
분산 생성이 가능하면서도 시간순 정렬 특성을 어느 정도 유지할 수 있다.

정리 표

상황	설명	핵심
서버만 여러 대	API 서버가 여러 대여도 insert가 하나의 DB로 감	AUTO_INCREMENT 문제 없음
Replica가 여러 개	Replica는 읽기용 복사본이고 ID를 발급하지 않음	쓰기 DB가 하나면 문제 없음
Shard DB가 여러 개	데이터가 여러 DB에 나뉘어 저장됨	각 DB가 id=1을 만들 수 있음
Multi-Master	여러 DB가 동시에 쓰기를 받음	ID 발급 충돌 조정 필요
데이터 병합	여러 시스템에서 만든 데이터를 나중에 합침	전역 유일 ID가 필요

[Jiihyun]

Q1. B-Tree와 B+Tree의 차이가 무엇인가요?

B-Tree는 리프 노드끼리 연결되어 있지 않아 범위 조회 시 다음 리프 노드로 이동하기 위해 부모 노드를 다시 탐색해야 한다. 반면 B+Tree는 리프 노드들이 연결 리스트 형태로 연결되어 있어 리프 노드 간 순차 탐색이 가능하므로 범위 조회 성능이 더 우수하다.
또한 B+Tree는 실제 데이터를 리프 노드에만 저장하고 내부 노드에는 탐색을 위한 키만 저장하기 때문에, 모든 노드에 데이터를 저장하는 B-Tree보다 같은 크기의 페이지에 더 많은 키를 저장할 수 있어 디스크 접근 횟수가 B-Tree보다 적다.

Q2. UUID v4 삽입 성능이 데이터가 쌓인 이후에 더 크게 저하된 이유가 무엇인가요?

UUID v4는 값이 랜덤하게 생성되기 때문에, 데이터가 많이 쌓인 이후에는 인덱스의 중간 위치에 데이터를 삽입해야 하는 경우가 많다. 이 과정에서 순서를 유지하기 위해 리프 노드 분할(Page Split)이 발생할 수 있으며, 경우에 따라 상위 브랜치 노드까지 변경이 전파될 수 있다. 따라서 데이터가 많아질수록 인덱스 유지 비용이 증가해 쓰기 작업이 많이 필요하며 결국 성능이 저하한다.

Q3. 세컨더리 인덱스로 범위 조회할 때 기본키 전략에 따라 성능 차이가 나는 이유가 무엇인가요?

세컨더리 인덱스의 리프 노드에는 인덱스 키뿐만 아니라 기본키도 함께 저장된다. 따라서 기본키가 길수록 세컨더리 인덱스의 크기가 커지게 된다.
인덱스 크기가 커지면 한 페이지에 저장할 수 있는 인덱스 엔트리 수가 줄어들고, 동일한 데이터를 저장하기 위해 더 많은 페이지가 필요해진다. 결국 범위 조회 시 더 많은 페이지를 읽어야 하므로 I/O 비용이 증가해 성능 차이가 발생한다.

[Soojin6943]

Q1. B-Tree와 B+Tree의 차이가 무엇인가요?

B-Tree

• 모든 노드가 데이터를 가지고 있음
• 범위 탐색 시 매번 루트 노드부터 다시 탐색해야함

B+Tree

• 리프 노드만 데이터를 가지고 있음
• 리프 노트끼리 연결되어 있어 범위 탐색이 빠름

Q2. UUID v4 삽입 성능이 데이터가 쌓인 이후에 더 크게 저하된 이유가 무엇인가요?

UUID v4는 랜덤값이기 때문에 AUTO_INCREMENT와 다르게 데이터를 중간에 끼워넣어야 함.
이때, 데이터가 많을 수록 밀어낼 데이터가 늘어나고, 페이지 분할이 자주 일어나게 됨.
-> 성능 저하

Q3. 세컨더리 인덱스로 범위 조회할 때 기본키 전략에 따라 성능 차이가 나는 이유가 무엇인가요?

세컨터리 인덱스는 PK를 저장함. 이때 PK의 길이가 길거나 랜덤 삽입의 경우 인덱스 크기가 커지거나 페이지 분할이 빈번해짐. 이 경우 성능 저하 발생

인덱스의 크기가 클 경우
    -> 메모리에 덜 올라가
         -> 디스크 I/O 증가

랜덤 삽입의 경우
     -> 랜덤이기에 중간에 적절한 위치에 끼워 넣어야 함
         -> 뒤에 있는 데이터 밀어내기 (이때, 페이지 분할 발생 가능)

[Jihyun3478]

Q1. B-Tree와 B+Tree의 차이가 무엇인가요?

• B-Tree: 모든 노드에 (키+데이터)를 저장하므로 노드당 키를 적게 저장하게 되어, 트리 높이가 높아져 탐색 시 디스크 I/O가 많아짐.
• B+Tree: 내부 노드엔 키를, 리프 노드에는 데이터를 저장해 노드당 키를 많이 저장하게 되어, 트리 높이가 낮아져 탐색 시 디스크 I/O가 적어짐. 리프 노드 연결로 범위 조회에 유리함.

Q2. UUID v4 삽입 성능이 데이터가 쌓인 이후에 더 크게 저하된 이유가 무엇인가요?

• 데이터 적을 때: 페이지 분할이 발생해도 영향을 받는 노드가 적고, 트리가 메모리에 올라가 있을 가능성이 높음.
• 데이터 많을 때: 페이지 분할 시 재갱신해야 하는 노드의 깊이가 깊어지고, 디스크 I/O까지 발생하기 때문임.

Q3. 세컨더리 인덱스로 범위 조회할 때 기본키 전략에 따라 성능 차이가 나는 이유가 무엇인가요?

• 오토 인크리먼트: 범위 조회 시 기본키가 연속적이므로, 클러스터드 인덱스에서 인접한 노드만 탐색해 디스크 I/O가 적음.
• UUID v4: 범위 조회 시 기본키가 랜덤이므로 클러스터드 인덱스에서 데이터가 여기저기 흩어져 있어, 노드를 찾을 때마다 디스크 I/O가 발생함. 범위가 넓을수록 더 크게 차이남.

[wontop02]

Q1. B-Tree와 B+Tree의 차이가 무엇인가요?

B-Tree는 모든 노드가 키와 값을 담고 있다. 같은 노드에 있는 값들만 연결되어 있다.
그래서 범위 탐색을 할 때, 노드가 다르면 무조건 루트 노드부터 조회를 다시 시작해야 한다.

B+Tree는 리프 노드에만 값이 존재한다. 각 리프 노드들이 모두 연결되어 있다.
그래서 범위 탐색을 할 때, 연결된 리프 노드를 바로 조회할 수 있다.

Q2. UUID v4 삽입 성능이 데이터가 쌓인 이후에 더 크게 저하된 이유가 무엇인가요?

UUID v4는 값이 무작위로 생성되어, 생성된 값에 따라 삽입 위치를 결정해야 한다.
삽입하려는 페이지의 공간이 꽉 찼을 때는, 공간을 확보하기 위해 페이지 분할이 발생한다.
이 과정에서 많은 디스크 I/O가 발생해 삽입 성능이 저하된다.

Q3. 세컨더리 인덱스로 범위 조회할 때 기본키 전략에 따라 성능 차이가 나는 이유가 무엇인가요?

세컨더리 인덱스 리프 노드에는 기본키가 저장되어 있다.
UUID v7은 시간순으로 정렬되기 때문에, 세컨더리 인덱스를 통해 범위 조회를 할 때 얻은 기본키가 디스크 상에서 물리적으로 인접해 있을 확률이 높다.

반면 UUID v4는 무작위 값이므로 획득한 기본키가 디스크 상에서 흩어져 있다.
그래서 실제 데이터를 가져오기 위해 클러스터드 인덱스를 탐색할 때마다 각기 다른 페이지를 읽어 와야 하는 I/O가 발생해 성능이 떨어진다.