DB 인덱스가 조회를 빠르게 하는 이유

100만 권의 책과 색인의 마법

도서관에 무작위로 꽂혀 있는 100만 권의 장서 가운데 특정한 책 한 권을 찾아야 하는 상황을 떠올려 봅니다. 책들이 아무런 분류나 순서 없이 서가에 꽂혀 있다면, 사서는 첫 번째 서가의 첫 번째 책부터 시작해 원하는 제목이 나올 때까지 100만 권을 한 권 한 권 뽑아서 확인해야 합니다. 최악의 경우 100만 번의 확인 작업을 거쳐야만 책을 찾을 수 있습니다.

그런데 도서관 입구에 제목 순서대로 정렬된 검색 카드 서랍(색인)이 비치되어 있다면 상황은 완전히 달라집니다. '가'부터 '하'까지 자음 순으로 분류된 서랍 속에서 원하는 제목의 첫 글자를 찾고, 몇 번의 카드 넘김만으로 해당 책이 몇 번 서가 몇 번째 칸에 꽂혀 있는지 정확한 위치를 알아냅니다. 100만 권을 일일이 뒤지는 대신 단 3~4번의 카드 확인만으로 목표에 도달합니다.

데이터베이스 테이블에 100만 건의 사용자 데이터가 저장되어 있을 때도 동일한 원리가 작동합니다. 데이터베이스 엔진이 특정 이메일을 가진 사용자를 찾기 위해 100만 행 전체를 디스크에서 읽어 들이는 과정은 수 초 이상의 긴 지연 시간을 유발합니다. 반면 검색 열에 색인을 미리 만들어 두면 데이터베이스는 단 3~4회의 블록 읽기만으로 원하는 레코드를 1밀리초도 되지 않는 찰나에 찾아냅니다. 이 놀라운 성능 격차를 만들어내는 중심에 데이터베이스의 핵심 저장 구조인 인덱스가 자리 잡고 있습니다.

디스크 블록을 모두 훑는 전체 스캔의 한계

데이터베이스가 테이블에 새로운 데이터를 기록할 때, 레코드는 디스크 상의 데이터 페이지(Data Page 또는 Block)에 빈자리가 생기는 순서대로 적재됩니다. 사용자가 회원가입을 하거나 주문을 생성하는 순서는 이메일이나 이름의 가나다순과 무관하므로, 디스크에 기록된 실제 행들은 특정 열을 기준으로 정렬되어 있지 않습니다.

이 상태에서 WHERE email = 'user@example.com'과 같은 조건 검색 쿼리를 실행하면 데이터베이스 엔진은 선택의 여지 없이 테이블이 차지하는 모든 디스크 블록을 첫 페이지부터 끝 페이지까지 빠짐없이 읽어 들여야 합니다. 이를 전체 테이블 스캔(Full Table Scan)이라고 부릅니다.

시간 복잡도와 Big-O 읽기에서 살펴보았듯 전체 테이블 스캔의 시간 복잡도는 데이터 행 수 N에 정비례하는 O(N)입니다. 1만 건 수준의 작은 테이블에서는 전체 스캔이 일어나도 데이터가 운영체제의 버퍼 캐시에 머물러 체감 지연이 크지 않을 수 있습니다. 그러나 행 수가 수백만, 수천만 건으로 불어나면 수 기가바이트에 달하는 데이터를 디스크 저장 장치로부터 끊임없이 읽어 와야 하므로 극심한 디스크 입출력(I/O) 병목이 발생하고 데이터베이스 서버의 CPU 사용률이 치솟습니다.

이 문제를 해결하기 위해 특정 열의 값과 해당 행이 저장된 디스크 위치 포인터를 미리 정렬된 상태로 별도 보관해 두는 전용 자료구조를 만듭니다. 이를 인덱스(Index)라고 부릅니다.

B-트리가 O(log N) 탐색을 보장하는 구조

관계형 데이터베이스 시스템(PostgreSQL, MySQL, SQLite, Oracle 등)에서 가장 보편적으로 사용하는 기본 인덱스 알고리즘은 B-트리(B-tree)와 그 변형인 B+트리입니다. B-트리는 이진 탐색 트리와 달리 하나의 노드가 수십에서 수백 개의 자식 노드를 가질 수 있는 다분(Multi-way) 균형 탐색 트리입니다.

B-트리가 데이터베이스 엔진에서 탐색 경로를 어떻게 좁혀 내려가는지 계층 구조를 통해 확인합니다.

그림: B-트리 인덱스의 3단계 계층 구조와 목표 키 탐색 경로

다이어그램을 살펴보면 B-트리 인덱스는 크게 세 계층으로 구성됩니다.

1. 루트 노드(Root Node): 탐색이 시작되는 단 하나의 최상위 노드입니다. 키 값의 전체 범위를 하위 브랜치 노드로 분할하는 기준 키들을 품고 있습니다.
2. 중간 브랜치 노드(Branch Node): 루트와 리프 노드 사이에서 범위를 더욱 잘게 쪼개는 이정표 역할을 합니다. 조건에 맞는 특정 하위 노드로만 포인터를 연결하므로, 조건 범위를 벗어난 방대한 데이터 블록들을 단 한 번의 판정으로 탐색 대상에서 즉시 제외합니다.
3. 잎 노드(Leaf Node): 트리의 맨 아래에 위치하며, 실제 정렬된 인덱스 키 값과 원본 데이터 행을 가리키는 디스크 물리 주소 포인터(ROWID 또는 기본 키)가 저장되어 있습니다. 잎 노드들은 양방향 연결 리스트로 서로 엮여 있어, 단일 값 조회뿐 아니라 WHERE age BETWEEN 20 AND 30 같은 범위 검색에서도 추가 트리 탐색 없이 인접 노드를 차례로 훑을 수 있습니다.

B-트리의 가장 큰 강점은 트리의 모든 잎 노드가 항상 같은 깊이에 머물도록 스스로 균형을 맞춘다는 점입니다. 데이터가 1,000만 건에 달하더라도 한 노드가 수백 개의 갈래(Fan-out)를 품고 있기 때문에 트리의 높이는 34단계 수준에 불과합니다. 따라서 아무리 많은 행이 쌓여 있어도 단 34번의 디스크 페이지 접근만으로 원하는 위치를 정확히 짚어내는 O(log N)의 안정적인 성능을 보장합니다.

[참고] 클러스터형 인덱스와 보조 인덱스

테이블의 실제 데이터 행 자체가 인덱스 키 순서에 맞춰 물리적으로 정렬되어 저장되는 방식을 클러스터형 인덱스(Clustered Index)라고 부릅니다. 대다수 데이터베이스에서 테이블의 기본 키(Primary Key)가 이 역할을 맡으며, 테이블당 오직 하나만 존재할 수 있습니다. 반면 추가로 생성하는 보조 인덱스(Secondary Index)는 별도의 인덱스 페이지에 정렬 키와 클러스터형 키 포인터를 함께 보관합니다.

EXPLAIN QUERY PLAN으로 확인하는 인덱스 전환

데이터베이스가 질의를 처리할 때 실제로 인덱스를 사용하는지 아니면 전체 스캔을 수행하는지는 실행 계획(Execution Plan) 분석 명령을 통해 직접 검증할 수 있습니다.

Python에 내장된 sqlite3 모듈을 활용해 사용자 테이블을 생성하고, 인덱스를 만들기 전과 만든 후의 EXPLAIN QUERY PLAN 결과를 단계별로 비교해 봅니다.

import sqlite3
 
def run_index_demo():
    conn = sqlite3.connect(":memory:")
    cursor = conn.cursor()
 
    # 1. 회원 테이블 생성 및 샘플 행 삽입
    cursor.execute("CREATE TABLE users (id INTEGER PRIMARY KEY, email TEXT, name TEXT)")
    sample_users = [
        ("alice@example.com", "Alice"),
        ("bob@example.com", "Bob"),
        ("charlie@example.com", "Charlie"),
    ]
    cursor.executemany("INSERT INTO users (email, name) VALUES (?, ?)", sample_users)
    conn.commit()
 
    # 2. 인덱스 생성 전: 실행 계획 확인
    print("--- 인덱스 생성 전 실행 계획 ---")
    cursor.execute("EXPLAIN QUERY PLAN SELECT name FROM users WHERE email = 'alice@example.com'")
    for row in cursor.fetchall():
        # SQLite 쿼리 플랜 결과 튜플의 4번째 열(row[3])에 상세 실행 방식이 기록됨
        print(row[3])
 
    # 3. email 열에 B-트리 보조 인덱스 생성
    cursor.execute("CREATE INDEX idx_users_email ON users(email)")
    conn.commit()
 
    # 4. 인덱스 생성 후: 동일 쿼리의 실행 계획 재확인
    print("\n--- 인덱스 생성 후 실행 계획 ---")
    cursor.execute("EXPLAIN QUERY PLAN SELECT name FROM users WHERE email = 'alice@example.com'")
    for row in cursor.fetchall():
        print(row[3])
 
    conn.close()
 
run_index_demo()

위 코드를 실행하면 터미널 콘솔에 다음과 같은 형식의 실행 계획 분석 결과가 출력됩니다.

예시 출력:
--- 인덱스 생성 전 실행 계획 ---
SCAN users
 
--- 인덱스 생성 후 실행 계획 ---
SEARCH users USING INDEX idx_users_email (email=?)

출력 결과에서 명확한 차이가 드러납니다. 인덱스가 없던 초기 상태에서는 SCAN users가 출력되며 전체 테이블의 모든 행을 일일이 검사했습니다. 반면 CREATE INDEX 명령으로 email 열에 인덱스를 생성한 뒤에는 SEARCH users USING INDEX idx_users_email (email=?)로 전환되었습니다. B-트리 인덱스를 타고 내려가 일치하는 행만을 정확하게 집어내는 인덱스 탐색(Index Seek) 방식으로 최적화된 것입니다.

복합 인덱스와 좌측 접두사 규칙

실무 서비스에서는 단일 열뿐만 아니라 둘 이상의 열을 묶어서 조회하는 경우가 매우 흔합니다. 예를 들어 결제 내역 테이블에서 특정 고객(user_id)이 특정 결제 상태(status)로 결제한 건을 자주 찾는다면 두 열을 결합한 복합 인덱스(Composite Index)를 생성합니다.

복합 인덱스를 구성할 때는 열의 배치 순서가 성능을 전적으로 좌우합니다. 복합 인덱스는 선행 열을 기준으로 먼저 정렬되고, 선행 열의 값이 같을 때에 한해 후행 열을 기준으로 정렬되는 사전식 정렬 구조를 갖기 때문입니다.

전화번호부를 떠올리면 이해하기 쉽습니다. 전화번호부가 (성, 이름) 순서로 정렬되어 있다면 '김철수'를 찾기 위해 '김' 씨 영역을 먼저 찾은 뒤 그 안에서 '철수'를 빠르게 찾을 수 있습니다. 하지만 성을 모른 채 '이름이 철수인 사람'만을 찾으려 한다면 전화번호부의 모든 페이지를 처음부터 끝까지 넘겨야 합니다.

데이터베이스 엔진도 마찬가지로 복합 인덱스가 (user_id, status) 순서로 정의되어 있을 때, 조건절에 user_id가 포함되어야만 인덱스를 정상적으로 활용할 수 있습니다. WHERE status = 'PAID'처럼 후행 열만으로 질의를 던지면 인덱스의 정렬 구조를 탈 수 없어 전체 테이블 스캔으로 되돌아갑니다. 이를 좌측 접두사 규칙(Leftmost Prefix Rule)이라고 부릅니다. 따라서 카디널리티(고유값의 개수)가 높고 등가 조건(=)으로 자주 걸리는 열을 복합 인덱스의 앞자리에 배치해야 최대의 검색 효율을 얻을 수 있습니다.

인덱스가 침묵하는 순간과 쓰기 비용의 상충

인덱스를 만들어 두었다고 해서 모든 쿼리가 자동으로 빨라지는 것은 아닙니다. 작성한 SQL 문장이 인덱스의 정렬 특성을 깨뜨리면 옵티마이저는 인덱스를 외면하고 전체 테이블 스캔을 선택합니다.

• 인덱스 열을 가공하거나 함수를 씌우는 경우: WHERE SUBSTR(created_at, 1, 4) = '2026'이나 WHERE price * 0.9 > 10000처럼 열 자체를 연산식에 넣으면, 엔진은 인덱스에 저장된 원래 값을 바로 비교할 수 없어 전체 행을 계산해야 합니다. WHERE price > 10000 / 0.9처럼 대상 열을 순수하게 남겨두어야 합니다.
• 앞부분에 와일드카드를 붙인 문자열 검색: WHERE name LIKE '%길동'처럼 앞부분이 가려진 검색은 B-트리의 사전식 정렬을 탈 수 없습니다. 반면 뒷자리가 와일드카드인 WHERE name LIKE '홍%'는 인덱스 범위 검색을 완벽히 활용합니다.
• 데이터 타입의 불일치: 문자열 열에 숫자 리터럴을 대조하는 등 암시적 형변환이 일어날 때도 인덱스가 비활성화될 수 있습니다.

더 나아가 인덱스는 공짜가 아닙니다. 인덱스는 검색 성능을 끌어올리는 대신 쓰기 작업의 속도를 갉아먹는 트레이드오프를 수반합니다. 테이블에 새로운 행을 INSERT하거나 기존 키를 UPDATE, DELETE할 때마다 데이터베이스는 원본 테이블뿐 아니라 그 테이블에 걸려 있는 모든 인덱스 트리에도 변경을 반영하고 균형을 재조정(Node Split 및 Rebalance)해야 합니다.

트랜잭션으로 변경 묶기에서 다룬 대규모 배치 삽입 작업이 필요할 때는, 수많은 인덱스가 걸려 있을 경우 트랜잭션 완료 시간이 극적으로 지연됩니다. 더불어 인덱스 자체가 원본 테이블 크기에 버금가는 디스크 저장 공간을 차지하므로, 무분별하게 인덱스를 늘리기보다 실제 병목이 발생하는 핵심 조회 쿼리를 선별하여 최소한의 인덱스를 정교하게 설계해야 합니다.

이러한 관계형 데이터베이스의 정형 인덱스 원리는 최근 주목받는 인공지능 엔지니어링과도 밀접하게 연결됩니다. RAG와 벡터 검색에서 다루는 벡터 데이터베이스는 수백 차원의 실수 임베딩을 다루므로 등가나 대소 비교를 수행하는 B-트리 인덱스를 직접 적용할 수 없습니다. 대신 고차원 공간에서 가장 가까운 이웃 벡터들을 빠르게 근사 탐색(ANN)하기 위해 HNSW 같은 그래프 기반 색인 구조를 사용합니다. 데이터의 특성과 질의 목적에 알맞은 색인 구조를 선별하고 관리하는 원리는 전통적인 관계형 데이터베이스의 B-트리부터 지능형 검색 시스템의 고차원 벡터 인덱스에 이르기까지 고성능 소프트웨어를 떠받치는 변함없는 핵심 설계 역량입니다.

참고 문서

• SQLite 공식 문서 — EXPLAIN QUERY PLAN
• PostgreSQL 공식 문서 — B-Tree Indexes
• MySQL 공식 문서 — How MySQL Uses Indexes
• Garcia-Molina et al. — Database Systems: The Complete Book (2nd Edition, Chapter 14. Index Structures)