인덱스(Index)의 개념 및 동작 원리와 설계 시 고려 조건

zayn_noh·2026년 6월 9일

DB(DataBase)

목록 보기

1/3

데이터베이스 성능을 이야기할 때 가장 자주 등장하는 개념 중 하나가 인덱스(Index) 이다.

인덱스를 사용하면 조회 성능을 크게 개선할 수 있지만,
단순히 “자주 조회하는 컬럼에 인덱스를 걸면 된다” 정도로 이해하고 사용하면
오히려 기대한 효과를 얻지 못하거나 불필요한 오버헤드만 늘어날 수 있다.

인덱스는 결국 데이터를 빠르게 찾기 위한 자료구조이기에

어떤 구조로 동작하며,
어떤 컬럼에 만들어야 효과적인지,
여러 컬럼을 묶을 때는 어떤 순서로 설계해야 하는지를 함께 이해해야 한다.

이번 포스트에서는 인덱스를 단순히 “조회 성능을 높이는 기능”으로만 보지 않고,
인덱스를 왜 사용하는지와 어떤 기준으로 설계해야 하는지를 목표로 정리해보려 한다.

1. 인덱스(Index)의 자료구조

1-1) 이진 탐색 트리(Binary Search Tree)

인덱스는 트리 구조를 가진다. 인덱스에서 실제로 사용하는 트리 구조를 알아보기 전에
먼저 이진 탐색 트리(Binary Search Tree)에 대해 알아보면

이진 탐색 트리는 각 노드가 최대 두 개의 노드를 가지며, 값의 크기 관계에 따라 데이터를 배치한다.

트리 내 어떤 노드냐에 상관없이 모두 다음과 같은 규칙 하에 구조를 이룬다.

왼쪽 서브트리의 모든 값 < 현재 노드의 값 < 오른쪽 서브 트리의 모든 값

이진 탐색 트리에서 값을 찾을 때는 다음과 같은 과정을 거친다. (상단 이미지 기준)

자료구조에서 7을 찾고자 한다 가정
루트노드의 값(8)과 찾고자 하는 값(7)을 비교한다.
찾고자 하는 값(8)이 루트 노드의 값(7)보다 작기에 좌측 노드로 이동한다.
이동한 노드의 값(3)과 찾고자 하는 값(7)을 비교한다.
찾고자 하는 값(7)이 위치한 노드의 값(3)보다 크기에 우측 노드로 이동한다.
찾고자 하는 값(7)과 해당 노드의 값(6)을 비교한다.
찾고자 하는 값(7)이 해당 노드의 값(6)보다 크기에 우측 노드로 이동한다.
찾고자 하는 값(7)과 해당 노드의 값(7)을 비교한다.
일치하기에 해당 값을 반환한다.

예시로 든 그래프가 값이 삽입될 당시 다음과 같은 순서로 삽입되었다 가정해보면

8 -> 3 -> 10 -> 1 -> 6 -> 14 -> 4 -> 7 -> 13

배열로 동일 삽입 내용을 관리한다 하였을 때, 원하는 값 7을 탐색하기 위해
8, 3, 10, 1, 6, 14, 4, 7을 모두 확인하며 비교해야 했을 것이다.

이진 탐색 트리 구조는 배열과 비교하였을 때 월등한 탐색적 성능 효과를 가지는 것을 알 수 있다.

그러나 이러한 이진 탐색이 언제나 시간복잡도적으로 이점을 가지는 것은 아니다.
만약 이진 탐색 트리에 다음과 같은 순서로 값을 삽입한다고 가정해보자

1 -> 3 -> 4 -> 6 -> 7 -> 8 -> 10 -> 13 -> 14

결과적으로 트리 내 모든 노드는 오른쪽에 위치하여, 구조상 편향된 트리가 만들어진다.
여기서 14라는 값을 탐색해야 한다면,
사실상 모든 노드를 조회(Full Scan)해야하기에 O(N)의 시간복잡도가 나온다.

사실상 배열을 전체 순회하는 것과 다를 바 없는 탐색 시 성능적 문제를 야기한다.

이러한 문제를 해결할 수 있는
AVL Tree, Red-Black Tree같은 자가 균형 이진 탐색 트리가 존재한다.
다만 데이터베이스의 인덱스에서는 일반적으로 B-Tree/B+Tree 계열 구조를 사용한다.

데이터베이의 대용량 데이터는 메모리(RAM)가 아닌 HDD, SSD와 같은 하드 디스크에 저장되며,
해당 환경에서는 비교 횟수보다 디스크 I/O 횟수를 줄이는 것이 더 중요하기 때문이다.

1-2) B-Tree

앞서 살펴본 이진 탐색 트리와 이를 개선한 AVL Tree, Red-Black Tree는
각 노드가 최대 두 개의 자식 노드 포인터와 하나의 키 값만을 가지는 자료구조이다.

그렇기에 데이터가 많아지면 결국 트리의 height가 높아질 수 밖에 없고
이는 값을 탐색할 때 거쳐야하는 노드가 많아짐을 의미하는데, 디스크에 저장되는 데이터베이스에서는
이러한 탐색 시 값을 비교하는 연산보다 디스크 I/O 과정이 훨씬 큰 비용을 차지한다.

이에 데이터베이스와 파일 시스템에서
대량의 데이터를 효율적으로 검색하기 위해 설계된 트리 자료구조인 B-Tree가 등장한다.

하나의 노드에 데이터(키)를 하나만 담지 않고 여러 개 저장한다.
여러 키가 담기기에 해당 키들을 기준으로 더욱 많은 분기점이 발생하여 다수의 자식 노드를 가진다.

결과적으로 개별 노드당 담고 있는 키도 많아지고, 자식 노드의 수도 늘어나기에
루트에서 리프노드까지 거쳐야하는 노드 수가 줄어들게 된다. 즉, 디스크 I/O가 줄어드는 것이다.

B-Tree는 DB 인덱스와 파일 시스템에 최적화되어 있을까?

결론을 먼저 말하자면, B-Tree는 DB 인덱스와 파일 시스템에서 사용하기에
다음과 같은 아쉬움이 남아있다.

1. 중간 노드에 실제 데이터 저장
B-Tree는 중간 노드와 리프 노드 모두에 실제 데이터가 포함되어 있는데,
이는 한 노드에서 나타낼 수 있는 분기점이 줄어들게 되는 것이며
트리의 height를 더 낮출 수 있는 기회를 잃게 되는 것이다.

2. 범위 검색에 취약
DB에서 데이터를 검색할 때는, 특정 하나의 데이터뿐만 아니라 범위를 검색하는 경우가 많다.
WHERE age BETWEEN 20 AND 30
ORDER BY created_at
앞서 말했지만 B-Tree는 중간 노드에도 실제 데이터가 들어있을 수 있기에
리프노드뿐만 아니라 내부노드까지 오가며 범위에 포함되는 값을 탐색해 디스크 I/O가 추가로 발생한다.

1-3) B+Tree

B+Tree는 MySQL의 InnoDB 스토리지 엔진에서 인덱스를 관리하기 위해 사용하는 대표적인 자료구조이다.

앞선 B-Tree를 DB 인덱스에 사용할 때 문제점들은 B+Tree의 특징으로 보완할 수 있다.

B+Tree 특징

1. 모든 데이터가 리프 노드에만 저장된다.
B-Tree는 중간 노드에도 실제 값(데이터)이 저장될 수 있었는데,
B+Tree는 중간 노드에 오직 자식 노드를 찾아가기 위한 경로 정보(키값)만 들어가고
실제 다루는 데이터는 리프 노드에만 저장된다.
" 트리 높이 감소 -> 디스크 I/O 감소 "

2. 리프 노드들이 Linked List 구조를 가진다.
B-Tree의 경우 범위 검색(Range Scan)에 취약함을 앞선 내용에서 짚고 넘어갔다.
B+Tree는 모든 실제 데이터가 최하단 리프 노드에 저장되기에
한 리프노드 내부 데이터의 범위 탐색이 끝났다면, 다음 리프노드의 포인터를 따라가면 된다.
" 범위 검색 시 노드 이동 수 감소 -> 디스크 I/O 감소 "

2. Clustered / Non Clustered

2-1) 특징을 통한 개념 이해

인덱스(Index)의 종류는 크게 Clustered Index와 Non Clustered Index로 나눌 수 있다.

각각의 정의를 살펴보기보단 특징을 기반으로 각 개념을 이해하여 보겠다.

클러스터형 인덱스(Clustered Index)의 특징

단일성
한 테이블에는 오직 하나의 클러스터형 인덱스만 존재한다.
클러스터형 인덱스는 테이블의 물리적 구조를 결정하기 때문이다.

물리적 정렬
클러스터형 인덱스는 테이블의 레코드를 인덱스가 정의한 순서대로 재정렬한다.

자동 생성
일반적으로 테이블의 기본 키(Primary Key)를 설정하면 해당 키에 대해서
클러스터형 인덱스가 자동으로 생성된다.
PK가 없다면 직접 클러스터형 인덱스를 지정할 수 있다.

인덱스 구조
클러스터형 인덱스는 별도의 인덱스 테이블을 만들지 않고,
실제 데이터 테이블 자체를 인덱스로 사용한다.
이는 데이터 조회 시 인덱스 테이블과 데이터 테이블 사이의 별도 이동 없이 바로 접근이 가능하다.

쉽게 생각해 클러스터형 인덱스는 우리가 사용하는 데이터베이스 내 테이블의 Primary Key라 할 수 있다.

비클러스터형 인덱스(Non Clustered Index)의 특징

다중성
하나의 테이블에 여러 개의 비클러스터형 인덱스가 존재 가능하다.
서로 다른 검색 조건, 쿼리에 최적화된 다양한 인덱스를 생성할 수 있다.

논리적 정렬
비클러스터형 인덱스는 데이터를 물리적으로 재정렬하지 않는다.
인덱스 키 값이 정렬되어 있는 별도의 인덱스 페이지를 생성하며, 원본 데이터를 가리키게 한다.

공간 요구
비클러스터형 인덱스는 인덱스 페이지를 생성하기에, 별도의 저장공간을 차지한다.
때문에 인덱스를 많이 만들면 만들 수록, 더 많은 디스크 공간을 차지하게 된다.

역시 쉽게 생각하면 비클러스터형은 PK가 아닌 개발자가 직접 쿼리를 통해 설정하는 인덱스라 할 수 있다.

결국 클러스터형 인덱스는 PK가 실제 테이블의 데이터 탐색 기준이되는 것이기에,
우리가 관심 깊게 봐야하는 것은 비클러스터형 인덱스(Non Clustered Index)일 것이다.

2-2) Non Clustered Index의 장단점

장점) 데이터 입력, 수정, 삭제

클러스터형 인덱스의 경우 데이터를 입력하거나 수정, 삭제한다면
물리적 정렬되어 있는 특성상, 데이터 자체를 재정렬해야할 수 있는 어쩔 수 없는 손실을 지닌다.

하지만 비클러스터형 인덱스에서는 별도의 인덱스 페이지만 갱신하면 되기에,
상대적으로 입력, 수정, 삭제 작업에서 이점이 있다. (논리적 정렬되어 있기에)

단점) 인덱스 페이지의 존재

비클러스터형 인덱스는 인덱스 페이지에서 실제 데이터를 가리키는 포인터로 작동하기에
바로 실제 테이블에서 PK를 통해 값에 접근하는 것이 아니라,
인덱스를 탐색하고 데이터를 탐색하는 두 단계를 거치게 된다.

또한 결국 인덱스 페이지가 디스크의 저장 공간을 차지하기에 공간적 손해를 보게 된다.

커버링 인덱스(Covering Index)

커버링 인덱스는 쿼리를 처리하는 데 필요한 컬럼들이 모두 인덱스에 포함되어 있어,
테이블의 실제 데이터 row까지 접근하지 않고 인덱스만으로 결과를 반환하는 것을 말한다.
= key lookup 과정의 생략

이러한 커버링 인덱스는 비클러스터형 인덱스에서의 단점을 보완할 수 있다.
+) 자주 사용하는 쿼리인 경우 분석하여 커버링 인덱스를 의도적으로 설계하는 경우도 있다.

3. 인덱스(Index)의 필요성

인덱스의 간단한 필요 이유는 데이터베이스에서 원하는 데이터를 빠르게 찾기 위해 사용된다 할 수 있다.

즉, 적절한 인덱스가 있다면 데이터베이스는 전체 데이터를 모두 확인(풀스캔(Full Scan))하지 않고
인덱스를 통해 조건에 맞는 데이터의 위치를 빠르게 찾을 수 있는 것이다.

// 예시
// 1억건의 주문 데이터를 담은 order 테이블이 존재
// 특정 사용자 주문 내역을 조회하는 쿼리가 있다 가정

SELECT * FROM orders WHERE user_id = 123;

// 이때 만약에 user_id 컬럼에 인덱스가 없다면,
// 데이터베이스는 1억건의 주문 데이터를 모두 다 확인하면서 user_id가 123인 주문을 찾아야한다.

// user_id가 비클러스터형 인덱스로 지정되어 있다면,
// 데이터베이스는 자료구조(인덱스 페이지)를 통해 user_id가 123인 데이터가
// 어디에 저장되어 있는지, 디스크IO 몇 번으로 찾을 수 있는 것이다.

ex) orders
id | user_id | product | price
---|---------|---------|------
1  | 123     | A       | 10000
2  | 456     | B       | 20000
3  | 123     | C       | 15000
4  | 789     | D       | 30000
5  | 123     | E       | 12000

ex) idx_orders_user_id (인덱스 테이블)
user_id | PK(id)
--------|-------
123     | 1
123     | 3
123     | 5
456     | 2
789     | 4
// 인덱스 테이블은 user_id(인덱스) 기준으로 정렬되어 있기에, 풀스캔을 피할 수 있는 것

4. 인덱스(Index)는 항상 이점인가

인덱스는 조회 성능을 개선하는 데 효과적이지만, 모든 상황에서 항상 이점을 주는 것은 아니다.
먼저 인덱스는 테이블과 별도로 관리되는 자료구조이기 때문에 추가적인 저장공간이 필요하며

데이터가 변경될 때마다 인덱스도 함께 갱신되어야 한다는 점에서 오버헤드가 발생한다.

INSERT, UPDATE, DELETE 작업이 발생하면,
테이블 데이터뿐만 아니라 관련 인덱스 페이지들도 수정해야 한다.
따라서 인덱스가 많을 수록 쓰기 작업의 비용은 증가된다.

-> 조회가 많이 없고, 쓰기 작업이 자주 일어난다면 인덱스를 최소화하거나 쓰지 않는게 나을 수 있다.

또한 조회 조건의 선택도가 낮거나, 테이블 대부분의 데이터를 읽어야한다면,
인덱스 타면서 테이블 옮겨다니는 오버헤드보다 풀스캔이 나은 경우도 있다.

실제로 DB의 옵티마이저(Optimizer)가 이를 자동으로 판단해,
풀 테이블 스캔이 더 효율적이라고 판단하면 해당 인덱스를 사용하지 않을 수 있다.

따라서 인덱스를 사용할 때는 조회 성능 개선 효과와 함께,
저장 공간, 쓰기 성능 저하, 인덱스 갱신 비용 같은 오버헤드를 함께 고려해야 한다.

인덱스로 인한 이점이 이러한 비용보다 큰 경우에만 적절한 인덱스 설계라고 할 수 있다.

5. 인덱스(Index) 설계

컬럼의 카디널리티(Cardinality)와 셀렉티비티(Selectivity)는, 인덱스 설계의 기준이라 할 수 있다.

카디널리티(Cardinality) : 컬럼에 저장된 값의 고유성, 해당 컬럼 내 중복값이 얼마나 적은가

주민등록번호, e-mail, 주문번호 etc.

카디널리티는 값이 거의 중복되지 않은 컬럼의 경우 카디널리티가 높다고 표현할 수 있으며,
값의 종류가 적고 중복이 많은 컬럼의 경우에는 카디널리티가 낮다 표현한다.

셀렉티비티(Selectivity) : 특정 조건으로 값을 얼마나 걸러낼 수 있는지
```
	성별, 회원 상태, 게시글 공개 여부 etc.
```

Selectivity의 경우 다음 수식을 통해 파악할 수 있다.

Selectivity = Cardinality / 전체 row 수 Selectivity의 값이 1에 가까울 수록, "선택도가 좋다"

인덱스는 결국 조회 대상 데이터를 줄여주는 역할을 해야 의미를 가진다.
따라서 인덱스를 설계할 때는 해당 컬럼의 카디널리티와 셀렉티비티를 함께 고려해야 한다.
중복 값이 적고 조건에 맞는 데이터를 많이 걸러낼 수 있는 컬럼일수록,
인덱스를 사용했을 때 조회 범위를 효과적으로 줄일 수 있다.

카디널리티가 낮으면 항상 인덱스의 의미가 없는가?

카디널리티가 낮다고 해서 항상 인덱스의 의미가 없는 것은 아니다.
다른 컬럼과 함께 복합 인덱스로 구성되거나,
특정 값의 분포가 매우 치우쳐 있는 경우에는 낮은 카디널리티의 컬럼도 인덱스 설계에 포함될 수 있다.

6. 복합 인덱스(Composite Index)

복합 인덱스(Composite Index)는 두 개 이상의 컬럼을 묶어서 만든 인덱스이다.

CREATE INDEX idx_location_first ON users(Location, Name, ID);
CREATE INDEX idx_id_first ON users(ID, Name, Location);

위와 같이 복합 인덱스를 만들 수 있으며, 복합 인덱스를 사용할 때는

컬럼의 순서가 인덱스의 성능을 결정한다는 점을 주의해서 설계해야 한다.

B+Tree 구조를 가지는 인덱스의 특성상 위 예시에서는, Location -> Name -> ID순으로 정렬이 일어난다.

따라서 WHERE Location = '서울' AND Name = 'Lamine' 같은 경우는 문제 없지만

WHERE Name = 'Kylian'같은 경우, 첫 정렬 조건인 Location을 명시하지 않아 풀스캔의 가능성이 크다.

+ 복합 인덱스의 설계 방식

복합 인덱스는 보통 동등 조건(=)에 사용되는 컬럼을 앞에 두고,

그다음 범위 조건(>, <, BETWEEN, LIKE 'prefix%')이나,
정렬 조건(ORDER BY)에 사용되는 컬럼을 배치하는 방식으로 설계한다.
WHERE user_id = 10 AND created ≥ ‘2026-06-01’
	ORDER BY created_at DESC, id DESC LIMIT 20
위와 같은 특정 유저의 최근 주문 목록을 가져오는 쿼리가 있다 하였을 때

(user_id, created_at, id) 순서로 복합 인덱스를 설정했었다면
user_id = 10을 통해 특정 유저의 주문만으로 데이터 탐색 범위를 제한하고,
이후 범위 조건을 타며 정렬과 리미트까지 효율적으로 이어질 가능성이 있다.

반면 (created_at, user_id, id) 순서로 복합 인덱스를 설정했다면
created_at 범위 기준으로 첫 정렬된 데이터들 중 몇 개를 뽑아내고,
기준에 맞는 user_id를 흩뿌려진 데이터들 사이에서 찾아내야 한다.
결과적으로 인덱스를 사용함으로 얻는 효과적인 탐색을 누리지 못하는 것이다.

"복합 인덱스는 자주 쓰는 컬럼을 다 넣는게 아니라, 실제 쿼리 순서를 보고 결정할 것"

zayn_noh

개발 및 IT기술에 대해 정리하고 기록합니다.

다음 포스트