[DATABASE] 인덱스 구조와 원리의 이해

이영재·2025년 5월 20일

B+TREE B-tree Database mysql 인덱스

DB 정복 대작전

목록 보기

3/6

0. 들어가며

예전에 면접에서 인덱스 관련 질문을 받았다.

👩‍ : "인덱스가 뭔가요?"
🥔 : "검색 속도를 높이기 위한 자료구조입니다."
👩‍ : "그럼 MySQL은 어떤 인덱스 구조를 쓰는지 아시나요? B+Tree 아세요?"
🥔 : 음...

이후 질문에는 제대로 대답하지 못했다.
그 순간, 단순히 개념만 외우는 것만으로는 부족하다는 걸 느꼈다.
‘빠르다’는 건 알겠는데, 정확히 어떻게 동작하고 왜 그렇게 빠른지에 대해서는 설명할 수 없었다.

그래서 이번 글에서는 인덱스의 개념부터 MySQL이 사용하는 B+Tree 구조,
그리고 인덱스를 언제 쓰는 게 효과적이고, 언제 오히려 비효율적인지까지 정리해보려 한다.

실제로 인덱스는 성능 최적화의 핵심이지만, 잘못 쓰면 발목을 잡기도 한다.
면접 질문 하나에서 시작된 고민이지만, 지금은 실무에서도 꼭 짚고 넘어가야 할 주제라고 생각한다.

1. 인덱스

1.1 인덱스란?

인덱스(Index)는 데이터베이스에서 검색 속도를 빠르게 하기 위해 사용하는 자료 구조다.
쉽게 말해, 책의 목차처럼 원하는 데이터를 빠르게 찾기 위해 미리 만들어둔 데이터의 정렬된 목록이다.

1.2 인덱스를 사용하는 이유

1. 검색 속도 향상

인덱스 없으면: 전체 테이블 탐색 (Full Table Scan)
인덱스 있으면: 인덱스 탐색 → 빠르게 해당 row 위치 탐색

2. WHERE, JOIN, ORDER BY, GROUP BY 등에서 성능 최적화

WHERE : 조건 필터링
JOIN : 연결 키 기반 row 탐색
ORDER BY : 이미 정렬된 인덱스 기반 순회
GROUP BY : 인덱스 기반 그룹핑 성능 향상

3. 중복 제약 조건 검사에 사용

UNIQUE, PRIMARY KEY 는 인덱스를 사용하여 값 중복을 빠르게 판별함

4. 데이터 무결성과 성능의 균형

인덱스는 SELECT에선 빠르게 하지만 INSERT/UPDATE에선 부하가 있음
따라서 조회 빈도가 높은 컬럼에만 인덱스를 적용하는 것이 일반적 전략

때문에 인덱스는 대량의 데이터가 있는 시스템에서 특히 중요한 역할을 한다. 주로 반복적으로 조회되는 컬럼에 인덱스를 적용하는 것이 효과적이다.

1.3 인덱스 사용 예시

SELECT * FROM USER WHERE grade = 2;
총 2,000명의 학생이 저장된 USER 테이블에서, 2학년 학생만 조회하는 쿼리라고 가정해보자.

만약 인덱스가 없다면 모든 레코드를 확인해야한다.(Full Table Scan)

USER 테이블의 모든 row를 처음부터 끝까지 읽고 각 row에서 grade 값을 확인해서 결과 row 를 반환한다.
2,000명 중 1명만 찾더라도 전체 테이블을 다 스캔한다.
데이터가 커질수록 성능이 떨어진다.

이번엔 인덱스(idx_grade)가 있다면

MySQL은 먼저 grade 인덱스를 탐색하여 B+Tree 구조 상에서 grade = 2인 row의 위치(PK)를 모두 찾고 실제 데이터를 조회한다.
조건에 해당하는 row만 직접 접근하고
데이터가 커져도 성능이 저하되지 않는다.

MySQL(InnoDB)의 인덱스는 내부적으로 B+Tree라는 구조를 기반으로 구현되어 있다.
이는 B-Tree의 개념을 확장한 형태이며 데이터를 정렬된 상태로 저장하고, 범위 조회나 순차 탐색에 최적화된 구조다.

B-Tree 와 B+Tree에 대해서 자세히 알아보자.

2. B-Tree

2.1 B-Tree란?

일반적인 트리부터 살펴보자.


일반적인 Tree	최악의 Tree 구조

일반적인 트리는 분할정복 방식으로 평균 O(logN)의 시간 복잡도로 트리 내에서 데이터를 찾을 수 있다.
하지만 최악에 경우 한 쪽으로 편향된 데이터가 저장된다면 다음과 같은 최악의 구조가 될 수 있다.

이러한 성능 저하 문제를 해결하기 위해 등장한 것이 바로
균형 잡힌 트리 구조인 B-Tree이다.

B-Tree 구조

2.3 B-Tree 가 만들어지는 과정

아래는 3차(차수 3) B-Tree가 생성되는 과정을 보여준다.

삽입 순서는 다음과 같다
1 → 15 → 2 → 5 → 30
이러한 key 값이 순서대로 삽입될 때, B-Tree는 내부적으로 균형(Balanced)을 유지하면서 분할(Split)과 승격(Promotion)을 수행한다.

B-Tree 삽입 규칙 정리

항상 Leaf 노드에 데이터를 삽입한다.
삽입 후 노드가 차수를 초과하면,
- 가운데 key를 기준으로 좌우로 분할(Split)하고
- 가운데 key는 부모 노드로 승격(Promotion)된다.
루트 노드가 분할되면, 트리의 깊이가 1 증가한다.

삽입 과정을 그려보면...

이렇게 B-Tree는 삽입이 반복되더라도 트리 전체의 균형을 유지하며 검색 성능을 항상 O(log N)으로 보장할 수 있도록 구조가 자동으로 조정된다.

3. B+Tree

B-Tree는 데이터의 검색에는 유리하다. 하지만 모든 데이터를 풀 스캔하려면 모든 트리를 전부 방문해야 한다.

이러한 단점을 개선한 것이 B+Tree 이다.

3.1 B+Tree 란?

B+Tree는 리프 노드에만 데이터를 저장하고 모든 리프노드를 Linke List를 통해 연결한다.
대신 값을 찾기 위해 반드시 리프 노드까지 내려가야 하고, 브랜치 노드에 중복된 key가 존재할 수 있다는 점은 고려해야 한다.

그럼 이 구조로 어떤 이점을 얻을까?

3.3 B+Tree 특징 정리

트리 높이 감소 (검색 속도 향상)
- 내부 노드에 데이터 없이 키만 저장하므로 한 노드에 더 많은 키 저장 가능
- 트리의 차수가 높아져 전체 높이가 낮아지고, 디스크 I/O가 줄어든다.
범위 검색 및 순차 접근에 최적화
- 리프 노드가 정렬된 상태로 Linked List로 연결되어 있어
- BETWEEN, ORDER BY, LIMIT 쿼리에 매우 효율적
효율적인 메모리 및 저장 공간 사용
- 중복 데이터 없이 리프 노드에만 실제 데이터 저장
- 내부 노드는 키와 포인터만 포함해 공간 활용도가 높음

4. B-Tree vs B+Tree 비교

구분	B-Tree	B+Tree
데이터 저장 위치	내부 노드와 리프 노드에 모두 저장	리프 노드에만 저장
내부 노드 구성	키 + 데이터	키 + 포인터만
리프 노드 연결	연결되어 있지 않음	Linked List로 연결됨
트리 높이	상대적으로 깊어질 수 있음	더 많은 키 저장 가능 → 트리 높이 낮음
검색 효율	단일 키 검색은 빠름	단일 검색 + 범위 검색 모두 효율적
범위 검색 성능	트리 재탐색 반복 필요 → 비효율적	한 번 탐색 후 리프 노드 순차 접근 가능
중복 키 저장	없음	가능 (브랜치 노드에 중복 키 존재)
사용 예시	메모리 기반 트리 (TreeMap 등)	디스크 기반 DB 인덱스 (MySQL, Oracle 등)
인덱스 구조로의 적합성	디스크 I/O 최적화에 불리함	디스크 I/O 최소화에 최적화

인덱스가 그렇게 좋은데, 왜 아무 컬럼에나 다 쓰지 않을까?

5. 인덱스를 어떻게 사용해야 할까?

5.1 인덱스 사용의 특징

인덱스는 읽기 성능을 극적으로 향상시킨다.
SELECT, WHERE, ORDER BY, JOIN, GROUP BY 등에 모두 활용 가능하다.
**정렬된 구조(B+Tree)**를 기반으로 하므로, 범위 검색이나 순차 접근에도 강력하다.
인덱스는 기본적으로 디스크 공간을 추가로 사용하며, 유지 관리 비용이 발생한다.

✅ 읽기는 빠르게!
❌ 하지만 쓰기와 저장에는 비용이 든다.

5.2 인덱스 사용의 단점

쓰기(INSERT/UPDATE/DELETE) 성능 저하
- 인덱스도 매번 함께 갱신되어야 하므로
  → 테이블에 인덱스가 많을수록 쓰기 성능은 저하됨
디스크 공간 추가 사용
- 인덱스도 별도의 데이터 구조이므로
  → 특히 보조 인덱스가 많아지면 스토리지 부담 커짐
잘못 만든 인덱스는 오히려 성능 악화
- 잘못된 순서의 복합 인덱스, 낮은 선택도(중복 많은 컬럼) 인덱스는 사용되지 않거나 쿼리 플랜을 왜곡시킬 수 있음

5.3 인덱스를 사용하면 좋은 경우

조회(SELECT) 비중이 높은 테이블
검색 조건으로 자주 사용하는 컬럼
- WHERE user_id = ?
- WHERE created_at BETWEEN ? AND ?
정렬이나 그룹 연산이 자주 발생하는 컬럼
- ORDER BY, GROUP BY, DISTINCT 등에 포함되는 컬럼
조인(JOIN) 조건으로 사용되는 컬럼
- 특히 외래키(FK) 역할을 하는 컬럼

예: 유저가 많은 서비스의 user_id, email, created_at 등

5.4 인덱스를 사용하지 않는 것이 좋은 경우

→ Full Table Scan이 더 효율적인 경우

작은 테이블 (예: 몇 백 건 이하)
- 인덱스 조회보다 그냥 한 번 다 읽는 게 더 빠름
선택도가 낮은 컬럼 (중복 많음)
- 예: gender, status = 'ACTIVE' 같이 값이 거의 다 같은 경우
- → 인덱스를 써도 대부분의 row를 접근해야 하므로 비효율
계산이나 함수가 적용된 WHERE 조건
- 예: WHERE YEAR(created_at) = 2024
- → 인덱스를 타지 않고 Full Scan
LIKE '%abc'
- 와일드카드가 앞에 오면 인덱스 사용 불가

💡 "인덱스를 만든다고 다 쓰는 게 아니다."
→ 결국 선택도(필터링 비율)와 사용 패턴이 핵심이다.

마무리 요약

인덱스는 "읽기 성능을 위한 강력한 도구"지만 쓰기 성능과 저장 효율을 희생하기 때문에 전략적으로 적용해야 한다.

실제로는 쿼리 패턴, 테이블 크기, 컬럼 특성 등을 고려해 정밀하게 설계하는 것이 중요하다.

이영재

이전 포스트

[DATABASE] MySQL 내부 동작 이해 – InnoDB vs MyISAM 비교

다음 포스트