데이터베이스 2편 - 인덱스 구조 속 거래의 양면

Published: May 20, 2026

어느 핀테크 팀의 새벽 3시. 결제 시스템이 멈췄다. 금요일 저녁에 배포된 새 기능 하나가 문제였다. 인덱스가 빠진 컬럼으로 매 결제마다 240만 행 테이블을 풀스캔하고 있었다. 쿼리 하나당 8초. 48분 동안 장애가 이어졌고, 매출 4만 7천 달러가 사라졌다. 인덱스 한 줄이면 막을 수 있던 일이었다.

다른 팀, 다른 시스템. 이번엔 그 반대였다. 119개 컬렉션에 인덱스 955개. 컬렉션당 평균 14개. 읽기는 빨랐다. 그런데 어느 시점부터 쓰기 큐가 쌓이기 시작했다. Replication lag이 누적되고, 디스크 레이턴시가 999ms까지 치솟았다. 한 행을 INSERT할 때마다 14개의 인덱스 트리가 함께 갱신되고 있었던 것이다.

데이터베이스가 같은 곳에서 두 번 무너졌다. 한 번은 인덱스가 없어서. 한 번은 인덱스가 너무 많아서.

1편의 다음편 예고에서 디스크 접근 횟수 자체를 줄이는 물리적 방법이 인덱스라고 했다.

인덱스는 공짜가 아니다. 인덱스는 읽기를 빠르게 만드는 대신 쓰기에 세금을 매긴다. 데이터베이스의 모든 인덱스 결정은 결국 한 줄로 귀결된다.

인덱스는 읽기를 위해 쓰기를 판다.

Reference: Production Incident Story (2026)
Reference: MongoDB Community: Performance Impact of 955 Indexes

풀스캔의 비용과 읽지 않을 권리

인덱스가 없는 검색은 모든 오답을 일일이 배제하는 과정이다. 1,000만 건의 데이터 중 정답 하나를 찾기 위해 나머지 999만여 건을 전부 확인해야 한다. 정답을 찾는 비용이 아니라 오답을 걷어내는 비용, 이것이 풀스캔의 본질이다.

인덱스의 핵심은 필요한 데이터만 읽는 것이 아니라, 필요 없는 데이터를 최대한 읽지 않게 만드는 데 있다. 책 뒤의 색인처럼, 무수한 데이터를 처음부터 검토 대상에서 제외하는 정교한 장치다.

하지만 여기에는 보이지 않는 대가가 있다. 데이터가 변경될 때마다 인덱스도 함께 업데이트되어야 한다. 풀스캔을 피하는 대신, 데이터를 추가하거나 수정할 때마다 인덱스 갱신이라는 추가 비용을 치르는 셈이다.

이제 인덱스가 어떤 방식으로 읽기 성능을 올리고, 또 그 대가로 어떤 숨은 비용을 치르는지 하부 구조를 들여다보자.

환경이라는 변수

인덱스가 풀어야 할 trade-off는 단순하다. 바로 빠른 탐색과 효율적인 삽입이다. 자료구조의 역사는 이 두 가치 사이에서 어떤 타협점을 찾을 것인가에 대한 기록과 같다.

그러나 이 trade-off의 정답은 자료구조 자체에 있지 않다. 그것이 작동하는 환경의 비용 구조가 정답을 결정한다.

메모리와 디스크는 비용을 계산하는 방식이 완전히 다르다.

• 메모리에서는 CPU 연산이 비싸다.
• 디스크에서는 I/O 접근이 비싸다.

메모리에서는 키를 얼마나 적게 비교하느냐가 중요했고, 디스크에서는 페이지를 몇 번 덜 읽느냐가 더 중요했다.

같은 자료구조라도, 무엇을 비용으로 계산하느냐에 따라 최적의 선택은 달라진다.

메모리 환경의 참가자들

메모리 환경의 목표는 분명했다. 메모리에서는 데이터를 가져오는 비용이 거의 없다. 디스크처럼 페이지를 통째로 옮기는 무거운 이동이 필요 없기 때문이다. 이동 비용이 사라지면 남는 병목은 하나뿐이다. 데이터를 비교하고 재배치하는 연산 비용이다.

결국 메모리 환경의 관건은 삽입과 조회 사이의 비용 배분이었다.

데이터를 넣을 때 트리의 균형을 엄격하게 맞춰두면 나중에 찾을 때 빠르지만, 매 삽입마다 재정렬 비용을 치러야 한다. 반대로 균형 유지 기준을 낮추면 넣는 건 빠르지만, 찾을 때 더 많은 비교를 감수해야 한다.

자료구조들은 이 두 조건 사이에서 서로 다른 타협점을 선택했다.

참가자 계보

우선 아래의 표를 한 번 보자.

자료구조	얻은 것	잃은 것	저장위치	실행 환경
이진 탐색 트리	빠른 탐색	균형 보장	메모리	(없음 — 인덱스로 부적합)
AVL	엄격한 균형	무거운 쓰기 비용	메모리	(실무에서 거의 안 쓰임)
Red-Black	쓰기 비용 회복	완벽한 균형	메모리	Linux 커널, Java TreeMap, std::map
B+Tree	디스크 접근 최소화	메모리 내 연산 효율	디스크	DB 인덱스, 파일 시스템

이진 탐색 트리 — 빠른 탐색, 깨진 균형

가장 먼저 등장한 답은 이진 탐색 트리였다. 균형이 잡혀 있다면 탐색은 빨랐다. 문제는 균형이라는 전제가 운에 달려 있었다는 점이다.

데이터가 정렬된 순서로 들어오면 트리는 한쪽으로 기울었다. 읽기 성능이 데이터 입력 순서라는 통제 불가능한 외생 변수에 인질로 잡힌 셈이다. 이 예측 불가능성 때문에 이진 탐색 트리는 인덱스 후보에서 탈락했다.

AVL — 엄격한 균형, 무거운 쓰기

AVL Tree(1962)는 어떤 데이터가 들어오든 엄격하게 트리의 균형을 맞췄다. 덕분에 일관된 읽기 성능이라는 확실성을 얻었다.

그러나 대가는 쓰기 성능의 희생이었다. 데이터 하나를 넣을 때마다 발생하는 균형 유지 비용이 너무 비쌌다.

Red-Black — 가벼운 쓰기, 느슨한 균형

Red-Black Tree(1972)는 AVL이 균형을 너무 비싸게 샀다고 봤다. 완벽한 균형 대신 대략적인 균형만 보장하는 우회로를 택했다.

[ Red - Black ]
                                1억 개 키 저장 시
              [Root]            트리 높이: ~30
              /    \
           [N]      [N]         디스크 접근: 30번
          / \        / \        각 접근 = 페이지 한 장 통째로
        [N] [N]    [N] [N]

        ... 깊이 30까지 ...

이 합리적인 타협은 메모리 안에서 정렬된 데이터를 관리하는 메모리 시장을 지배했다. Linux 커널의 스케줄러, Java의 TreeMap, C++의 std::map이 모두 이 최적해를 사용한다.

그러나 디스크 환경에서는 이 챔피언조차 무너졌다. 중요 가치가 달랐기 때문이다.

디스크 환경의 새 참가자

디스크에서 비용을 매기는 단위는 메모리와 완전히 다르다. 디스크는 데이터를 페이지(Page)라는 큰 단위로만 읽기 때문에, 노드 안의 작은 데이터 하나만 보려고 해도 페이지 한 장(보통 16KB)의 비용이 통째로 청구된다.

메모리 챔피언의 몰락

Red-Black Tree는 메모리에서 최적해였지만, 디스크 비용으로 환산되는 순간 가치가 곤두박질친다.

[ 1억 개 키 저장 시 구조 비교 ]

Red-Black Tree       트리 높이: ~30 층  → 디스크 접근: 30번
B+Tree               트리 높이:   4 층  → 디스크 접근:  4번

1억 개의 키를 저장할 때 Red-Black 트리의 높이는 약 30이다. 메모리에서는 30번의 비교가 찰나에 불과하지만, 디스크에서는 30번의 I/O 청구서가 된다. 한 번의 조회를 처리하기 위해 비싼 창고를 30번이나 열어야 하는 셈이다.

B+Tree의 설계 원리

B+Tree는 이 비용 구조에 맞춰 설계된 자료구조다. 핵심 발상은 단순하다. 어차피 페이지 한 장의 비용을 통째로 내야 한다면, 그 한 장 안에 최대한 많은 정보를 담는 것이다.

그래서 B+Tree는 한 노드에 수백 개의 키를 압축해서 밀어 넣고, 이 노드 크기를 디스크의 페이지 단위와 정확히 일치시켰다. 덕분에 한 번의 디스크 접근으로 수백 개의 키를 메모리에 한꺼번에 올려 비교할 수 있다.

[ B+Tree 구조 ]
        [Root: 100 keys]
        /    |    |    \
        [...100 keys...]             ← 한 노드 = 한 페이지 (수백 갈래 분기)
      / | | \   ...
    [Leaf nodes: 실제 데이터]         ← 리프 노드끼리 연결 리스트로 결합
    → → → → → → → → → → → →
    (범위 검색 시 리프만 따라가며 순회)

트리의 가로 폭이 넓어진 만큼 높이는 폭발적으로 낮아진다. 1억 개의 데이터를 저장해도 높이는 단 4층에 불과하여 디스크 청구서가 30번에서 4번으로 줄어든다.

시장이 결정한 정답

이진 트리부터 Red-Black Tree까지는 메모리 안에서 발전한 구조였다. 반면 B+Tree는 그 계보의 연장선이 아니라, 디스크 환경의 비용 구조에 맞춰 새로 만들어진 구조이다.

자료구조의 우열은 절대적이지 않다. 무엇으로 비용을 매기느냐에 따라 정답을 결정한다.

인덱스의 아키텍처와 숨은 청구서

B+Tree가 인덱스의 뼈대라면, 그 위에 어떤 인덱스를 구성할지는 우선순위의 선택이다. 모든 인덱스는 눈앞의 효율성을 대가로 반드시 보이지 않는 곳에 물리적 비용을 청구한다.

설계의 본질은 공짜 성능을 얻는 것이 아니다. 당장 눈에 보이는 하나의 이득을 위해, 보이지 않는 다른 성능을 담보로 잡는다.

Hash Index의 등가교환

단건 조회가 필요한 경우가 있다. user_id나 주문 번호처럼 하나의 값으로 바로 결과를 가져와야 하는 작업이다. Hash 인덱스는 이런 경우를 위해 만들어졌다. 키를 해시로 변환해 위치를 바로 계산하기 때문에, 정확한 값 조회는 매우 빠르다.

하지만 이 구조는 데이터의 순서를 완전히 버린다. 값들이 흩어져 저장되기 때문에 범위 조회나 정렬이 불가능하다.

Composite Index의 우선순위 배분

실제 쿼리는 여러 조건이 함께 붙는 경우가 많다. “이 사용자의 최근 주문”처럼 user_id와 created_at이 함께 등장하거나, “이 카테고리에서 가격순 정렬”처럼 여러 컬럼이 동시에 조건으로 걸린다.

[ Composite Index (user_id, created_at) ]

인덱스 정렬 순서:

    user_id  | created_at
    ─────────┼───────────
    100      | 2024-01-01
    100      | 2024-02-15
    100      | 2024-03-20
    200      | 2024-01-10
    200      | 2024-02-05
    300      | 2024-01-25

  ✓ WHERE user_id = 100                        → 빠름 (앞에서 끊어 읽기)
  ✓ WHERE user_id = 100 AND created_at > ...   → 빠름 (둘 다 활용)
  ✗ WHERE created_at = '2024-01-01'            → 인덱스 못 씀 (왼쪽 끊김)

복합 인덱스는 모든 컬럼에 동일한 효율을 제공하지 않는다. 인덱스는 항상 앞쪽 컬럼부터 의미를 가지기 때문에, 선두 컬럼이 포함된 쿼리는 빠르게 처리되지만 뒤쪽 컬럼만으로는 인덱스를 사용할 수 없다.

Covering Index가 받아들인 부피의 대가

앞선 DB 1편에서 언급했듯이, 디스크에서 데이터를 읽는 건 너무 비싼 비용을 치러야 한다. 읽기 병목이 심한 환경이라면 이를 대비한 인덱스 아키텍처가 필요하다.

커버링 인덱스는 인덱스 페이지 안에서 필요한 데이터들을 모두 담아 실질적 디스크 I/O 비용을 최소화하므로, 읽기 성능이 매우 개선된다.

그러나 컬럼이 추가된 만큼 인덱스가 차지하는 용량이 많아진다. 따라서 테이블에 데이터가 추가되거나 수정될 때마다, 쓰기 작업에서 더 많은 비용을 감수해야 한다.

정리

아키텍처 설계에서 ‘무료 성능’이란 존재하지 않는다. 아래의 선택 기준 역시 거래의 양면을 모두 저울질한 결과다.

인덱스 형태	가시적 이득	비가시적 비용	최적 상황
Hash Index	특정 값의 초고속 조회 O(1)	범위 검색 및 정렬 기능의 완전 무력화	고유한 키-값 기반의 정확한 단건 조회가 중심일 때
Composite Index	복합 조건 쿼리의 다중 필터링	선두 컬럼 누락 시 인덱스 전체 필요성 급락	자주 묶여서 들어오는 명확한 비즈니스 조회 패턴이 있을 때
Covering Index	데이터 페이지 디스크 접근 생략	인덱스 용량 비대화 및 모든 쓰기 비용 증가	읽기 빈도가 압도적이며, 쓰기 성능 저하를 감당할 수 있을 때

보이는 것과 보이지 않는 것

1850년 프랑스 경제학자 프레데릭 바스티아는 에세이 “보이는 것과 보이지 않는 것(That Which Is Seen, and That Which Is Not Seen)“에서 경제적 판단의 핵심 오류를 지적했다. 사람들은 어떤 행위가 가져오는 눈에 보이는 즉각적 결과에는 반응하지만, 그 행위가 동시에 발생시키는 눈에 보이지 않는 연쇄적 결과는 계산하지 못한다는 점이다.

바스티아가 제시한 ‘깨진 유리창 우화’가 대표적이다. 유리창이 깨지면 유리장수가 일을 얻지만(보이는 결과), 유리창 주인이 그 돈으로 사려 했던 책이나 옷의 거래는 사라진다(보이지 않는 결과). 결국 사회 전체로 보면 부의 창출이 아닌 단순한 자원 손실일 뿐이다. 보이는 이득이 보이지 않는 손실을 가렸을 뿐이다.

Reference: Bastiat, “That Which Is Seen, and That Which Is Not Seen” (1850)

데이터베이스 인덱스의 역설도 정확히 이 구조를 따른다.

보이는 성능과 숨은 비용

인덱스를 추가하면 읽기 속도 향상은 가시적이고 즉각적이다. 반면, 그로 인해 발생하는 쓰기 쿼리의 지연은 건당 수 밀리초 미만이기에 비가시적이고 지연적이다.

이 숨은 비용은 쓰기 작업마다 조용히 누적된다. 대규모 트래픽 환경에서 누적된 디스크 작업은 대기 큐(Write Queue)를 형성하고 복제 지연(Replication Lag)을 유발하여 시스템 전반의 성능 저하로 이어진다.

인덱스가 없을 때(Full Scan)와 인덱스가 많을 때의 보이지 않는 손실(쓰기 비용 누적)은 결국 자원 거래의 양면이다.

인덱스 남발의 인지 편향

이 비대칭성은 엔지니어에게 인지 편향을 유발한다. 느린 쿼리를 발견할 때마다 인덱스를 추가하는 것은 안전한 결정처럼 느껴지기 마련이다.

데이터베이스에 수백 개의 인덱스가 쌓이는 것은 설계 실패가 아니다. 보이는 이득을 좇아 보이지 않는 비용을 무시한 작은 선택들이 누적된 결과다. 바스티아가 경고한 인간의 편향이 현대 데이터베이스 운영에서도 동일하게 반복된다.

숨은 비용의 가시화

인덱스 설계는 결국 최적화의 문제가 아니라 비용 분담의 문제다. 새로운 인덱스를 추가할 때, 다음 두 가지를 따져야 한다.

첫째, 누가 이득을 보는가. 1년에 몇 번 쓰지도 않는 통계 쿼리를 위해, 1초에도 수십 번 발생하는 INSERT 성능을 희생할 이유는 없다. 모든 인덱스는 그만한 가치가 있는 쿼리를 위해 존재해야 한다.

둘째, 비용을 회수할 수 있는가. 인덱스를 유지하는 데 드는 비용(쓰기 지연)보다, 인덱스로 얻는 이득(조회 성능 향상)이 더 커야 한다. 일회성 데이터 조회를 위해 평생 인덱스 유지 비용을 지불하는 건 합리적이지 않다.

인덱스 운영의 핵심은 늘리는 게 아니라 정리하는 것이다. 쓰임새가 다한 인덱스는 성능을 갉아먹는 고정비가 된다. 가끔은 인덱스를 하나 삭제하는 것이, 인덱스를 하나 추가하는 것보다 더 큰 성능 향상을 가져오기도 한다.

The Bottom Line

인덱스는 데이터베이스가 풀스캔이라는 비용 폭탄에서 벗어나기 위해 쓰는 가장 강력한 도구다. 이 도구는 매 쿼리마다 99%를 건너뛰게 해주고, 1편이 약속한 디스크를 덜 읽는다는 명제를 가장 직접적으로 실현한다. 그러나 인덱스는 읽기를 위해 쓰기를 팔고, 그 댓가는 보이지 않는 곳에서 청구된다.

엔지니어가 이 구조를 이해하면, 인덱스를 추가하는 결정과 제거하는 결정 모두를 같은 무게로 다룬다.

이 인덱스가 어떤 쿼리에 우선권을 주는가, 그리고 그 우선권의 대가를 어디에서 지불하는가.

다음 편: 여러 사용자가 동시에 같은 데이터를 건드리는 순간, 데이터베이스는 어떤 작업을 허용하고 어떤 작업을 멈춰야 할까. 성능과 무결성이 충돌하는 지점에서 등장한 규칙, 다음 주제는 트랜잭션이다.