B+Tree 인덱스

인덱스는 조회를 무조건 빠르게 만드는 장치가 아니라, 정렬된 보조 구조를 유지하는 선택입니다.

어떤 행을 찾는지 설명하지 않은 채 인덱스를 늘리면 쓰기 비용과 저장 공간만 커집니다.

먼저 인덱스가 없는 회원 게시판 검색에서 데이터베이스가 얼마나 많은 후보를 확인하는지 관찰해야 합니다.

이번 문서는 author_id, status, created_at으로 최근 공개 게시글을 찾는 한 가지 요구를 끝까지 추적합니다.

결과 행은 같아도 테이블 스캔과 인덱스 범위 스캔은 읽는 후보 수가 다르다는 점을 중심에 둡니다.

실습용 post_search_demo는 운영 스키마를 훼손하지 않도록 별도 테이블로 만듭니다.

기본 키 외의 보조 인덱스를 두지 않은 상태에서 정확히 1만 건을 적재하고, 그중 4천 건을 author_id=42에 집중시킵니다.

특정 값에 행이 몰린 편향 분포를 만들어야 인덱스 선택도와 반복 조회 비용을 실제로 비교할 수 있습니다.

작은 샘플에서 2ms가 나왔다는 숫자보다 접근 방식과 검사한 행 수를 읽는 습관이 목적입니다.

전체 테이블 스캔

WHERE 절이 있으므로 필요한 행만 읽을 것이라 생각하기 쉽습니다.

그러나 정렬된 진입점이 없으면 InnoDB는 각 행의 작성자와 상태를 확인해야 합니다.

데이터가 100건일 때 숨겨진 비용은 1천만 건에서 지연과 버퍼 오염으로 드러납니다.

DROP TABLE IF EXISTS post_search_demo;
CREATE TABLE post_search_demo (
  post_id BIGINT UNSIGNED NOT NULL AUTO_INCREMENT,
  author_id BIGINT UNSIGNED NOT NULL,
  status VARCHAR(16) NOT NULL,
  created_at DATETIME(6) NOT NULL,
  view_count SMALLINT UNSIGNED NOT NULL,
  title VARCHAR(120) NOT NULL,
  PRIMARY KEY (post_id)
) ENGINE = InnoDB;

-- 0~9 숫자 10개를 비재귀 CTE로 정의한다.
INSERT INTO post_search_demo (
  author_id, status, created_at, view_count, title
)
WITH fixture_digit (digit) AS (
  SELECT 0 UNION ALL SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3
  UNION ALL SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6
  UNION ALL SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9
)
SELECT
  CASE WHEN seq.n <= 4000 THEN 42 ELSE 100 + MOD(seq.n, 200) END,
  CASE WHEN MOD(seq.n, 4) = 0 THEN 'DRAFT' ELSE 'PUBLISHED' END,
  TIMESTAMP('2026-01-01 00:00:00') + INTERVAL seq.n MINUTE,
  10 + MOD(seq.n, 111),
  CONCAT('post ', LPAD(seq.n, 5, '0'))
FROM (
  SELECT
    1 + ones.digit
      + tens.digit * 10
      + hundreds.digit * 100
      + thousands.digit * 1000 AS n
  FROM fixture_digit AS ones
  CROSS JOIN fixture_digit AS tens
  CROSS JOIN fixture_digit AS hundreds
  CROSS JOIN fixture_digit AS thousands
) AS seq;

-- 성능 비교가 의미 있는 동일 fixture인지 먼저 확인한다.
SELECT
  COUNT(*) AS total_rows,
  SUM(author_id = 42) AS author_42_rows,
  SUM(author_id = 42 AND status = 'PUBLISHED')
    AS author_42_published_rows,
  COUNT(DISTINCT author_id) AS distinct_authors
FROM post_search_demo;

EXPLAIN FORMAT=TREE
SELECT post_id, title, created_at
FROM post_search_demo
WHERE author_id = 42
  AND status = 'PUBLISHED'
ORDER BY created_at DESC
LIMIT 20;

fixture 확인 결과는 total_rows=10000, author_42_rows=4000, author_42_published_rows=3000이어야 합니다.

값이 다르면 뒤의 실행 계획 숫자를 비교하지 말고 DROP TABLE post_search_demo부터 이 블록을 다시 실행합니다.

fixture_digit은 0~9 행 10개이고, 5장에서 배운 CROSS JOIN으로 네 번 조합하면 10×10×10×10=10,000개 숫자가 됩니다.

MySQL은 한 쿼리에서 같은 TEMPORARY 테이블을 여러 번 참조할 수 없어 오류 1137을 냅니다. 여기서는 비재귀 CTE를 재사용하므로 재귀 한도와 무관합니다.

생성식의 시각은 2026년 1월 1일 00:01부터 1월 7일 22:40까지입니다. 뒤 문서의 7월 검색은 경계 테스트 행을 따로 넣기 전에는 결과가 없습니다.

기본 키 순서는 검색 조건과 무관하므로 실행 계획에는 테이블 스캔과 별도 정렬이 나타납니다.

아래는 접근 구조를 설명하는 예시이며 이번 작업에서 수집한 실행 로그가 아닙니다. 트리 아래의 key·access_type은 전통 형식·JSON에서 확인하는 별도 항목을 함께 적었습니다.

-> Limit: 20 row(s)
    -> Sort: post_search_demo.created_at DESC
        -> Filter: ((author_id = 42) and (status = 'PUBLISHED'))
            -> Table scan on post_search_demo

key = NULL
access_type = ALL

이 예시는 SQL 문법 오류가 아니라 검사량이 커질 수 있는 접근 경로를 보여 줍니다.

key = NULL은 사용할 보조 인덱스가 없다는 뜻이고 ALL은 테이블 전체 접근을 뜻합니다.

LIMIT 20은 반환 수를 제한합니다. 이처럼 별도 정렬이 필요하면 상위 20개를 고르기 위해 조건에 맞는 전체 후보를 읽을 수 있습니다.

기본 키 B+Tree의 리프에는 전체 행이 있지만 author_id 순으로 모여 있지 않습니다.

조건 컬럼을 앞에서부터 정렬한 보조 인덱스가 있어야 검색 시작점과 종료점을 계산할 수 있습니다.

계획에서 병목 노드를 찾는 네 번의 확인

1. 결과와 작업 구분 — 반환 행 20개와 검사 행 10,000개를 같은 숫자로 생각하지 않습니다.
2. 접근 노드 확인 — 트리 출력의 가장 안쪽이 테이블 스캔인지 인덱스 조회인지 먼저 찾습니다.
3. 정렬 비용 확인 — ORDER BY를 인덱스 순서로 해결하지 못해 Sort 노드가 생겼는지 봅니다.
4. 데이터 규모 환산 — 현재 행 수가 열 배가 될 때 검사량도 선형으로 늘어나는지 예측합니다.

회원가입의 이메일 조회는 빠르기만 해서는 부족합니다.

동시에 들어온 두 가입 요청도 같은 이메일을 저장하지 못하도록 members.email의 UNIQUE 제약이 최종 경계를 맡아야 합니다.

UNIQUE 제약은 내부적으로 고유 인덱스를 만들지만, 목적은 검색 성능보다 업무 무결성에 있습니다.

SHOW INDEX FROM members
WHERE Key_name = 'uq_members_email';

EXPLAIN FORMAT=TREE
SELECT id, email, name
FROM members
WHERE email = '[email protected]';

uq_members_email이 한 이메일의 탐색 범위를 한 행 이하로 줄이는지 확인합니다.

다만 SELECT 후 INSERT 순서만으로 중복 가입을 막을 수는 없으며, 실제 경합 처리는 다음 장에서 제약 오류와 트랜잭션 경계로 검증합니다.

B+Tree 탐색 원리

InnoDB 보조 인덱스의 리프 항목에는 인덱스 키와 기본 키 값이 저장됩니다.

데이터베이스는 루트에서 분기를 따라 조건의 시작 리프를 찾고, 필요한 범위만 순서대로 읽습니다.

따라서 탐색 높이는 완만하게 늘지만 리프 범위가 넓으면 여전히 많은 항목을 읽습니다.

인덱스가 있다는 사실보다 첫 컬럼이 자주 쓰는 동등 조건인지, 뒤 컬럼이 범위와 정렬을 이어받는지가 중요합니다.

선택도가 낮은 상태 하나만 인덱싱하면 전체의 절반 이상을 읽어 테이블 스캔이 더 쌀 수도 있습니다.

검색 문장을 B+Tree 순서로 옮기기

1. 질문 고정 — 작성자 한 명의 공개 게시글을 최신순 20건 찾는다고 자연어로 씁니다.
2. 동등 조건 배치 — author_id와 status는 한 값으로 범위를 좁히므로 앞쪽 후보입니다.
3. 순서 조건 배치 — created_at DESC를 뒤에 두면 같은 작성자·상태 안에서 최신순 리프를 읽습니다.
4. 투영 확인 — 목록이 제목까지 요구하므로 테이블 접근을 허용할지 커버링할지 다음 문서에서 판단합니다.

일곱 키로 리프에서 원본 행까지 따라가기

보조 인덱스에서 행까지 가는 길을 작은 키 목록으로 따라가 보겠습니다. 같은 작성자의 공개 글은 최신순으로 모여 있지만, 제목은 아래 인덱스에 없습니다. 먼저 리프에서 후보의 기본 키(PK)를 얻고, 그 기본 키로 원본 행의 제목을 찾습니다.

다음 절에서 만들 (author_id, status, created_at DESC) 인덱스의 순서를 일곱 개의 가상 항목에 적용합니다. 작성자와 상태는 오름차순이고, 같은 작성자·상태 안의 시각은 내림차순입니다. 키가 나열된 끝 노드인 리프는 이 순서대로 이어집니다. 아래 시각은 모두 2026-01-07이며, 앞서 만든 10,000행 fixture의 일부를 발췌한 것이 아닙니다.

루트는 어느 리프로 내려갈지 알려 주는 분기 노드입니다. 이 모형에서는 L2의 첫 키 (42, PUBLISHED, 10:00, PK 25)를 분기 기준으로 둡니다. 인덱스 정렬 순서에서 이 키보다 앞인 항목은 L1에, 이 키부터 뒤의 항목은 L2에 있습니다. 시각만 비교하지 않고 작성자·상태·시각의 순서로 비교해야 합니다.

표에서 author_id=42 AND status='PUBLISHED'에 맞는 첫 항목을 찾아보세요. 이 구간은 루트의 분기를 따라 L1에서 시작하며, 첫 일치 항목은 12:00의 PK 18입니다. L1에서 다음 일치 항목인 11:00의 PK 7을 얻고, 리프 연결을 따라 L2로 이동하면 10:00의 PK 25와 09:00의 PK 3을 얻습니다.

다음 항목은 작성자 43이므로 조건 구간이 끝납니다. 선택 순서는 18 → 7 → 25 → 3이고, 이 작은 모형의 일치 행은 네 개뿐입니다. LIMIT 20은 최대 반환 수이므로 네 행을 반환합니다. 항상 20행을 채우는 규칙이 아닙니다.

이제 제목을 채웁니다. 보조 리프에 있는 PK로 클러스터형 기본 키 인덱스의 원본 행을 찾습니다. 클러스터형 인덱스는 PK 순서이므로 선택한 네 행을 그 순서로 발췌하면 3, 7, 18, 25입니다. 그래도 요구한 결과 순서는 시각 내림차순인 18, 7, 25, 3입니다. PK로 행을 찾는다는 것은 결과를 PK 순서로 바꾸라는 뜻이 아닙니다.

결과 키의 순서가 다르면 작성자·상태의 동등 조건과 시각의 DESC 방향을 먼저 확인합니다. 제목이 다르면 리프의 PK와 원본 행의 대응을 확인합니다. 이 그림은 논리적인 탐색 경로이며 실제 InnoDB 페이지 배치·트리 높이·물리 I/O 횟수나 측정 결과를 나타내지 않습니다. 시작점을 찾는 동안 다른 키와 비교할 수도 있으므로, 조건 밖 항목을 물리적으로 전혀 읽지 않았다는 뜻도 아닙니다.

화면이 post_id, created_at만 필요하다면 이 보조 리프에 필요한 값이 모두 있습니다. 이렇게 조회에 필요한 열을 인덱스에서 얻을 수 있는 경우를 커버링 접근이라고 합니다. 이때 제목을 얻기 위한 원본 조회는 생략될 수 있지만, 원래 쿼리는 제목을 요구하므로 그 요구를 그대로 유지합니다.

다만 현재 트랜잭션에서 볼 수 있는 행인지 확인하는 MVCC 가시성 검사 때문에 원본 행을 확인할 수도 있습니다. 커버링이어도 항상 원본 접근이 0회인 것은 아닙니다. 값의 포함 여부와 정렬 충족 여부도 구별해야 하며, 커버링 인덱스 절에서 이어서 살펴봅니다.

조회 조건과 복합 인덱스

작성자와 상태를 동등 비교한 뒤 시각 순서로 읽도록 복합 인덱스를 만듭니다.

인덱스 이름에는 테이블과 선두 컬럼을 드러내고, 생성 직후 같은 SQL로 계획을 다시 수집합니다.

CREATE INDEX ix_post_search_author_status_created
  ON post_search_demo (
    author_id,
    status,
    created_at DESC
  );

ANALYZE TABLE post_search_demo;

EXPLAIN FORMAT=TREE
SELECT post_id, title, created_at
FROM post_search_demo
WHERE author_id = 42
  AND status = 'PUBLISHED'
ORDER BY created_at DESC
LIMIT 20;

새 계획은 조건 범위에서 바로 시작하고 리프 순서가 정렬 요구와 같아 별도 Sort를 피할 수 있습니다.

-> Limit: 20 row(s)
    -> Index lookup on post_search_demo
       using ix_post_search_author_status_created
       (author_id=42, status='PUBLISHED')

key = ix_post_search_author_status_created
access = ref/range
separate Sort node = absent

트리 문구와 비용 숫자는 데이터 분포와 통계에 따라 달라질 수 있지만, 인덱스 이름·접근 범위·별도 정렬 유무는 비교할 수 있습니다.

옵티마이저가 여전히 테이블 스캔을 고른다면 데이터가 너무 작거나 조건이 대부분 행을 선택하는지 확인합니다.

인덱스는 결과 정합성을 바꾸면 안 됩니다.

생성 전후의 post_id 집합과 순서를 비교하고, 성능은 EXPLAIN ANALYZE의 실제 행 수와 반복 횟수로 따로 검증합니다.

배포 전후를 같은 조건으로 대조하기

1. 기준선 저장 — 인덱스 생성 전 SQL, 계획, 대표 파라미터, 행 수를 함께 보존합니다.
2. DDL 적용 — 온라인 DDL 가능 여부와 잠금 영향을 확인하고 이름이 중복되지 않게 생성합니다.
3. 통계 갱신 — 대량 적재 직후라면 ANALYZE TABLE로 분포 추정치를 최신화합니다.
4. 결과 일치 검사 — 성능 개선 전후 반환 키를 비교합니다. MySQL 8.4의 EXCEPT나 안티 조인으로 집합 차이를 확인하고, 정렬 순서는 별도로 비교합니다.

예상 행과 실제 행 비교

EXPLAIN ANALYZE는 쿼리를 실제 실행하므로 읽기 전용 대표 데이터에서 사용합니다.

추정 행 수와 실제 행 수 차이가 크면 인덱스 자체보다 통계·상관관계·파라미터 분포를 의심합니다.

EXPLAIN ANALYZE
SELECT post_id, title, created_at
FROM post_search_demo
WHERE author_id = 42
  AND status = 'PUBLISHED'
ORDER BY created_at DESC
LIMIT 20;

SELECT COUNT(*) AS matching_rows
FROM post_search_demo
WHERE author_id = 42
  AND status = 'PUBLISHED';

계획에 표시된 인덱스 조회의 실제 행 수가 matching_rows 또는 LIMIT으로 중단된 행 수와 어떤 관계인지 설명할 수 있어야 합니다.

시간 숫자 한 번보다 같은 데이터 스냅샷에서 여러 번 측정한 분포를 기록합니다.

보조 인덱스 리프 뒤에서 일어나는 일

제목이 포함되지 않은 보조 인덱스로 행을 찾으면 리프의 기본 키를 사용해 클러스터형 인덱스에서 원본 행을 다시 읽습니다.

후보가 적으면 효율적이지만 수만 건이면 랜덤 접근이 누적됩니다.

모든 컬럼을 인덱스에 넣기 전에 목록이 정말 제목을 즉시 필요로 하는지와 쓰기 비용을 비교합니다.

페이지 캐시에 데이터가 있는지, 동시 쓰기가 있는지, 디스크가 SSD인지에 따라 절대 시간은 달라집니다.

그러므로 구조 비교는 접근 방식과 실제 행 수를 우선하고 시간은 동일 조건에서 보조 지표로 봅니다.

스캔·복합·커버링 선택표

분포를 바꿔 다시 측정하기

1. 데이터 분포 만들기 — 작성자 수와 상태 비율을 바꾸어 같은 인덱스의 선택도가 달라지게 합니다.
2. 계획 캡처 — 인덱스 전후 FORMAT=TREE와 FORMAT=JSON을 저장하고 키, 행 수, 정렬을 표시합니다.
3. 결과 일치 검사 — 두 실행의 post_id를 임시 테이블에 저장해 누락과 추가가 0인지 확인합니다.
4. 삭제 실험 — 인덱스를 DROP한 뒤 계획이 기준선으로 돌아오는지 확인해 인과관계를 분리합니다.

온라인 DDL에 붙여야 할 관찰값

운영 인덱스 추가는 메타데이터 잠금과 I/O를 만들 수 있습니다.

MySQL 8.4의 DDL 알고리즘 지원 여부, 복제본 지연, 디스크 여유를 확인하고 롤백 계획을 준비합니다.

슬로 쿼리의 파라미터 분포가 개발 샘플과 다르면 같은 SQL도 다른 계획을 고를 수 있습니다.

상위·중간·하위 빈도 작성자를 대표값으로 측정합니다.

NULL·동률·대량 조회에서 달라지는 판단

• NULL이 가능한 선두 컬럼은 NULL 범위도 인덱싱되지만 = NULL이 아니라 IS NULL로 조회합니다.
• DESC 인덱스 지원 여부와 혼합 정렬 방향을 확인하고, 같은 시각 동률에는 post_id 정렬을 추가합니다.
• LIMIT 없는 전체 내보내기는 인덱스를 타도 많은 원본 행을 읽으므로 페이지 나누기·배치 경계를 별도로 설계합니다.
• 외래 키가 자동 생성한 단일 인덱스와 새 복합 인덱스가 중복되는지 SHOW INDEX로 확인합니다.

이 문서의 복합 인덱스는 다음 문서의 범위·LIKE·정렬 조건을 검증하는 기준선입니다.

이후 물리 모델링에서는 논리 모델의 키와 실제 접근 경로를 분리해 기록합니다.

인덱스 도입 기준

인덱스는 컬럼 인기도가 아니라 쿼리 규칙에 붙입니다.

대표 SQL이 없거나 검사한 행 수 감소를 설명할 수 없으면 생성 후보에서 보류합니다.

연습 문제

author_id = ?인 초안 상태의 게시글을 created_at ASC로 10건 찾는 화면을 설계하세요.

현재 공개 게시글용 인덱스를 재사용할지 새 인덱스를 만들지 판단하고, 계획을 확인하는 SQL까지 작성합니다.

이 문제의 초안 상태의 게시글은 앞 장의 초안 상태인 DRAFT를 뜻합니다. 생성 블록을 한 번만 실행한 기준 fixture에서 작성자 42의 초안은 생성 번호가 4의 배수인 행입니다. 인덱스 선택을 보기 전에 첫 10건의 제목과 시각을 먼저 예측해 보세요. post_id의 값은 적재 순서에 따라 달라질 수 있으므로 생성 번호와 같다고 가정하지 않습니다.

EXPLAIN ANALYZE
SELECT post_id, title, created_at
FROM post_search_demo
WHERE author_id = 42
  AND status = 'DRAFT'
ORDER BY created_at ASC, post_id ASC
LIMIT 10;

SHOW INDEX FROM post_search_demo;

핵심 정리

• WHERE와 LIMIT만으로 읽는 후보가 줄지는 않습니다.
• B+Tree 인덱스는 정렬된 키에서 시작점과 범위를 제공합니다.
• 실행 계획은 키, 접근 노드, 실제 행 수, 정렬 유무로 읽습니다.
• 인덱스 전후에는 결과 동일성과 운영 DDL 비용을 함께 검증합니다.

다음 문서에서는 같은 인덱스도 함수·범위·LIKE 표현에 따라 사용할 수 없는 이유를 다룹니다.