인덱스와 B-tree

데이터베이스에 100만 건의 주문 데이터가 있다. 특정 고객의 주문을 찾는 쿼리를 실행한다. 인덱스가 없으면 100만 건을 처음부터 끝까지 읽어야 한다. 인덱스가 있으면 3~4번의 디스크 접근으로 끝난다. 이 차이가 어디서 오는지 이해하려면 B-tree를 알아야 한다.

인덱스가 없을 때 -- 풀 테이블 스캔

인덱스 없이 다음 쿼리를 실행한다:

SELECT * FROM orders WHERE customer_id = 42;

InnoDB는 테이블의 모든 page를 순서대로 읽는다. 03편에서 다룬 것처럼, InnoDB의 page 크기는 16KB다. 행 하나가 평균 200바이트라면 한 page에 약 80개의 행이 들어간다. 100만 건이면 약 12,500개의 page를 읽어야 한다.

각 page를 읽을 때마다 그 안의 모든 행에서 customer_id = 42인지 확인한다. 조건에 맞는 행이 10건이든 0건이든, 마지막 page까지 전부 읽어야 끝난다. 이것이 풀 테이블 스캔(full table scan)이다.

풀 테이블 스캔이 항상 나쁜 것은 아니다. 테이블 전체의 80% 이상을 읽어야 하는 쿼리라면 인덱스를 거치는 것보다 풀 스캔이 더 빠를 수 있다. 하지만 100만 건 중 10건을 찾는 상황이라면 비효율이 극심하다.

B-tree 구조

데이터베이스 인덱스의 핵심 자료구조는 B-tree다. 정확히 말하면 InnoDB는 B+tree를 사용한다. 1972년 Rudolf Bayer와 Edward McCreight가 발표한 이 자료구조는 디스크 기반 시스템에 최적화되어 있다.

B+tree의 구조

B+tree는 세 종류의 노드로 구성된다:

루트 노드(root node): 트리의 최상위. 검색의 시작점이다.
브랜치 노드(branch node): 중간 계층. 검색 방향을 결정하는 가이드 역할을 한다.
리프 노드(leaf node): 최하위 계층. 실제 데이터(또는 데이터를 가리키는 포인터)가 여기에 있다.

customer_id 컬럼에 인덱스가 있다고 가정한다. 트리의 구조는 이렇게 생겼다:

             [루트: 100, 500]
            /        |        \
  [브랜치: 30,70]  [브랜치: 200,350]  [브랜치: 600,800]
    /    |   \       /    |    \        /    |    \
[리프] [리프] [리프] [리프] [리프] [리프] [리프] [리프] [리프]

루트 노드에 [100, 500]이 있다면:

customer_id < 100이면 왼쪽 브랜치로
100 <= customer_id < 500이면 가운데 브랜치로
customer_id >= 500이면 오른쪽 브랜치로

브랜치 노드에서도 같은 방식으로 다음 노드를 선택한다. 최종적으로 리프 노드에 도달한다.

B+tree와 B-tree의 차이

일반 B-tree는 모든 노드에 데이터를 저장한다. B+tree는 데이터를 리프 노드에만 저장한다. 브랜치 노드에는 검색을 위한 키 값과 자식 노드 포인터만 있다.

이 차이가 중요한 이유가 있다. 브랜치 노드에 데이터가 없으면, 같은 크기의 page에 더 많은 키를 담을 수 있다. 키가 많을수록 한 번의 page 읽기로 더 넓은 범위를 커버한다. 트리의 높이가 낮아지고, 디스크 접근 횟수가 줄어든다.

B+tree의 또 다른 특징은 리프 노드끼리 연결 리스트(linked list)로 연결되어 있다는 점이다. 범위 검색(BETWEEN, >, <)에서 이 구조가 빛을 발한다. 시작 리프를 찾으면, 연결 리스트를 따라가며 순서대로 읽기만 하면 된다. 트리를 다시 탐색할 필요가 없다.

트리의 높이와 성능

InnoDB에서 B+tree 하나의 노드는 하나의 page(16KB)다. 키 하나의 크기가 8바이트(BIGINT)이고 포인터가 6바이트라면, 한 page에 약 1,000개의 키를 담을 수 있다.

높이 1 (루트만): 약 1,000개의 키
높이 2: 약 1,000 x 1,000 = 100만 개의 키
높이 3: 약 1,000 x 1,000 x 1,000 = 10억 개의 키

높이 3이면 10억 건의 데이터에서 특정 값을 찾는 데 page 3번만 읽으면 된다. 루트 노드는 거의 항상 buffer pool에 캐시되어 있으므로, 실질적인 디스크 읽기는 2회 이하다. 대부분의 실무 테이블에서 인덱스 트리의 높이는 3~4를 넘지 않는다.

Clustered index

InnoDB에서 clustered index는 단순한 인덱스가 아니다. 테이블 데이터 그 자체다.

InnoDB의 모든 테이블은 clustered index 구조로 저장된다. Primary key(PK)가 clustered index의 키가 된다. 테이블의 모든 행은 PK 순서대로 B+tree의 리프 노드에 저장된다. "테이블을 읽는다"는 것은 곧 "clustered index의 리프 노드를 읽는다"는 뜻이다.

Clustered Index (PK = id):

     [루트: 500, 1000]
      /       |       \
[브랜치]  [브랜치]   [브랜치]
   |         |          |
[리프]    [리프]      [리프]
 id=1      id=501     id=1001
 name=...  name=...   name=...
 email=... email=...  email=...
 (전체 행)  (전체 행)   (전체 행)

PK가 명시되지 않으면 InnoDB는 NOT NULL UNIQUE 컬럼을 찾고, 그것도 없으면 내부적으로 6바이트 row ID를 생성하여 clustered index를 만든다. 어떤 경우에도 InnoDB 테이블은 clustered index 위에 존재한다.

PK가 auto increment 정수인 경우, 새로운 행은 항상 리프 노드의 끝에 추가된다. 트리 구조가 안정적으로 유지된다. UUID를 PK로 사용하면 삽입 위치가 랜덤해져서, page split이 빈번하게 발생하고 성능이 저하된다.

Secondary index

PK 이외의 컬럼에 만드는 인덱스가 secondary index다. customer_id에 인덱스를 만드는 경우를 본다:

CREATE INDEX idx_customer ON orders (customer_id);

이 인덱스도 B+tree 구조다. 하지만 리프 노드에 저장하는 것이 다르다. Clustered index의 리프 노드에는 행 전체가 들어 있지만, secondary index의 리프 노드에는 인덱스 키 값과 해당 행의 PK 값만 들어 있다.

Secondary Index (customer_id):

     [루트: 100, 500]
      /       |       \
[브랜치]  [브랜치]   [브랜치]
   |         |          |
[리프]    [리프]      [리프]
 cust=1    cust=101   cust=501
 → PK=7   → PK=23    → PK=102
 cust=1    cust=102   cust=503
 → PK=15  → PK=45    → PK=88

리프 노드에 행의 물리적 주소가 아니라 PK 값을 저장하는 것이 InnoDB secondary index의 핵심 특징이다. 다른 storage engine(예: MyISAM)은 행의 물리적 위치(파일 오프셋)를 저장하는데, InnoDB는 이 방식을 취하지 않는다. 이유는 clustered index 때문이다. 행이 이동하면(page split 등) 물리적 주소가 바뀐다. PK 값을 저장하면 행이 어디로 이동하든 PK로 다시 찾을 수 있다.

인덱스로 검색할 때 일어나는 일

다시 이 쿼리를 본다:

SELECT * FROM orders WHERE customer_id = 42;

customer_id에 secondary index가 있을 때, InnoDB는 두 단계를 거친다:

1단계: Secondary index 탐색

secondary index의 B+tree를 루트부터 탐색하여 customer_id = 42인 리프 노드에 도달한다. 여기서 해당하는 PK 값들을 얻는다. 예를 들어 PK가 7, 15, 203이라고 가정한다.

2단계: PK lookup (bookmark lookup)

얻은 PK 값 각각에 대해 clustered index를 다시 탐색한다. PK = 7인 행, PK = 15인 행, PK = 203인 행을 각각 찾아서 전체 컬럼 데이터를 가져온다.

이 두 번째 단계를 bookmark lookup 또는 table lookup이라고 부른다. Secondary index만으로는 SELECT *에 필요한 모든 컬럼 데이터를 얻을 수 없기 때문에, clustered index로 다시 가서 나머지 데이터를 가져오는 것이다.

쿼리: WHERE customer_id = 42

[Secondary Index]              [Clustered Index]
  루트 → 브랜치 → 리프          루트 → 브랜치 → 리프
  customer_id=42 발견            PK=7 → 전체 행 반환
  → PK=7, 15, 203               PK=15 → 전체 행 반환
                                 PK=203 → 전체 행 반환

총 디스크 접근 횟수를 세어 본다. Secondary index 탐색에 2~~3회, PK lookup에 결과 행 하나당 2~~3회. customer_id = 42인 행이 3건이면, 최악의 경우 약 12회의 page 읽기로 끝난다. 풀 테이블 스캔의 12,500회와 비교하면 1,000배 차이다.

왜 풀 스캔보다 빠른가

인덱스가 빠른 이유는 결국 디스크 I/O의 양이 줄어들기 때문이다.

랜덤 I/O vs 순차 I/O

디스크(특히 HDD)에서 데이터를 읽는 비용은 두 가지로 나뉜다:

순차 I/O: 연속된 위치의 데이터를 읽는다. 디스크 헤드가 한 번 위치를 잡으면 쭉 읽으면 된다. 빠르다.
랜덤 I/O: 떨어진 위치의 데이터를 하나씩 읽는다. 매번 디스크 헤드가 이동해야 한다. 느리다.

풀 테이블 스캔은 순차 I/O다. Page를 처음부터 끝까지 순서대로 읽는다. 하지만 읽는 양 자체가 많다.

인덱스를 사용한 검색은 랜덤 I/O다. B+tree의 루트에서 리프로 점프하고, PK lookup에서 또 점프한다. 한 번의 I/O 비용은 더 크지만, 총 I/O 횟수가 극적으로 적다.

SSD에서는 랜덤 I/O와 순차 I/O의 성능 차이가 HDD보다 작다. 하지만 SSD에서도 읽는 page의 수를 줄이는 것이 핵심이라는 사실은 변하지 않는다.

읽는 데이터의 양

100만 건의 테이블에서 3건을 찾는 상황:

방식	읽는 page 수	비고
풀 테이블 스캔	~12,500	전체 테이블
인덱스 검색	~12	secondary index 탐색 + PK lookup

buffer pool에 데이터가 캐시되어 있으면 실제 디스크 I/O는 이보다 적다. 하지만 캐시에 없는 경우(cold start, 대용량 테이블)에는 이 차이가 쿼리 응답 시간에 직접적으로 반영된다.

인덱스의 비용

인덱스는 공짜가 아니다. 읽기 성능을 높이는 대가로 다른 곳에서 비용을 지불한다.

쓰기 성능 저하

행을 삽입하면 clustered index의 리프 노드에 데이터를 추가하는 것 외에, 해당 테이블의 모든 secondary index에도 새 항목을 추가해야 한다. 인덱스가 3개면 삽입 한 번에 B+tree 갱신이 4번(clustered 1 + secondary 3) 발생한다.

UPDATE도 마찬가지다. 인덱스된 컬럼의 값이 바뀌면, 기존 인덱스 항목을 삭제하고 새 항목을 추가해야 한다. DELETE는 모든 인덱스에서 해당 항목을 제거한다.

InnoDB는 change buffer라는 메커니즘으로 secondary index의 쓰기를 지연시킨다. 해당 page가 buffer pool에 없을 때, 변경 사항을 change buffer에 기록해 두고 나중에 page를 읽을 때 병합한다. 이 최적화 덕분에 즉각적인 랜덤 I/O를 줄일 수 있지만, 인덱스 유지 비용 자체가 사라지는 것은 아니다.

저장 공간

각 secondary index는 별도의 B+tree이므로 추가 디스크 공간을 차지한다. 테이블이 1GB이고 인덱스가 3개면, 인덱스만으로 수백 MB에서 1GB 이상의 추가 공간이 필요할 수 있다. 인덱스 키의 크기, 테이블의 행 수, PK의 크기에 따라 달라진다.

Secondary index의 리프 노드에 PK 값이 저장되므로, PK가 크면(예: 36바이트 UUID) secondary index도 커진다. PK를 작게 유지하는 것이 저장 공간과 성능 양쪽에 유리하다.

인덱스 설계의 트레이드오프

인덱스를 많이 만들면 읽기가 빨라지지만 쓰기가 느려진다. 인덱스를 적게 만들면 쓰기는 빠르지만 읽기에서 풀 스캔이 발생할 수 있다.

읽기 비율이 높은 서비스(대부분의 웹 애플리케이션)에서는 적절한 인덱스를 만드는 것이 유리하다. 쓰기 비율이 높은 시스템(로깅, 이벤트 수집 등)에서는 인덱스를 최소화해야 한다.

사용하지 않는 인덱스는 쓰기 비용만 발생시키고 읽기에 기여하지 않는다. 주기적으로 인덱스 사용 현황을 점검하고, 불필요한 인덱스를 제거하는 것이 바람직하다. MySQL에서는 sys.schema_unused_indexes 뷰로 사용되지 않는 인덱스를 확인할 수 있다:

SELECT * FROM sys.schema_unused_indexes
WHERE object_schema = 'my_database';

인덱스의 존재 자체가 비용이라는 점을 항상 인식해야 한다. "혹시 쓸까 봐" 만들어 두는 인덱스는 그 자체로 성능 부채다.

정리

B+tree는 디스크 기반 검색에 최적화된 자료구조로, 높이 3이면 10억 건에서도 3번의 페이지 읽기로 검색이 가능하다.
InnoDB의 clustered index는 테이블 데이터 그 자체이며, primary key 순서로 행이 저장된다.
Secondary index의 리프 노드에는 인덱스 키와 PK 값이 저장되어, 검색 시 PK lookup이 추가로 발생한다.
인덱스는 읽기를 빠르게 하지만, 쓰기 시 모든 관련 인덱스를 갱신해야 하므로 쓰기 비용이 증가한다.
PK를 작게 유지하면 모든 secondary index의 크기가 줄어든다.

← 행과 페이지

인덱스 심화 →