데이터베이스 인덱스 - B-Tree와 성능 최적화

데이터 접근(검색, 삽입, 삭제 등) 속도를 향상시키기 위해 사용되는 데이터 구조입니다.

 

B-Tree 인덱스

 

보통의 데이터베이스에서 사용되는 인덱스 구조로, 이진검색트리를 일반화한 자료구조입니다. 2개 이상의 자식을 가진 노드를 허용하고 탐색에 평균 O(log N) 시간이 걸립니다.

주요 데이터베이스의 인덱스

• MySQL
• PostgreSQL
• Oracle

B-Tree 구조

B-Tree 구성 요소:
        [50]           ← 루트 노드
       /    \
    [25]    [75]       ← 브랜치 노드 (내부 노드)
    / \     / \
[10][40][60][90]      ← 리프 노드

핵심 원리:
요소들을 선형적으로 탐색하는 것이 아닌
트리 자료구조를 이용해 있을 법한 노드를 기반으로
찾고자 하는 요소를 빠르게 찾는 것

 

B-Tree의 대수확장성

대수확장성이란 트리 깊이가 리프 노드 수에 비해 매우 느리게 성장하는 것을 의미합니다.

4차 B-Tree의 성장 패턴:

깊이 1: 최대 4개 항목
깊이 2: 최대 16개 항목 (4²)
깊이 3: 최대 64개 항목 (4³)
깊이 4: 최대 256개 항목 (4⁴)
깊이 5: 최대 1,024개 항목 (4⁵)

인덱스가 한 깊이씩 증가할 때마다
최대 인덱스 항목의 수는 4배씩 증가

 

B-Tree의 효율성 이유

1. 균형잡힌 트리 구조: O(log N) 탐색 시간
2. 대수확장성: 데이터가 많아져도 깊이는 천천히 증가
3. 다중 자식 노드: 트리의 높이를 낮춤

트리의 높이를 낮추기 위해 그저 자식 노드가 2개가 아니라 보다 많은 키를 노드에 넣은 것

 

인덱스 성능 최적화

 

1. 이중 탐색 비용

인덱스는 두 번 탐색하도록 강요합니다.

검색 과정:
1. 인덱스 트리 탐색 → 데이터 위치 파악
2. 실제 데이터 테이블 접근 → 데이터 조회

탐색에 따른 비용 발생

 

2. 수정 비용

인덱스는 컬렉션이 수정됨에 따라 같이 수정되며 이에 따른 비용이 발생합니다.

-- 데이터 삽입 시
INSERT INTO users (name, email) VALUES ('Alice', 'alice@example.com');

-- 내부적으로 발생하는 일:
-- 1. 테이블에 데이터 삽입
-- 2. name 인덱스 업데이트
-- 3. email 인덱스 업데이트
-- → 인덱스 개수만큼 추가 작업 발생

 

3. 항상 테스팅

인덱스 최적화 기법은 도메인의 특징에 따라 달라집니다. 서비스에서 사용하는 데이터의 크기, 종류, 타입 등이 다르기 때문입니다.

성능 측정 방법

-- MySQL EXPLAIN을 통한 실행 계획 확인
EXPLAIN SELECT * FROM users WHERE email = 'test@example.com';

-- 인덱스 적용 전후 비교
-- Before: type = ALL (풀 테이블 스캔)
-- After: type = ref (인덱스 사용)

EXPLAIN() 함수를 통해 인덱스를 만들고 쿼리를 보낸 이후에 테스팅을 하며 걸리는 시간을 최소화해야 합니다.

 

 

복합 인덱스 설정 방법

복합 인덱스를 설정할 때 인덱스 생성 순서가 매우 중요합니다.

 

인덱스 순서 우선순위

 

1순위: 등가 조건 (=, equal)

어떠한 값과 같음을 비교하는 == 이나 equal 쿼리가 있다면 제일 먼저 인덱스로 설정

-- WHERE status = 'active'
CREATE INDEX idx_user ON users(status, ...);

 

2순위: 정렬 조건 (ORDER BY)

정렬에 쓰는 필드가 있다면 그 다음 인덱스로 설정

-- WHERE status = 'active' ORDER BY created_at
CREATE INDEX idx_user ON users(status, created_at, ...);

 

3순위: 범위 조건 (<, >, BETWEEN)

다중 값을 출력해야 하는 필드, 예를 들어 <, >, BETWEEN 등 많은 값을 출력해야 하는 쿼리라면 그 다음 인덱스로 설정

-- WHERE status = 'active' ORDER BY created_at WHERE age > 20
CREATE INDEX idx_user ON users(status, created_at, age);

 

4순위: 카디널리티

카디널리티가 높은 순서대로 설정

카디널리티(Cardinality): 중복도가 낮을수록 높음

예시:
- email: 카디널리티 높음 (거의 모두 고유값)
- age: 카디널리티 중간 (1~100 정도)
- gender: 카디널리티 낮음 (M/F 2가지)

age와 email 중 email을 먼저 인덱스로 설정

 

복합 인덱스 예시

-- 잘못된 순서
CREATE INDEX idx_bad ON users(age, email, status);

-- 올바른 순서
CREATE INDEX idx_good ON users(
    status,      -- 1. 등가 조건
    email,       -- 2. 카디널리티 높음
    age          -- 3. 범위 조건
);

 

인덱스 설계 원칙

인덱스를 만들어야 하는 경우

• WHERE 절에 자주 사용되는 컬럼
• JOIN 조건에 사용되는 컬럼
• ORDER BY 절에 자주 사용되는 컬럼
• 카디널리티가 높은 컬럼

인덱스를 피해야 하는 경우

• 데이터가 적은 테이블 (수백 행 이하)
• 자주 변경되는 컬럼
• 카디널리티가 매우 낮은 컬럼
• 사용 빈도가 낮은 쿼리의 컬럼

 

인덱스 종류

클러스터형 인덱스

• 테이블당 1개만 생성 가능
• 기본키에 자동 생성
• 데이터가 물리적으로 정렬되어 저장

비클러스터형 인덱스

• 테이블당 여러 개 생성 가능
• 별도의 인덱스 구조 유지
• 데이터 위치에 대한 포인터 저장