시스템 & 인프라/PintOS & CS

[데이터베이스] DB 인덱스(Index) 핵심 원리: B-Tree 구조와 검색 성능 최적화

kugorang 2025. 1. 16. 16:28
728x90

TL;DR (세 줄 요약)

  1. 인덱스는 테이블의 컬럼 값과 그 값이 있는 레코드의 위치를 정렬해서 저장해 둔 별도의 자료구조입니다. 조회할 때 테이블 전체를 읽지 않고 필요한 위치만 읽게 해 줍니다.
  2. 인덱스는 조회를 빠르게 하지만, 데이터를 넣고 고치고 지울 때는 인덱스도 함께 고쳐야 해서 쓰기가 느려지고 디스크 공간도 더 씁니다.
  3. WHERE, JOIN, GROUP BY, ORDER BY에 자주 쓰이는 컬럼 중 선택도가 높은 것부터 인덱스를 만듭니다. 만든 뒤에는 EXPLAIN으로 실제로 쓰이는지 확인합니다.

이 글은 한 기업의 직무 테스트를 본 뒤에 쓴 기록입니다. CS 기초 필기 시험이었는데, 데이터베이스 인덱스를 설명하는 문항을 끝까지 쓰지 못했습니다. 인덱스는 초당 트랜잭션 수(TPS)와 응답 속도에 큰 영향을 주기 때문에 면접과 실무에서 자주 나오는 주제입니다. 지원한 분야가 모바일 게임 서버여서 더 중요했습니다. 그때 정리하지 못한 내용을 다시 공부해서 적었습니다.

원통 모양 데이터베이스 여러 개와 그 위에 놓인 돋보기를 그린 삽화. 주변에 DATABASE INDEXING OPTIMIZATION 글자가 적혀 있음
그림. 데이터베이스와 돋보기를 그린 삽화

1. 인덱스는 무엇인가요?

먼저 용어를 정리합니다. 데이터베이스는 데이터를 테이블에 저장합니다. 테이블은 행과 열로 이루어진 표입니다. 열을 컬럼이라고 부르고, 행 하나를 레코드라고 부릅니다. 데이터베이스에 보내는 요청문을 쿼리라고 부릅니다.

인덱스는 테이블의 특정 컬럼 값과, 그 값이 있는 레코드의 위치를 미리 정렬해 둔 별도의 자료구조입니다. 조회할 때 테이블의 모든 행을 읽지 않습니다. 인덱스에서 위치를 먼저 찾고, 그 위치의 레코드만 읽습니다.

예를 들어 유저 ID가 1003인 레코드를 찾는다고 가정합니다.

  • 인덱스가 있으면: 인덱스가 "1003은 테이블의 57번 레코드"라는 정보를 줍니다. 57번 레코드만 읽으면 됩니다.
  • 인덱스가 없으면: 첫 행부터 마지막 행까지 읽으면서 1003을 찾아야 합니다. 이것을 풀 테이블 스캔이라고 부릅니다.

대신 인덱스를 만들면 INSERT(추가), UPDATE(수정), DELETE(삭제)를 할 때 인덱스도 같이 고쳐야 합니다. 읽기가 빨라지는 대신 쓰기에 비용이 붙습니다.

2. 인덱스는 어떤 자료구조로 만드나요?

B-Tree와 B+Tree는 무엇인가요?

가장 많이 쓰이는 구조입니다. 키(인덱스에 넣은 컬럼 값)를 정렬된 트리 모양으로 유지합니다. 트리는 노드(값을 담는 칸)를 부모와 자식 관계로 이은 구조입니다. 맨 위 노드를 루트, 자식이 없는 맨 아래 노드를 리프, 그 사이의 노드를 내부 노드라고 부릅니다.

  • 키가 정렬되어 있어서 같은 값을 찾는 일과 범위를 찾는 일에 모두 쓸 수 있습니다.
  • 루트에서 모든 리프까지의 거리가 같도록 균형을 유지합니다. 그래서 어떤 값을 찾든 걸리는 시간이 비슷합니다.
구조데이터 위치를 두는 곳특징
B-Tree내부 노드와 리프 노드 모두에 키와 데이터 위치를 둘 수 있습니다.찾는 키가 내부 노드에 있으면 리프까지 내려가지 않아도 됩니다.
B+Tree데이터 위치는 리프 노드에만 둡니다. 내부 노드는 키와 자식을 가리키는 포인터만 가집니다.리프 노드끼리 차례로 연결되어 있어 범위 검색이 빠릅니다.

MySQL의 InnoDB 엔진은 B+Tree를 씁니다. PostgreSQL의 B-Tree 인덱스도 행의 위치를 리프에만 두고 리프끼리 연결하는 구조입니다. 두 데이터베이스의 문서에서 "B-Tree 인덱스"라고 부르는 것은 이런 변형을 포함해 넓게 부르는 이름입니다.

Hash 인덱스는 무엇인가요?

해시는 값을 정해진 계산으로 숫자로 바꾸는 것입니다. Hash 인덱스는 이 숫자를 저장 위치로 씁니다. 그래서 같은 값을 찾는 일이 빠릅니다. 하지만 값의 크기 순서를 유지하지 않으므로 범위 검색에는 쓸 수 없습니다. MySQL에서는 주로 MEMORY 엔진에서 씁니다.

특수한 인덱스에는 무엇이 있나요?

인덱스쓰는 곳
Full-Text글 내용에서 단어를 찾는 검색에 씁니다.
R-Tree좌표와 영역을 다루는 공간 검색에 씁니다.
GiSTPostgreSQL의 범용 트리 구조입니다. 도형, 범위 타입 등에 씁니다.
GINPostgreSQL의 역색인 구조입니다. 배열이나 문서처럼 값 하나에 여러 요소가 들어 있는 데이터와 전문 검색에 씁니다.

3. 인덱스는 어떻게 동작하나요?

조회할 때는 어떻게 되나요?

CREATE INDEX idx_user_name ON user_table (name);
SELECT * FROM user_table WHERE name = 'Alice';

첫 줄은 user_table의 name 컬럼에 idx_user_name이라는 인덱스를 만듭니다. 둘째 줄은 이름이 'Alice'인 레코드를 찾습니다.

  1. 데이터베이스 엔진이 name 컬럼에 쓸 수 있는 인덱스가 있는지 확인합니다.
  2. 인덱스에서 'Alice'의 위치를 찾습니다.
  3. 그 위치의 레코드만 읽습니다.

테이블 전체를 읽는 풀 테이블 스캔을 하지 않습니다.

범위 검색은 어떻게 되나요?

SELECT * FROM score_table WHERE score BETWEEN 100 AND 300;

점수가 100 이상 300 이하인 레코드를 찾는 쿼리입니다. B+Tree는 리프 노드가 정렬된 순서로 이어져 있습니다. 그래서 100이 있는 위치를 찾은 뒤, 300까지 리프를 차례로 읽으면 됩니다. 테이블 전체를 읽지 않습니다.

쓸 때는 어떻게 되나요?

INSERT INTO user_table (name, score) VALUES ('Bob', 250);

테이블에 행이 하나 추가됩니다. 그러면 name 인덱스에 'Bob'과 그 행의 위치가 추가됩니다. score 컬럼에도 인덱스가 있다면 그 인덱스에 250과 그 행의 위치가 추가됩니다.

  • 인덱스가 여러 개면 그 수만큼 고칠 곳이 늘어납니다.
  • 트리의 균형을 유지하려고 노드를 나누거나 합치는 작업도 일어납니다.
  • 그만큼 CPU와 디스크 입출력을 더 씁니다.

4. 인덱스의 장점과 단점은 무엇인가요?

구분내용
장점조회 속도와 응답 시간이 좋아집니다. 조건 검색과 범위 검색이 빨라집니다.
단점INSERT, UPDATE, DELETE가 느려집니다. 인덱스를 저장할 디스크 공간이 더 필요합니다.

데이터베이스에서 인덱스와 실제 데이터는 항상 일치해야 합니다. 그래서 테이블이 바뀔 때마다 인덱스도 함께 고칩니다. 이 비용이 쓰기 성능을 떨어뜨립니다. 쓰기가 많은 테이블에는 인덱스를 적게 두고, 읽기가 많은 테이블에는 필요한 만큼 두는 것이 기본 원칙입니다.

5. 인덱스를 설계할 때 무엇을 봐야 하나요?

어떤 컬럼에 만드나요?

쿼리의 부분하는 일인덱스의 효과
WHERE조건에 맞는 행만 고릅니다.조건에 쓰이는 컬럼에 인덱스가 있으면 전체 스캔을 피합니다.
JOIN두 테이블을 기준 컬럼으로 연결합니다.기준 컬럼에 인덱스가 없으면 양쪽 테이블을 모두 읽어서 맞춰야 합니다.
GROUP BY, ORDER BY행을 묶거나 정렬합니다.인덱스가 이미 정렬되어 있으므로 추가 정렬을 줄일 수 있습니다.

그래서 WHERE, JOIN, GROUP BY, ORDER BY에 반복해서 나오는 컬럼부터 인덱스를 만듭니다.

선택도와 쓰기 부담은 무엇인가요?

선택도는 컬럼의 값이 얼마나 다양하게 나뉘는지를 뜻합니다.

  • 성별처럼 값이 두 가지뿐인 컬럼은 선택도가 낮습니다. 인덱스를 만들어도 읽어야 할 행이 전체의 절반 정도라서 효과가 작습니다.
  • 유저 ID처럼 값이 거의 겹치지 않는 컬럼은 선택도가 높습니다. 인덱스의 효과가 큽니다.

값이 매분 바뀌는 컬럼이라면 인덱스 수를 줄이거나 캐시를 함께 쓰는 방법을 검토합니다. 캐시는 자주 읽는 데이터를 빠른 저장소에 따로 보관해 두는 방법입니다.

실행 계획은 어떻게 확인하나요?

EXPLAIN SELECT * FROM user_table WHERE name = 'Alice';            -- MySQL, PostgreSQL
EXPLAIN ANALYZE SELECT * FROM user_table WHERE name = 'Alice';    -- 실제 실행 시간 포함
  • EXPLAIN: 데이터베이스가 쿼리를 어떤 순서로, 어떤 인덱스를 써서 처리할지 세운 계획을 보여 줍니다. 이 계획을 실행 계획이라고 부릅니다.
  • EXPLAIN ANALYZE: 쿼리를 실제로 실행하고 걸린 시간까지 보여 줍니다. PostgreSQL에서 쓸 수 있고, MySQL에서는 8.0.18 버전부터 쓸 수 있습니다.

인덱스를 만들었는데도 실행 계획에 풀 테이블 스캔이 나오면 다음을 확인합니다.

  • 복합 인덱스(컬럼 여러 개로 만든 인덱스)의 컬럼 순서가 쿼리의 조건과 맞는지 확인합니다.
  • 조건에서 컬럼에 함수나 형 변환을 적용하고 있는지 확인합니다.

인덱스를 만든 것과 인덱스가 실제로 쓰이는 것은 다른 문제입니다. 그래서 실행 계획을 직접 봐야 합니다.

6. 모바일 게임 서버에서는 왜 중요한가요?

  • 동시에 접속하는 사람이 많습니다. 로그인, 매치메이킹, 인벤토리 조회처럼 읽기 쿼리가 계속 들어옵니다.
  • 유저 프로필, 보유 아이템, 랭킹 점수는 짧은 간격으로 반복해서 조회됩니다.
  • 이벤트나 패치 직후에 접속이 몰릴 때 인덱스가 없으면 응답이 밀립니다.

인덱스는 이런 읽기 부하에서 병목을 줄이는 직접적인 수단입니다. 병목은 전체 처리 속도를 늦추는 가장 느린 구간입니다. 다만 아이템 획득처럼 쓰기가 잦은 부분은 인덱스를 늘리는 대신 다른 방법을 함께 검토해야 합니다.

7. 한 번에 정리하면 어떻게 되나요?

  • 인덱스는 컬럼 값과 레코드 위치를 정렬해 둔 별도의 구조입니다.
  • B+Tree가 가장 흔하고 범위 검색에 강합니다. Hash는 같은 값을 찾는 일에만 강합니다.
  • 읽기를 빠르게 하고 쓰기를 느리게 합니다. 디스크도 더 씁니다.
  • 설계할 때는 쿼리 패턴, 선택도, 쓰기 부담을 함께 보고, EXPLAIN으로 확인합니다.

자주 묻는 질문 (FAQ)

Q1. 인덱스를 많이 만들수록 좋은가요?

아닙니다. 조회는 빨라지지만 INSERT, UPDATE, DELETE를 할 때마다 관련된 인덱스를 모두 고쳐야 합니다. 그래서 쓰기가 느려지고 디스크도 더 씁니다. 실제 쿼리에서 쓰이는 인덱스만 남기는 것이 좋습니다.

Q2. B-Tree와 B+Tree는 무엇이 다른가요?

B-Tree는 내부 노드에도 데이터 위치를 둘 수 있습니다. B+Tree는 데이터 위치를 리프 노드에만 두고 리프끼리 연결합니다. 그래서 B+Tree가 범위 검색에 유리합니다. MySQL의 InnoDB 같은 데이터베이스 엔진이 B+Tree를 씁니다.

Q3. 인덱스를 만들었는데도 느린 이유는 무엇인가요?

대표적인 이유는 네 가지입니다.

  • 조건에서 컬럼에 함수나 형 변환을 적용해서 인덱스를 쓰지 못하는 경우
  • 복합 인덱스의 앞쪽 컬럼에 대한 조건이 빠진 경우
  • 선택도가 낮은 컬럼에 인덱스를 만든 경우
  • 읽어야 할 행이 전체의 상당 부분이라서 옵티마이저가 풀 테이블 스캔을 고르는 경우

옵티마이저는 쿼리를 처리할 방법을 고르는 데이터베이스의 부품입니다. 어느 경우인지는 EXPLAIN으로 실행 계획을 확인해야 알 수 있습니다.

수정 안내

이 글은 2026년 11월 21일에 다시 썼습니다. 이전 판의 "PostgreSQL은 B+Tree를 쓴다"는 문장은 "행의 위치를 리프에만 두고 리프끼리 연결하는 구조"로 고쳐 적었습니다. Hash 인덱스가 같은 값을 찾는 데 "가장 빠르다"는 표현은 근거를 확인할 수 없어 "빠르다"로 고쳤습니다. 풀 테이블 스캔이 나올 때 확인할 항목 중 "조건 순서"는 "복합 인덱스의 컬럼 순서"로 고쳤습니다. GiST와 GIN 설명을 PostgreSQL 문서에 맞게 나눠 적었고, MySQL의 EXPLAIN ANALYZE 지원 버전을 더했습니다.

참고 자료

같은 주제의 다른 글: [알고리즘] 최소 스패닝 트리(MST) 개념과 구현: 크루스칼 vs 프림 비교, [자료구조/C언어] 레드-블랙 트리(Red-Black Tree) 규칙·회전·삽입·삭제 정리, [알고리즘] 퀵 정렬(Quick Sort) 동작 원리와 시간 복잡도 분석: 피벗 선택과 분할 정복

728x90
728x90