younganswer
DatabaseSep 23, 2025

Index

#Database#Index#B-Tree#B+Tree#MySQL#MongoDB#Query Optimization
Index

인덱스



목차



인덱스의 필요성

데이터베이스에서 원하는 데이터를 찾기 위해서는 일반적으로 테이블의 모든 데이터를 순차적으로 비교하는 풀 테이블 스캔(Full Table Scan) 방식이 사용된다. 이 방식은 데이터의 양이 적을 때는 문제가 되지 않지만, 수백만, 수천만 건의 데이터가 저장된 테이블에서는 심각한 성능 저하를 유발한다.

인덱스(Index)​는 이러한 문제를 해결하기 위해 사용되는 자료구조이다. 책 뒤편의 '찾아보기'처럼, 특정 컬럼의 데이터와 해당 데이터의 물리적 위치를 미리 정렬하여 저장해 둔다.

  • 인덱스가 없을 때: 테이블 전체를 순차적으로 탐색 (Full Table Scan, 시간 복잡도: O(n))
  • 인덱스가 있을 때: 정렬된 인덱스 구조를 통해 빠르게 위치를 탐색 (시간 복잡도: O(log n))

결과적으로 인덱스를 사용하면 데이터 검색 속도를 획기적으로 향상시켜 데이터베이스의 전반적인 성능을 높일 수 있다.



B-Tree

인덱스는 일반적으로 B-Tree(Balanced Tree) 자료 구조를 기반으로 구현된다. B-Tree는 스스로 균형을 맞추는 트리 구조로, 데이터가 항상 정렬된 상태를 유지하여 검색, 삽입, 삭제 연산을 모두 효율적으로 수행할 수 있다.


대부분의 현대적인 데이터베이스(MySQL InnoDB 엔진 등)는 B-Tree를 개선한 B+Tree를 인덱스 자료 구조로 사용한다. B+Tree는 B-Tree와 달리 모든 데이터 포인터를 리프 노드(leaf node)에만 저장하고, 리프 노드끼리는 연결 리스트(Linked List) 구조로 서로 연결되어 있다. 이러한 특징 덕분에 특정 데이터를 찾는 단일 조회(point query)뿐만 아니라, 특정 범위의 데이터를 모두 조회하는 범위 검색(range scan) 성능이 매우 뛰어나다.


아래는 트리 구조를 활용한 검색 과정을 보여주는 예시이다.

B-Tree 구조 예시

예를 들어 E라는 id값을 가진 객체를 검색한다고 가정해보자. 인덱스가 없다면 A부터 순차적으로 탐색하여 5번의 비교 연산이 필요하다. 하지만, 인덱스가 설정되어 있다면, D와 L을 비교한 후, D의 오른쪽 서브트리로 이동하여 E를 찾을 수 있고, 단 2번의 비교 연산만으로 E를 찾을 수 있다. 이렇게 인덱스는 데이터베이스의 성능을 크게 향상시킨다.


인덱스가 효율적인 이유와 대수 확장성

인덱스가 효율적인 이유는 모든 요소에 접근할 수 있는 균형 잡힌 트리 구조와 트리 깊이의 대수 확장성 때문이다. 대수 확장성은 데이터의 양이 증가할 때, 트리의 높이가 로그 스케일로 노드 수에 비해 매우 완만하게 증가하는 특성을 의미한다. M개의 자식 노드를 가지는 B-Tree에서, N개의 요소를 저장할 때 트리의 높이 h는 다음과 같이 계산된다.

h=logM(N)h = log_M(N)

즉, 트리에 높이가 h라면, 최대 M^h개의 요소를 저장할 수 있다. 수백만 개의 데이터라 할지라도 트리의 높이는 단 몇 단계에 불과하여, 디스크 접근 횟수를 최소화하고 빠른 검색을 가능하게 한다.



인덱스를 만드는 방법

MySQL과 MongoDB에서 인덱스를 만드는 방법에 대해 알아보자.


MySQL

MySQL(InnoDB 엔진 기준)의 인덱스는 크게 클러스터형 인덱스와 세컨더리 인덱스로 나뉜다.


클러스터형 인덱스 (Clustered Index)

클러스터형 인덱스는 테이블의 데이터를 인덱스 키 순서대로 물리적으로 정렬하여 저장하는 방식이다. 따라서 테이블 당 하나만 존재할 수 있으며, 책의 내용 자체가 목차 순서대로 정렬된 것과 같다.

  • PRIMARY KEY가 지정되면 해당 컬럼이 클러스터형 인덱스가 된다.
  • PRIMARY KEY가 없다면, 첫 번째 UNIQUE NOT NULL 컬럼이 클러스터형 인덱스가 된다.
  • 둘 다 없다면, InnoDB가 내부적으로 숨겨진 클러스터형 인덱스를 생성한다.

단일 속성에 대한 인덱스를 생성할 때는 세컨더리 인덱스보다 클러스터형 인덱스를 사용하는 것이 더 효율적이다.

sql
CREATE TABLE table_name (
	id INT PRIMARY KEY,					-- 클러스터형 인덱스 (기본 키)
	name VARCHAR(100),					-- 일반 속성
	email VARCHAR(100) UNIQUE NOT NULL	-- 클러스터형 인덱스
);

세컨더리 인덱스 (Secondary Index)

세컨더리 인덱스는 클러스터형 인덱스 외에 추가로 생성하는 인덱스이다. 책 뒤의 '찾아보기'와 같이 별도의 인덱스 페이지를 만들어 관리한다. 세컨더리 인덱스는 테이블 당 여러 개를 생성할 수 있다. 세컨더리 인덱스는 인덱스 키와 함께 실제 데이터의 위치를 가리키는 포인터(InnoDB에서는 클러스터형 인덱스 키)를 저장한다.

sql
-- name 컬럼에 대한 세컨더리 인덱스 생성
CREATE INDEX idx_users_name ON users (name);

-- (email, name) 순서의 복합 세컨더리 인덱스 생성
CREATE INDEX idx_users_email_name ON users (email, name);

MongoDB

MongoDB는 문서를 생성할 때 고유한 ObjectId를 자동으로 생성하며, 이 필드에 기본적으로 인덱스가 생성된다.

추가적인 인덱스는 createIndex() 메서드를 사용하여 생성할 수 있다. 1은 오름차순, -1은 내림차순 정렬을 의미한다.

mongosh
// 단일 필드 인덱스 생성
db.users.createIndex( { name: 1 } );

// 복합 인덱스(Compound Index) 생성
db.users.createIndex( { email: 1, name: -1 } );


인덱스 최적화 기법

인덱스 최적화 기법은 데이터베이스마다 조금씩 다르지만 기본적인 원리는 똑같다. MongoDB를 예시로 알아보자.


1. 인덱스는 비용이다.

인덱스는 검색(SELECT) 속도를 크게 향상시키지만, 데이터의 입력(INSERT), 수정(UPDATE), 삭제(DELETE) 시에는 성능을 저하시키는 요인이 된다. 데이터가 변경될 때마다 인덱스 트리도 함께 정렬해야 하는 추가 비용이 발생하기 때문이다.

  • 읽기(SELECT) 비용: O(log n)
  • 쓰기(INSERT, UPDATE, DELETE) 비용: O(log n)의 추가 비용 발생

따라서 모든 컬럼에 인덱스를 생성하는 것은 비효율적이다. 조회 시 WHERE 절에 자주 사용되고, 데이터의 변경이 잦지 않은 컬럼에 인덱스를 생성하는 것이 좋다. 또한, 조회하려는 데이터의 양이 테이블의 상당 부분(일반적으로 15~20% 이상)을 차지하는 경우, 인덱스를 사용하는 것보다 테이블 전체를 스캔하는 것이 더 빠를 수도 있다.


2. 항상 테스트해야 한다.

인덱스 전략은 서비스의 데이터 분포와 주요 쿼리 패턴에 따라 달라진다. 따라서 인덱스를 생성한 후에는 반드시 쿼리 실행 계획(Query Execution Plan)을 확인하여 의도대로 동작하는지, 성능이 개선되었는지 검증해야 한다.


데이터베이스 옵티마이저는 실행 계획을 통해 어떤 인덱스를 사용하여 쿼리를 처리할지 결정한다.

  • MySQL: EXPLAIN 명령어를 사용한다.
    sql
    EXPLAIN SELECT * FROM users WHERE name = 'John Doe';
  • MongoDB: explain() 메서드를 사용한다.
    mongosh
    db.users.find({ name: 'John Doe' }).explain('executionStats');

3. 복합 인덱스는 '동등 비교', '정렬', '범위 비교' 순으로 생성한다.

여러 필드를 묶어 생성하는 복합 인덱스는 필드의 순서가 매우 중요하다. { a: 1, b: 1 }과 { b: 1, a: 1 }은 완전히 다른 인덱스이다.


효율적인 복합 인덱스를 위한 일반적인 규칙은 ESR(Equality, Sort, Range) 이다.

  1. Equality (동등 비교): = 또는 { $eq: ... } 와 같이 정확한 값으로 비교하는 필드를 가장 앞에 둔다.
  2. Sort (정렬): ORDER BY 또는 .sort() 에 사용되는 정렬 필드를 그다음에 둔다.
  3. Range (범위 비교): >, <, $in, BETWEEN 등 범위를 지정하는 필드를 마지막에 둔다.

예를 들어, 아래와 같이 email로 사용자를 찾고(Equality), 특정 age 범위(Range)를 조회한 뒤 name으로 정렬하는 (Sort) 쿼리가 있다고 가정해보자.

mongosh
// email(동등)로 찾고, age(범위)를 조회하고, name(정렬)으로 정렬
db.users.find({
	email: 'example@example.com',
	age: { $gt: 20 }
}).sort({ name: 1 });

이 쿼리를 위한 최적의 복합 인덱스는 아래와 같이 ESR 규칙에 따라 { email: 1, name: 1, age: 1 } 순서가 된다.

mongosh
db.users.createIndex({ email: 1, name: 1, age: 1 });

Share this post

N