데이터베이스 인덱스 이해하기

1. 등장 배경

데이터베이스의 핵심 역할 중 하나는 필요한 데이터를 빠르게 조회하는 것이다.

테이블에 수백만 건의 데이터가 존재할 때, 조건에 맞는 행을 찾기 위해 모든 행을 순차적으로 검사하는 방식은 Full Table Scan이라 불린다. 이 방식은 데이터가 증가할수록 탐색 비용이 선형적으로 증가하며, 성능 저하로 이어진다.

이러한 문제를 해결하기 위해 인덱스(Index) 개념이 등장했다.

인덱스는 특정 컬럼의 값을 정렬된 구조로 유지하면서, 각 값이 실제 데이터가 저장된 위치를 가리키는 포인터 정보를 함께 관리한다. 이를 통해 데이터베이스는 전체 테이블을 스캔하지 않고도, 조건에 맞는 데이터를 빠르게 찾을 수 있다.

개념적으로 인덱스는 책의 목차나 색인과 유사한 역할을 수행한다.
본문을 처음부터 끝까지 읽지 않고도, 원하는 내용을 즉시 찾아갈 수 있게 해주는 장치다.

2. 인덱스의 내부 구조

2.1 B+ Tree

관계형 데이터베이스에서 가장 널리 사용되는 인덱스 자료구조는 **B+ Tree(Balanced Tree)**다.

2.1.1 B+ Tree의 구조적 특징

B+ Tree는 다음과 같은 특징을 가진다.

데이터가 정렬된 상태로 저장된다
균형 잡힌 트리 구조를 유지한다
- 모든 leaf node가 같은 깊이에 위치
- 검색, 삽입, 삭제 연산이 O(log n) 시간 복잡도로 수행됨
Leaf node 간 연결 구조
- Leaf node끼리 연결되어 있어 범위 검색이 효율적
- 순차 접근이 필요한 쿼리에 유리

2.1.2 쓰기와 읽기의 트레이드오프

인덱스는 읽기 성능을 향상시키는 대신, 쓰기 비용을 추가로 부담하는 구조다.

쓰기 시점:

데이터 삽입/수정/삭제 시 인덱스도 함께 갱신
B+ Tree의 정렬 상태를 유지하기 위한 추가 작업 발생
경우에 따라 트리 재구성(rebalancing) 필요

읽기 시점:

이미 정렬된 구조를 기반으로 트리 탐색을 통해 빠른 검색이 가능
Full Table Scan 대신 트리 탐색으로 데이터 접근
범위 검색 시 leaf node를 순차적으로 읽기만 하면 됨

2.1.3 인덱스가 없을 때의 문제

별도의 인덱스가 없으면 다음 과정을 거친다.

전체 테이블을 읽는다 (Full Table Scan)
조건을 만족하는 행을 필터링한다
정렬이 필요하면 메모리 또는 디스크에서 별도의 정렬 작업(filesort)이 수행된다.

이는 데이터가 많을수록 성능이 급격히 떨어진다.

반면 적절한 인덱스가 있으면:

이미 정렬되어 있어 정렬 과정 생략
필요한 데이터만 선택적으로 접근
메모리 사용량 감소

2.2 다양한 인덱스 자료구조

B+ Tree 외에도 데이터 특성과 쿼리 패턴에 따라 다양한 자료구조가 사용된다.

2.2.1 Hash Index

특징:

Key-Value 쌍으로 저장
등호 조건 검색(=)에 O(1) 성능

제약:

범위 검색 불가능 (>, <, BETWEEN)
정렬 상태를 유지하지 않음
부분 일치 검색 불가능 (LIKE)

사용 사례:

Redis 같은 Key-Value 저장소
특정 조건의 정확한 일치 검색만 필요한 경우

2.2.2 LSM Tree (Log-Structured Merge Tree)

특징:

쓰기를 메모리에 먼저 수행 후 배치로 디스크에 병합
쓰기 증폭(write amplification) 최소화

제약:

읽기 성능이 B+ Tree보다 떨어질 수 있음
주기적인 compaction 필요

사용 사례:

Cassandra, RocksDB
쓰기가 매우 빈번한 시계열 데이터

2.2.3 R Tree

특징:

공간 데이터(2D, 3D)의 범위 검색에 최적화
바운딩 박스 기반 탐색

사용 사례:

지리 정보 시스템 (GIS)
PostGIS 같은 공간 데이터베이스

2.2.4 Bitmap Index

특징:

각 값의 존재 여부를 비트로 표현
카디널리티가 낮은 컬럼에 효율적

제약:

값이 자주 변경되면 비효율적
카디널리티가 높으면 공간 낭비

사용 사례:

성별, 국가 코드 같은 제한된 값
데이터 웨어하우스

2.2.5 B+ Tree를 기본으로 선택하는 이유

일반적인 OLTP(Online Transaction Processing) 환경에서 B+ Tree가 선호되는 이유:

범용성: 등호, 범위, 정렬 모두 효율적으로 처리
균형: 읽기와 쓰기 성능의 적절한 균형
안정성: 수십 년간 검증된 구조
예측 가능성: O(log n)의 일관된 성능 보장

따라서 특수한 워크로드가 아니라면, B+ Tree는 가장 안전하고 범용적인 인덱스 선택지다.

3. 인덱스의 종류

3.1 Clustered Index

Clustered Index는 테이블의 물리적 저장 순서를 결정하는 인덱스다.

MySQL InnoDB 스토리지 엔진에서는 테이블마다 Clustered Index를 자동으로 생성한다.

생성 우선순위

InnoDB는 다음 우선순위에 따라 Clustered Index를 생성한다.

Primary Key ← 일반적
UNIQUE NOT NULL ← PK 없을 때
Hidden Row ID (6byte) ← 모두 없을 때

일반적으로 Primary Key를 기준으로 Clustered Index가 생성되며, InnoDB에서는 Primary Key Index가 곧 Clustered Index다.

구조적 특징

Clustered Index의 leaf node는 행 데이터 전체(row data)를 직접 저장한다.

즉, 인덱스를 통해 데이터에 접근하면 추가적인 탐색 없이 바로 행 데이터를 읽을 수 있다.

Clustered Index (Primary Key = id)

        [Root]
       /      \
    [Node]   [Node]
    /    \   /    \
[id=1] [id=2] [id=3] [id=4]
data1  data2  data3  data4

제약사항

테이블 당 1개만 존재할 수 있다. 데이터의 물리적 배치는 하나로만 결정될 수 있기 때문이다.

3.2 Secondary Index

Secondary Index는 테이블의 컬럼으로 직접 생성한 인덱스다.

Non-clustered Index라고도 불린다.

구조적 특징

Secondary Index의 leaf node는 다음을 포함한다.

인덱스 컬럼 값
Clustered Index를 찾기 위한 포인터 (Primary Key)

Secondary Index (index_column = col)

        [Root]
       /      \
    [Node]   [Node]
    /    \   /    \
[col=1] [col=2] [col=3] [col=4]
col=1   col=2   col=3   col=4
id=1    id=2    id=3    id=4

Secondary Index는 인덱스 컬럼을 key로 가지며,

leaf node에는 실제 데이터 대신 Primary Key를 저장한다.

제약사항

테이블 당 여러 개 생성할 수 있다. 이 때문에 Secondary Index를 통한 조회는 추가로 Clustered Index를 탐색하는 과정이 필요할 수 있다.

4. Clustered Index와 Secondary Index의 조회 과정 비교

4.1 Primary Key를 이용한 데이터 조회

Primary Key를 이용한 조회는 Clustered Index를 통해 데이터를 빠르게 찾을 수 있었다.

SELECT * FROM article WHERE id = 4;

조회 과정:

Clustered Index에서 id=4를 탐색
leaf node에서 data4를 직접 반환

인덱스 트리를 1번만 탐색한다.

4.2 Secondary Index를 이용한 데이터 조회

Secondary Index를 이용한 조회는 어떻게 처리될까?

SELECT * FROM article WHERE col = 4;

조회 과정:

Secondary Index에서 col=4 탐색
col 컬럼에 인덱스가 있어 빠르게 조회
Leaf node에서 포인터 id=4 획득
id=4를 이용해 Clustered Index 탐색
data4 반환

인덱스 트리를 2번 탐색한다.

Secondary Index에서 포인터(PK) 획득
Clustered Index에서 실제 데이터 획득

5. 계시글 목록 조회 - 페이지 번호

5.1 쿼리 실행 과정

SELECT * 
FROM article 
ORDER BY created_at DESC 
LIMIT 10 OFFSET ?;

인덱스 유무에 따라 데이터베이스가 정렬을 어떻게 처리하는지 비교해보면

인덱스가 없을 때

전체 테이블 스캔 (Full Table Scan)
created_at으로 정렬 (filesort)
OFFSET만큼 건너뛰기
10개 반환

인덱스가 있을 때(`created_at` 컬럼에 Secondary Index 생성)

Secondary Index(created_at) 탐색
이미 정렬된 상태 (정렬 과정 생략)
OFFSET만큼 건너뛰기
10개의 포인터(Primary Key) 획득
각 포인터로 Clustered Index 접근하여 실제 데이터 획득

6. 인덱스 설계 시 고려사항

인덱스는 정렬 과정을 생략하고 데이터 접근 속도를 크게 향상시킨다. 그러나 모든 컬럼에 인덱스를 만들 수는 없다. 인덱스 설계 시 장단점을 고려해야 한다.

6.1 인덱스의 장점

검색 속도 향상: O(log n) 시간 복잡도로 데이터 접근
정렬 최적화: 이미 정렬된 상태로 ORDER BY 생략 가능
범위 검색 효율화: Leaf node 연결 구조로 순차 접근 용이

6.2 인덱스의 단점

쓰기 성능 저하
- INSERT, UPDATE, DELETE 시 인덱스도 함께 갱신
- B+ Tree 재구성(rebalancing) 필요
저장 공간 추가 필요
- 인덱스 자체가 디스크 공간 차지
잘못된 설계 시 역효과
- 비효율적인 인덱스는 오히려 성능 저하

6.3 인덱스 선택 기준

인덱스 생성이 효과적인 경우

WHERE 절에 자주 등장하는 컬럼
JOIN 조건으로 사용되는 컬럼
ORDER BY에 사용되는 컬럼
카디널리티가 높은 컬럼 (중복도가 낮은 컬럼)

인덱스가 비효율적인 경우

데이터 변경이 매우 빈번한 컬럼
카디널리티가 낮은 컬럼 (예: 성별, boolean)
테이블 크기가 매우 작은 경우

7. 실제 예시: 게시글 조회 최적화

7.1 테이블 구조

CREATE TABLE article (
    id BIGINT PRIMARY KEY AUTO_INCREMENT,
    title VARCHAR(255),
    content TEXT,
    created_at DATETIME,
    board_id BIGINT
);

7.2 주요 쿼리 패턴

-- 쿼리 1: 최신 게시글 조회
SELECT * FROM article 
ORDER BY created_at DESC 
LIMIT 10;
 
-- 쿼리 2: 특정 게시판의 최신 게시글 조회
SELECT * FROM article 
WHERE board_id = ? 
ORDER BY created_at DESC 
LIMIT 10;

7.3 인덱스 설계

인덱스 1: created_at

CREATE INDEX idx_created_at ON article(created_at);

적용 쿼리: 쿼리 1 (최신 게시글 조회)

정렬 연산 최적화
ORDER BY 절 생략 가능

인덱스 2: 복합 인덱스 (board_id, created_at)

CREATE INDEX idx_board_created ON article(board_id, created_at);

적용 쿼리: 쿼리 2 (특정 게시판의 최신 게시글)

board_id로 필터링
created_at으로 정렬
하나의 인덱스로 두 연산 모두 최적화

7.4 복합 인덱스 컬럼 순서의 중요성

복합 인덱스는 컬럼 순서가 성능을 결정한다.

(board_id, created_at) 순서

-- 효율↑
WHERE board_id = ?
WHERE board_id = ? ORDER BY created_at
 
-- 비효율
ORDER BY created_at  -- board_id 조건 없음

(created_at, board_id) 순서

-- 효율↑
ORDER BY created_at
 
-- 비효율
WHERE board_id = ?  -- 첫 번째 컬럼 조건 없음

설계 원칙

가장 자주 사용되는 필터 조건을 앞에 배치한다.

등호 조건(=) → 앞
범위 조건(>, <) → 뒤
정렬 조건(ORDER BY) → 가장 뒤

8. 인덱스의 한계: OFFSET 기반 페이징

앞서 인덱스가 정렬을 최적화하고 조회 성능을 향상시키는 것을 확인했다.

그러나 인덱스를 적용해도 해결되지 않는 문제가 있다. 바로 OFFSET 기반 페이징이다.

8.1 문제 상황

-- 1페이지
SELECT * FROM article 
ORDER BY created_at DESC 
LIMIT 10 OFFSET 0;
 
-- 100페이지
SELECT * FROM article 
ORDER BY created_at DESC 
LIMIT 10 OFFSET 990;
 
-- 1000페이지
SELECT * FROM article 
ORDER BY created_at DESC 
LIMIT 10 OFFSET 9990;

created_at에 인덱스가 있어도, 뒷 페이지로 갈수록 성능이 느려진다.

8.2 성능 저하의 원인

OFFSET만큼 건너뛰는 과정에서도 데이터를 실제로 읽어야 한다.**

OFFSET 1000, LIMIT 10의 실행 과정:

Secondary Index에서 created_at 기준 정렬된 순서로 탐색 시작
처음부터 1,010개의 포인터(PK)를 순차적으로 읽음
각 포인터마다 Clustered Index 접근하여 실제 데이터 조회
처음 1,000개는 버리고, 마지막 10개만 반환

Secondary Index 탐색: 1,010개 포인터 읽기
    ↓
Clustered Index 접근: 1,010번 실행
    ↓
실제 사용: 마지막 10개만
    ↓
버려진 작업: 1,000개

OFFSET이 커질수록:

읽어야 할 포인터 수 증가 (OFFSET + LIMIT개)
Clustered Index 접근 횟수 증가
버려지는 작업 증가
성능이 선형적으로 나빠짐

8.3 인덱스만으로 해결할 수 없는 이유

인덱스는 정렬과 검색은 최적화하지만, OFFSET의 본질적인 문제는 해결하지 못한다.

정렬 ✅ → 인덱스로 해결
검색 ✅ → 인덱스로 해결
OFFSET ❌ → 건너뛰기 위해서도 데이터를 읽어야 함

8.4 페이징 한계 극복을 위한 해결 전략

1. 테이블 분리 (Partitioning)

게시글을 1년 단위 등 특정 기간별로 테이블을 분리하면 개별 테이블의 크기가 작아져 쿼리 성능이 향상된다. 또한, 각 단위 테이블별로 전체 게시글 수를 관리함으로써 관리 효율성도 높일 수 있다.

2. 애플리케이션 레벨에서의 제한

수십만 번대의 페이지를 조회하는 행위는 일반적인 사용 패턴이라기보다 데이터 크롤링 등 비정상적인 접근일 가능성이 높다. 따라서 게시글 목록 조회를 특정 페이지(예: 100페이지)까지만 허용하고 그 이상은 접근을 차단하여 쿼리 자체를 막는다.

3. 무한 스크롤(No-offset) 방식 활용

OFFSET 대신 마지막으로 조회한 위치(Last ID)를 기준으로 다음 데이터를 가져오는 Cursor-based Paging 방식을 도입하여, 앞부분의 데이터를 건너뛰기 위해 낭비되는 리소스를 제거한다.

이러한 방식들을 서비스의 성격에 맞춰 적절히 조합하여, 데이터 양이 늘어나도 성능 저하 없는 페이징 시스템을 구축할 수 있다.

9. 정리

9.1 인덱스의 역할

인덱스는 데이터 조회 성능을 획기적으로 개선하는 도구다.

정렬 최적화: ORDER BY 절 생략
검색 속도 향상: O(log n) 시간 복잡도
범위 검색 효율화: Leaf node 연결 구조 활용

9.2 인덱스 설계의 트레이드오프

무분별한 인덱스 생성은 오히려 성능을 저하시킨다.

비용:

쓰기 성능 저하 (INSERT, UPDATE, DELETE)
저장 공간 증가
잘못된 설계 시 쿼리 성능 악화

원칙:

실제 쿼리 패턴 분석
카디널리티와 변경 빈도 고려
복합 인덱스 컬럼 순서 신중히 결정

9.3 인덱스의 한계

인덱스는 만능이 아니다.

✅ 정렬 → 인덱스로 해결
✅ 검색 → 인덱스로 해결
❌ OFFSET 기반 페이징 → 근본적 한계 존재

OFFSET이 커질수록 성능이 선형적으로 나빠지는 문제는 인덱스만으로 해결할 수 없다.

해결 방안:

테이블 분리로 데이터 크기 축소
애플리케이션 레벨에서 페이지 제한
커서 기반 페이징으로 방식 전환

9.4 마무리

Clustered Index와 Secondary Index의 동작 방식을 이해하면:

쿼리가 어떻게 실행될지 예측 가능
인덱스 탐색 횟수 파악 가능
더 나은 성능 최적화 전략 수립 가능

인덱스는 올바르게 설계했을 때만 성능 향상을 보장한다.

Gonagi

데이터베이스 인덱스 이해하기

1. 등장 배경

2. 인덱스의 내부 구조

2.1 B+ Tree

2.1.1 B+ Tree의 구조적 특징

2.1.2 쓰기와 읽기의 트레이드오프

2.1.3 인덱스가 없을 때의 문제

2.2 다양한 인덱스 자료구조

2.2.1 Hash Index

2.2.2 LSM Tree (Log-Structured Merge Tree)

2.2.3 R Tree

2.2.4 Bitmap Index

2.2.5 B+ Tree를 기본으로 선택하는 이유

3. 인덱스의 종류

3.1 Clustered Index

생성 우선순위

구조적 특징

제약사항

3.2 Secondary Index

구조적 특징

제약사항

4. Clustered Index와 Secondary Index의 조회 과정 비교

4.1 Primary Key를 이용한 데이터 조회

4.2 Secondary Index를 이용한 데이터 조회

5. 계시글 목록 조회 - 페이지 번호

5.1 쿼리 실행 과정

인덱스가 없을 때

인덱스가 있을 때(created_at 컬럼에 Secondary Index 생성)

6. 인덱스 설계 시 고려사항

6.1 인덱스의 장점

6.2 인덱스의 단점

6.3 인덱스 선택 기준

인덱스 생성이 효과적인 경우

인덱스가 비효율적인 경우

7. 실제 예시: 게시글 조회 최적화

7.1 테이블 구조

7.2 주요 쿼리 패턴

7.3 인덱스 설계

인덱스 1: created_at

인덱스 2: 복합 인덱스 (board_id, created_at)

7.4 복합 인덱스 컬럼 순서의 중요성

(board_id, created_at) 순서

(created_at, board_id) 순서

설계 원칙

8. 인덱스의 한계: OFFSET 기반 페이징

8.1 문제 상황

8.2 성능 저하의 원인

8.3 인덱스만으로 해결할 수 없는 이유

8.4 페이징 한계 극복을 위한 해결 전략

1. 테이블 분리 (Partitioning)

2. 애플리케이션 레벨에서의 제한

3. 무한 스크롤(No-offset) 방식 활용

9. 정리

9.1 인덱스의 역할

9.2 인덱스 설계의 트레이드오프

9.3 인덱스의 한계

9.4 마무리

출처

그래프 뷰

목차

백링크

인덱스가 있을 때(`created_at` 컬럼에 Secondary Index 생성)