Index는 왜 빠를까?

백엔드 개발자라면 Index가 DB 조회 성능에 좋다는 건 익히 들어봤을 것이다.

이 글을 통해 왜 빠른지, 내부 구조는 어떻게 되어있는지 살펴보자.

🚀 Index의 효과

index를 직접 써보며 그 효과부터 체감해보자.

준비

실험 환경은 다음과 같다.

하드웨어: Github Codespace (CPU 2개, RAM 8GB)
데이터베이스: MySQL 8.0.42
데이터: 부동산 테이블과 100만개의 레코드

아래와 같은 부동산 테이블을 준비했다.

CREATE TABLE real_estate_transaction (
    id BIGINT AUTO_INCREMENT PRIMARY KEY,             -- 거래 데이터 ID
    transaction_type VARCHAR(20) NOT NULL,            -- 거래방식 (예: 매매, 전세, 월세)
    price BIGINT NOT NULL,                            -- 가격 (만원 단위, 월세면 보증금 기준)
    area DECIMAL(10,2) NOT NULL,                      -- 면적 (㎡, 예: 84.25)
    approval_date DATE,                               -- 사용승인일 (준공일)
    household_count INT,                              -- 세대수
    address VARCHAR(255) NOT NULL,                    -- 지번/도로명 주소
    building_name VARCHAR(100),                       -- 건물명 또는 아파트 이름
    created_at DATETIME DEFAULT CURRENT_TIMESTAMP,    -- 생성일시
    updated_at DATETIME DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP -- 수정일시
);

이 테이블에 100만개의 아파트 데이터를 삽입했다.

데이터는 아래와 같이 삽입되어 있다.

Index 걸기 전의 성능

approval_date(승인일)를 기준으로 2024년에 승인된 아파트를 조회하면 아래와 같이 조회된다.

처음에는 1초가 걸렸고 이후로 0.4초 정도가 걸렸다.

참고로 처음에 유독 값이 튀는 이유는 'InnoDB Buffer Pool' 때문이다. 해당 테이블의 데이터를 메모리에 올리느라 처음에는 오래 걸렸던 것이다. 이는 처음에 buffer pool에 올릴 때만 그렇기에, 위 쿼리의 실행시간은 평균적으로 0.4초가 걸렸다고 하자.

이 쿼리의 실행계획을 보면 아래와 같다.

type이 ALL인 것을 보아 Full Table Scan임을 알 수 있다. 즉, 테이블의 전체 레코드를 스캔해야 한다는 것이다. 100만개의 테이블 전체를 스캔한다는 건 매우 비효율적이다.

이러한 비효율을 없애기 위해 Index를 추가해보자.

Index 걸고 나서의 성능

approval_date를 기준으로 인덱스를 만들어보자.

이전에 실행했던 쿼리를 다시 실행해보자.

0.4초에서 평균 0.22초 정도로 조회 성능이 향상되었다. 대략 50% 빨라진 셈이다.

해당 쿼리의 실행계획을 살펴보자.

type이 range인 것을 보아하니 인덱스를 통해 행을 스캔한다는 걸 알 수 있다.

🎯 인덱스는 왜 빠른 걸까?

인덱스가 빠른 이유는 효율적인 자료구조를 통해 데이터를 미리 정렬해두었기 때문이다.

미리 정렬해두면 구체적으로 얻게 되는 장점이 뭘까?

그건 직관적으로 생각해보면 답이 나온다.

서랍 속에서 작은 건전지를 찾으려 한다. 이때 서랍에 미리 물건의 크기나 용도 별로 미리 정리해두었다면, 찾기 쉬울 것이다. 반면에 서랍에 여러 물건이 어지럽혀져 있다면 찾는 데 시간이 걸릴 것이다.

DB에서도 마찬가지이다. 데이터가 정렬되어 있지 않다면 Disk에서 Random I/O를 통해 접근해야 하므로 시간이 걸리게 된다. 하지만, 인덱스를 통해 미리 정렬해둔 것을 기준으로 찾게 된다면 I/O 횟수가 줄어들기에 시간이 훨씬 단축된다.

인덱스란 추가적인 저장공간과 쓰기작업을 통해 조회 성능을 높이는 자료구조이다. 이 인덱스는 크게 두 가지로 나누어진다.

1. 영어사전을 보면 단어들이 알파벳 순서대로 정렬되어 있다. 그래서 그 두꺼운 책 속에서도 원하는 단어를 쉽고 빠르게 찾을 수 있다. 이러한 구조를 클러스터링 인덱스라고 한다.

2. 프로그래밍 개념서를 보다보면, 맨 마지막 페이지에 키워드들이 순서대로 정렬되어 각각의 키워드가 몇 페이지에 나오는지 표시해둔 게 있다. 이게 논클러스터링 인덱스이다. 그 키워드 자체를 책 본문에서 정렬한 건 아니지만, 별도의 페이지에서 정렬한 걸 의미한다.

🕵🏻‍♂️ 클러스터링 인덱스의 원리

인덱스가 빠른 이유와 개요에 대해서 간단히 알아봤다. 이제는 인덱스가 왜 빠른지 그 원리를 더욱 구체적으로 탐구해보자.

우선 아까 언급했던 첫 번째 인덱스, 즉 클러스터링 인덱스에 대해서 알아보자.

도대체 내부적으로 데이터를 어떻게 정렬하기에 이렇게 빠른 걸까?

우선 B+Tree를 알아야 한다.

클러스터링 인덱스 내부 구조를 살펴보기 전에 우선 B+Tree에 대해서 알아야 한다. 대부분의 DB에서 인덱스는 B+Tree 자료구조를 보편적으로 사용하기 때문이다.

B+Tree의 기본이 되는 B-Tree를 기준으로 우선 살펴보자.

일련의 숫자가 저장된 구조에서 28을 찾으려고 한다. 선형 탐색과 B-Tree의 성능 차이를 체감해보자.

선형 탐색에서는 28을 찾기 위해서 11번의 탐색이 필요하다. 즉, 시간복잡도는 O(N)이다.

반면에 B-Tree를 살펴보자.

단 4번의 탐색으로도 28을 찾을 수 있다. 즉, 시간복잡도는 O(logN)이다. 위 gif를 통해서 왜 B-Tree를 쓰는지 직관적으로 알 수 있다. 원하는 데이터를 찾기 위해서 탐색하는 스텝이 훨씬 더 단축된다.

B-Tree는 Balanced Tree의 약자로 스스로 균형을 잡는 확장 이진트리이다. 이는 인덱스에서 가장 일반적으로 사용되며, 가장 먼저 도입된 인덱싱 알고리즘이기도 한다.

특징으로는 모든 Leaf Node가 같은 높이를 가진다는 것이다. 새로운 데이터가 삽입될 때마다 스스로 트리 높이의 균형을 잡기 때문이다. Leaf Node는 맨 마지막 계층의 데이터를 의미한다.

그러면 B+Tree는 B-Tree에서 무엇이 달라졌을까? B-Tree에서는 각각의 node에 데이터를 저장하는 반면, B+Tree는 실제 데이터가 Leaf Node에만 저장된다. 아래 그림을 보면 쉽게 이해될 것이다.

이를 바탕으로 차이점을 간략히 정리해보자.

[ B-Tree와 B+Tree의 차이점 ]
B-Tree
- 모든 노드(내부 노드 포함)에 데이터 저장
- 범위 검색 시 트리를 여러 번 탐색해야 함

B+Tree
- 실제 데이터는 Leaf Node에만 저장
- Leaf Node들이 링크드 리스트로 연결 -> 범위 검색 최적화
- 내부 노드는 더 많은 키를 저장 가능 -> 트리 높이 감소
- MySQL InnoDB에서 사용

클러스터링 인덱스 특징

아래 예시를 통해 클러스터링 인덱스의 생김새부터 알아보자.

위 그림을 자세히 살펴보며 어떤 특징이 있는지 직접 분석해보자.

아래 참고사항을 읽어보며 분석해보자.

Root Node는 가장 첫 번째 Node를 의미한다.
Leaf Node는 맨 마지막 계층의 Node를 의미한다.
그 사이에 있는 노드들은 Branch Node라고 한다.
각 Node는 페이지(Page)이다. 페이지는 DB에서 데이터를 읽고 쓰는 가장 작은 단위이다.

직접 분석해봤는가? 특징을 뽑아내자면 이러하다.

1. 기본키를 중심으로 데이터들이 정렬되어 있다.

-> 범위를 조건으로 쿼리하기 유리하다.

2. Root Node와 Branch Node는 기본키와 페이지 주소만을 담아 Leaf Node로 향하는 길을 안내해주고 있다.

-> 원하지 않는 데이터를 빠르게 필터링하고 원하는 데이터가 있는 쪽으로 찾아갈 수 있다.

3. 실제 데이터는 Leaf Node에 저장되어 있다.

-> Root Node, Branch Node에는 기본키와 페이지 주소만 저장함으로써, 한 페이지에 더욱 많은 정보를 담을 수 있다.

이러한 특징이 조회 성능을 높이는 데 어떻게 도움이 되는지 알아보자. 아래와 같은 쿼리를 실행했을 때 탐색과정은 어떻게 될까?

SELECT * FROM real_estate_transactoin WHERE id >= 9 AND i <= 11;

'페이지1 -> 페이지2 -> 페이지6' 순서대로 탐색할 것이다. 이렇게 탐색하면 페이지를 단 3번 I/O하는 것만으로 원하는 데이터를 찾을 수 있다.

물론 이렇게 적은 데이터에서 3번을 I/O하는 건 비효율적으로 보일 수 있다. 하지만 아까처럼 100만 개가 넘는 데이터 속에서 인덱스는 그 효용이 매우 커진다. 그래서 참고로 데이터 수가 적을 때는 인덱스를 도입하는 게 오히려 비효율적일 수 있다는 점을 알아두자.

그리고 조회 성능은 트리의 깊이에 비례한다. 트리의 깊이가 깊을수록 I/O해야 하는 페이지가 많아진다. 그런데 B+Tree에서 하나의 노드는 여러 자식 노드를 가질 수 있으므로 데이터가 몇 억 개 존재해도 트리의 깊이는 3~6단계로 유지할 수 있다.

클러스터링 인덱스에 INSERT되는 과정

읽는 과정을 알아봤다면, 이번엔 쓰기 과정을 알아보자.

아까 봤던 예시에서 레코드를 하나 더 추가하면 아래와 같이 추가된다.

새로운 페이지를 만들고, 그곳에 새로운 데이터를 삽입한다.

위와 같이 1, 2, 3 ... 순차적으로 증가하는 순서의 인덱스에서는 페이지 그 자체를 거의 다 활용한다. 참고로 위 그림에서는 한 페이지를 다 꽉 채워서 사용하지만, MySQL InnoDB 기준으로 정확히는 15/16까지 한 페이지를 쓰게 된다.

반면에 순차적으로 삽입되는 게 아니라 랜덤하게 삽입되는 인덱스라면, 1/2 ~ 15/16까지 페이지를 활용한다. 새로운 레코드를 삽입하기 위해서, 새로운 페이지를 만들고 기존에 꽉 차 있던 인덱스 페이지에 있는 데이터의 절반을 새로운 페이지로 옮긴다. 그러고 나서 새로운 레코드를 삽입한다. 뒤에서 해당 경우를 다루니 향후 또 살펴보자.

클러스터링 인덱스 정리

클러스터링 인덱스란 인덱스 순서에 따라 실제 데이터를 정렬하여 저장하는 인덱스를 의미한다.

클러스터링(Clustering)이란 여러 개를 하나로 묶는 것을 의미한다. 즉, 테이블의 레코드를 비슷한 것들끼리 묶어서 정렬하여 저장한다는 의미이다. 이는 주로 비슷한 값들을 동시에 조회하는 경우가 많다는 점에서 착안한 것이다.

클러스터링 인덱스는 항상 프라이머리 키 값에 의해 물리적으로 정렬된다. 실제 데이터를 정렬해서 저장하는 것이다보니, 클러스터링 인덱스는 하나의 테이블에 하나만 존재한다.

이는 거창한 기법이 아니라, 테이블 저장 방식 중의 하나라고 볼 수 있다. 위 예시 그림에서도 봤듯이 별도의 인덱스 페이지를 만드는 느낌이 아니라, 원래의 데이터를 어떤 식으로 저장할 것인지에 대한 관점이다.

🔍 논클러스터링 인덱스의 원리

이번엔 두 번째 인덱스인 논클러스터링 인덱스의 원리에 대해 알아보자. 이는 세컨더리 인덱스라고도 한다.

논클러스터링 인덱스는 인덱스에 정렬된 키와 해당 데이터의 위치를 저장하고, 해당 인덱스를 원래의 데이터와는 별개로 저장하는 구조이다.

이것도 그림부터 살펴보자.

어떤 특징이 있는지 스스로 파악해보자.

1. Root Node와 Branch Node는 클러스터링 인덱스와 유사하다.

2. Leaf Node에 원래 데이터가 있지 않고, 원래 데이터를 가리키는 주소가 들어있다.

3. 원래의 데이터는 별도의 페이지에 저장되어 있고, 물리적으로 정렬되어 있지 않다.

하지만, MySQL InnoDB에서 논클러스터링 인덱스 자체로 쓰이는 경우는 잘 없다. 보통 클러스터링 인덱스가 혼합되어 사용된다.

클러스터링 + 논클러스터링 인덱스

이 또한 예시로 살펴보자.

원래의 데이터는 기본키를 기준으로 클러스터링 인덱스로 저장되어 있다. 여기에 approval_date를 기준으로 인덱스를 하나 더 만들었을 때, 위와 같은 구조로 인덱스가 생성된다.

아까 논클러스터링 인덱스 중 Leaf Node에서는 원래의 데이터 주소를 직접적으로 가리키고 있었다. 하지만, 여기에서는 기본키를 통해 원래의 데이터를 가리키고 있다.

이 구조에서 새로운 레코드가 추가되면 어떻게 동작할까?

아까 말했다시피 순차적으로 증가하는 기본키는 새로운 페이지를 만들고 새로운 레코드를 곧바로 저장한다.

반면에 approval_date와 같이 1, 2, 3 ... 순차적으로 증가하는 게 아닌 컬럼의 인덱스는 페이지를 절반으로 나누고 레코드를 삽입한다.

🔥 인덱스 실전 TIP

인덱스를 활용하는 실전 TIP을 다루려 한다. 퀴즈를 통해서 알아보자.

직접 풀어보고 그 이유까지 생각한 다음, 답을 살펴보자.

퀴즈

아래 퀴즈를 잘 풀기 위해서는 B+Tree를 잘 떠올리며 풀어야 한다.

1. JOIN, WHERE, ORDER BY에 자주 사용되는 컬럼에 인덱스를 걸어야 유리하다. (O/X)

2. INSERT, DELETE, UPDATE가 자주 일어나는 테이블에 인덱스를 걸어야 유리하다. (O/X)

3. 인덱스를 거는 키의 크기(size)는 커야 유리하다. (O/X)

4. 카디널리티가 낮은 컬럼에 인덱스를 거는 게 유리하다. (O/X)

- 카디널리티: 컬럼의 고유 값 개수를 의미하며, 컬럼에서 중복된 값이 여러 개 나오면 카디널리티가 낮다고 표현 (이름은 주민등록번호보다 카디널리티가 낮음)

5. 복합 인덱스를 걸 때, 카디널리티가 높은 순으로 거는 게 유리하다. (O/X)

- 복합 인덱스: 두 개 이상의 컬럼을 조합하여 만든 인덱스

6. address를 기준으로 한 인덱스가 있을 때, 아래 쿼리는 인덱스를 탈 수 있다. (O/X)

SELECT * FROM real_estate_transaction WHERE address like '%강서구%';

7. 테이블에 있는 모든 컬럼에 인덱스를 거는 게 바람직하다. (O/X)

8. 인덱스가 존재하는 데도 인덱스를 안 타는 게 더 유리한 경우에는 어떤 게 있을까?

정답

1. O / JOIN, WHERE, ORDER BY에 자주 사용되는 컬럼에 인덱스를 걸어야 유리하다.

-> 그래야 인덱스를 쓰는 의미가 있다.

2. X / INSERT, DELETE, UPDATE가 자주 일어나는 테이블에 인덱스를 걸면 불리하다.

-> 레코드 값에 변경이 일어나면 인덱스도 바꿔줘야 하기에 오버헤드가 생긴다. 이는 조회를 제외한 나머지 쿼리의 성능이 떨어지기에 인덱스를 신중하게 도입해야 하는 상황이다.

3. X / 인덱스를 거는 키의 크기(size)는 작아야 유리하다.

-> 키의 크기가 작아야 한 페이지에 많은 키를 담을 수 있다. 그래야 B+Tree의 높이가 낮아지고, 적은 I/O로도 원하는 레코드를 찾을 수 있다. 페이지는 디스크에서 데이터를 읽고 쓰는 기본 단위이며, 기본값은 16KB이다.

4. X, 카디널리티가 높은 컬럼에 인덱스를 걸어야 유리하다.

-> 컬럼의 데이터가 여러 번 중복되면 인덱스를 거는 효과가 떨어진다. 중복도가 높으면 인덱스를 통해 탐색해야 하는 범위를 좁혀주지 못하기 때문이다.

5. O / 복합 인덱스를 걸 때, 카디널리티가 높은 순으로 거는 게 유리하다.

-> 이것도 마찬가지로 탐색해야 하는 범위를 최대한 줄이기 위해서는 초반에 카디널리티가 높은 컬럼을 기준으로 해야 한다.

6. X / address를 기준으로 한 인덱스가 있을 때, 아래 쿼리는 인덱스를 탈 수 없다.

SELECT * FROM real_estate_transaction WHERE address like '%강서구%';

-> 인덱스는 값의 시작 부분부터 정렬되어 있기에 중간부분만 제시하면 인덱스를 활용하지 못한다.

7. X / 테이블에 있는 모든 컬럼에 인덱스를 거는 건 바람직하지 않다.

-> 2번 퀴즈와 같은 이유이다. 인덱스를 관리하는 데 비용이 커지기에 꼭 필요한 컬럼에만 인덱스를 걸어주는 게 좋다.

8. 인덱스가 존재하는 데도 인덱스를 안 타는 게 더 유리한 경우

-> 테이블에 데이터가 적은 경우, 테이블에 있는 대부분의 데이터를 조회하는 경우가 있다.

📍 마무리

요약

인덱스란 추가적인 저장공간과 쓰기작업을 통해 조회 성능을 높인 자료구조이다.
클러스터링 인덱스는 인덱스의 순서대로 실제 레코드를 물리적으로 정렬한 인덱스이다.
논클러스터링 인덱스는 실제 레코드와는 별개로 정렬한 인덱스이다.
대부분의 RDB에서 인덱스는 B+Tree 자료구조를 사용하며, 이는 I/O 횟수를 줄여주는 데 큰 몫을 한다.
인덱스는 추가적인 저장공간이 필요하고, 별도의 쓰기 작업이 필요하기에 잘못 활용하면 오히려 안 좋을 수 있다.

소감

이번에는 자료에 많은 신경을 쓰려고 했다. 텍스트를 많이 쓰기보다는 하나의 그림으로 효과적으로 전달하고자 했다. 또, 마지막에 인덱스 활용 TIP을 퀴즈로 담아낸 게 뿌듯하다. 그냥 나열하면 눈에 잘 안 들어올 것 같아서 퀴즈를 통해 조금 더 독자의 머리에 각인시키고 싶었다.

이번에는 개인 프로젝트에 시간을 많이 할애하느라 글쓰기에 많이 집중을 하진 못했다. 그래도 인덱스에 관해 글을 쓰면서 잘 몰랐던 부분을 더욱 정확하게 알 수 있는 기회가 되었다.

레퍼런스

Real MySQL(백은빈)
데이터 중심 애플리케이션 설계(마틴 클레프만)
https://blog.jcole.us/2014/10/02/visualizing-the-impact-of-ordered-vs-random-index-insertion-in-innodb/
https://dev.mysql.com/doc/refman/5.7/en/innodb-physical-structure.html
직접 했던 BCS 스터디

저작자표시 비영리 변경금지 (새창열림)

'Computer Science > Database' 카테고리의 다른 글

트랜잭션 제대로 알고 계신가요? (2)	2025.06.25