---
title: "B+Tree 인덱스 구조: root, branch, leaf page와 탐색 비용"
description: "InnoDB B+Tree의 root·branch·leaf page 구조와 탐색 비용, 클러스터형·보조 인덱스의 차이를 운영 관점에서 설명한다."
tags: [ MySQL, InnoDB, 인덱스, 성능최적화 ]
image: "mysql-report-bg.png"
published: "2026-07-19"
updated: "2026-07-19"
author: "MySQL 기술 노트"
source_url: ""
---

MySQL에서 “인덱스를 사용한다”는 말만으로는 쿼리 비용을 충분히 설명할 수 없다. 같은 B+Tree 인덱스를 사용하더라도 한 건을 찾는 point lookup, 넓은 범위를 읽는 range scan, 보조 인덱스에서 기본 키를 따라가는 table lookup은 서로 다른 수의 page와 row를 방문한다. 더구나 논리적인 page 방문이 실제 storage I/O로 이어지는지는 Buffer Pool 적중 여부에 따라 달라진다.

이 글은 InnoDB B+Tree를 root page, branch page, leaf page로 나누어 탐색 경로를 설명한다. 이어서 클러스터형 인덱스와 보조 인덱스가 leaf page에 무엇을 저장하는지, tree height와 fan-out이 왜 중요한지, 실행 계획을 어떻게 읽어야 하는지를 운영 관점에서 정리한다. 기본 대상은 MySQL 8.0 이상이며, 예제는 MySQL 8.0 임시 환경에서 실행 검증한다.

## 1. B+Tree가 해결하는 문제

테이블에 원하는 row가 있는지 확인하려고 모든 row를 처음부터 끝까지 읽으면 데이터 양에 비례하여 비용이 증가한다. 정렬된 배열은 이진 탐색에는 유리하지만 중간 삽입과 삭제 비용이 크다. B+Tree는 정렬 상태를 page 단위로 유지하면서 다음 요구를 함께 만족시킨다.

- equality predicate의 탐색 범위를 빠르게 줄인다.
- leaf page를 key 순서로 연결하여 range scan을 지원한다.
- 하나의 branch page가 많은 child page를 가리키도록 하여 tree height를 낮춘다.
- page 분할과 병합을 통해 온라인 변경을 수용한다.
- storage와 Buffer Pool의 기본 전송 단위인 page에 맞춰 접근한다.

여기서 `B+`의 핵심은 실제 검색 대상 record가 leaf level에 있고, leaf page끼리 key 순서로 연결된다는 점이다. branch level은 검색 경로를 안내하는 separator key와 child page pointer를 보관한다. 따라서 특정 key를 찾을 때는 위에서 아래로 내려가고, 범위를 읽을 때는 시작 leaf를 찾은 뒤 옆 leaf로 이동한다.

## 2. root, branch, leaf page의 역할

```mermaid
flowchart TB
    Q["검색 조건: customer_id = 4201"] --> R["Root page<br/>separator key로 하위 범위 선택"]
    R --> B1["Branch page<br/>작은 key 범위"]
    R --> B2["Branch page<br/>중간 key 범위"]
    R --> B3["Branch page<br/>큰 key 범위"]
    B2 --> L1["Leaf page N"]
    B2 --> L2["Leaf page N+1"]
    B2 --> L3["Leaf page N+2"]
    L1 <--> L2
    L2 <--> L3
    L2 --> X["일치 record 또는 다음 탐색 단계"]
```

### 2.1 Root page

root page는 tree 탐색의 시작점이다. 작은 인덱스는 root 자체가 leaf인 단일-level tree일 수 있다. 데이터가 증가하면 root가 branch 역할을 하며 여러 하위 page 범위를 가리킨다.

root는 거의 모든 인덱스 탐색에서 방문하므로 자주 접근된다. 운영 중인 데이터베이스에서는 hot index의 상위 level이 Buffer Pool에 남아 있을 가능성이 높다. 그러므로 “tree height가 4이므로 매 lookup마다 디스크를 네 번 읽는다”라고 단정해서는 안 된다. height는 우선 논리적 page 탐색 횟수를 뜻하고, 물리 I/O는 cache 상태에 따라 달라진다.

### 2.2 Branch page

branch page는 separator key와 child page reference를 보관한다. 검색 key와 separator를 비교하여 다음 level에서 방문할 page를 결정한다. record 전체를 보관하지 않기 때문에 leaf보다 한 page에 더 많은 entry가 들어가는 경우가 많다.

한 branch page가 가리킬 수 있는 child 수를 fan-out이라고 생각할 수 있다. fan-out이 `F`이고 leaf가 `L`개라면 height는 대략 `log_F(L)`의 형태로 증가한다. 실제 InnoDB page에는 page header, record header, page directory, free space 등이 존재하며 variable-length key와 page occupancy도 영향을 주므로 단순 산식은 설명용 근사치다.

### 2.3 Leaf page

leaf page에는 정렬된 index record가 저장된다. 인접 leaf는 key 순서로 연결되어 있으므로 `BETWEEN`, prefix range, index-order scan은 시작 leaf까지 내려간 뒤 leaf chain을 따라갈 수 있다.

leaf에 저장되는 내용은 인덱스 종류에 따라 다르다.

| 인덱스 종류 | Leaf record의 핵심 내용 | 일치 후 동작 |
|---|---|---|
| 클러스터형 인덱스 | primary key와 row의 나머지 column | leaf에서 row를 얻음 |
| 보조 인덱스 | secondary key와 해당 row의 primary key | 필요한 column이 부족하면 primary key B+Tree를 다시 탐색 |
| covering 보조 인덱스 | query에 필요한 column이 모두 leaf record에 존재 | clustered lookup을 생략할 수 있음 |

InnoDB 테이블은 primary key를 기준으로 clustered index를 구성한다. 명시적 primary key가 없으면 적절한 `UNIQUE NOT NULL` 인덱스를 선택하거나 내부 row ID를 사용한다. 긴 primary key는 clustered leaf뿐 아니라 모든 secondary leaf에 반복 저장되므로, secondary index 크기와 fan-out에도 영향을 준다.

## 3. 한 건 탐색의 실행 경로

`WHERE order_id = 9001`처럼 unique key 한 건을 찾는 경로를 단순화하면 다음과 같다.

1. root page에서 key 범위를 비교한다.
2. 필요한 branch page를 선택하여 다음 level로 내려간다.
3. leaf page에서 index record를 찾는다.
4. clustered index라면 row를 반환한다.
5. secondary index이고 query가 covering되지 않으면 leaf에 저장된 primary key로 clustered index를 다시 탐색한다.
6. MVCC visibility와 residual predicate를 검사하고 결과를 반환한다.

Tree height를 `H`, secondary index height를 `Hs`, clustered index height를 `Hc`라고 하자. 논리 경로의 개념적 상한을 단순화하면 clustered point lookup은 약 `H`, non-covering secondary lookup은 약 `Hs + Hc`가 된다. 이것은 비용 모델 전체가 아니다. 비교 연산, latch, MVCC, page decompression, Buffer Pool miss, storage latency, 반환 row 수가 실제 지연 시간에 함께 영향을 준다.

특히 non-unique secondary 조건으로 `N`개 row를 찾으면 clustered lookup이 최대 `N`회 발생할 수 있다. primary key 순서가 secondary leaf 순서와 크게 다르면 clustered page 접근도 흩어진다. optimizer가 넓은 범위에서 인덱스보다 table scan을 선택할 수 있는 이유가 여기에 있다.

## 4. Range scan의 비용은 height보다 leaf 방문량이 지배한다

Point lookup에서는 tree height가 중요한 직관을 제공한다. 반면 range scan은 시작점을 찾는 `H`번 안팎의 탐색 이후 얼마나 많은 leaf page와 record를 연속해서 읽는지가 더 중요하다.

범위가 반환하는 record 수를 `N`, 한 leaf page의 유효 record 수를 `R`이라고 단순화하면 leaf 방문량은 대략 `N / R`에 비례한다. key가 넓고 row가 커지거나 page fragmentation이 심해 `R`이 줄면 같은 건수를 읽어도 더 많은 page가 필요하다. non-covering secondary range scan은 여기에 clustered lookup 비용까지 더해진다.

다음 세 query는 모두 인덱스를 사용할 수 있지만 비용 특성은 다르다.

```text
-- unique point lookup: 좁은 탐색 경로 한 번
SELECT * FROM orders WHERE order_id = ?;

-- covering range scan: secondary leaf를 연속해서 읽고 종료
SELECT order_id, created_at
FROM orders
WHERE created_at >= ? AND created_at < ?;

-- non-covering range scan: secondary leaf + 다수의 clustered lookup
SELECT order_id, created_at, payload
FROM orders
WHERE created_at >= ? AND created_at < ?;
```

실제 운영에서는 “`type=range`이므로 빠르다”가 아니라 예상·실제 row 수, covering 여부, leaf 접근 범위, random clustered lookup 가능성을 함께 확인해야 한다.

## 5. Page size와 fan-out

InnoDB의 일반적인 page size는 16 KiB이지만 서버 초기화 방식에 따라 다를 수 있다. 다음 query는 실행 중인 서버의 버전과 page size를 확인한다.

```sql
SELECT VERSION() AS mysql_version,
       @@innodb_page_size AS innodb_page_size_bytes;
```

실행 결과(MySQL 8.0.x):

```text
mysql> SELECT VERSION() AS mysql_version,
    ->        @@innodb_page_size AS innodb_page_size_bytes;

+---------------+------------------------+
| mysql_version | innodb_page_size_bytes |
+---------------+------------------------+
| 8.0.46        |                  16384 |
+---------------+------------------------+
1 row in set (0.00 sec)
```

Page 하나에 들어가는 entry 수는 대략 다음 요소에 좌우된다.

- index key의 byte 길이
- secondary leaf에 함께 저장되는 primary key 길이
- variable-length column의 실제 값 길이
- record header와 page directory overhead
- page가 얼마나 채워져 있는지
- compression 사용 여부와 record 형식

예를 들어 branch entry를 평균 수십 byte로 가정하면 16 KiB page 하나가 수백 개 child를 가리킬 수 있다. 이처럼 fan-out이 크기 때문에 수백만 건 인덱스도 비교적 낮은 height를 유지할 수 있다. 다만 “항상 3 level”과 같은 고정 규칙은 없다. key width, page utilization, row 수, 인덱스 종류에 따라 달라진다.

## 6. 재현 예제: point lookup과 range scan 비교

다음 예제는 primary key와 `(region_code, created_at, id)` 보조 인덱스를 만든다. 보조 인덱스에 `id`를 명시했지만 InnoDB secondary record에는 primary key가 원래 포함된다. 여기서는 column 순서와 covering 의도를 독자가 쉽게 확인할 수 있도록 DDL에 드러냈다.

```sql
DROP TABLE IF EXISTS btree_demo;
CREATE TABLE btree_demo (
    id BIGINT NOT NULL,
    region_code CHAR(2) NOT NULL,
    created_at DATETIME NOT NULL,
    amount DECIMAL(12,2) NOT NULL,
    note VARCHAR(200) NOT NULL,
    PRIMARY KEY (id),
    KEY ix_region_created_id (region_code, created_at, id)
) ENGINE=InnoDB;

SET SESSION cte_max_recursion_depth = 5000;
INSERT INTO btree_demo (id, region_code, created_at, amount, note)
WITH RECURSIVE seq AS (
    SELECT 1 AS n
    UNION ALL
    SELECT n + 1 FROM seq WHERE n < 4000
)
SELECT n,
       CASE MOD(n, 4)
           WHEN 0 THEN 'AP'
           WHEN 1 THEN 'EU'
           WHEN 2 THEN 'NA'
           ELSE 'SA'
       END,
       TIMESTAMP('2026-01-01 00:00:00') + INTERVAL n MINUTE,
       n * 1.25,
       RPAD(CONCAT('row-', n), 80, 'x')
FROM seq;

ANALYZE TABLE btree_demo;
SELECT COUNT(*) AS inserted_rows FROM btree_demo;
```

실행 결과(MySQL 8.0.x):

```text
mysql> DROP TABLE IF EXISTS btree_demo;

Query OK, 0 rows affected (0.00 sec)

mysql> CREATE TABLE btree_demo (
    ->     id BIGINT NOT NULL,
    ->     region_code CHAR(2) NOT NULL,
    ->     created_at DATETIME NOT NULL,
    ->     amount DECIMAL(12,2) NOT NULL,
    ->     note VARCHAR(200) NOT NULL,
    ->     PRIMARY KEY (id),
    ->     KEY ix_region_created_id (region_code, created_at, id)
    -> ) ENGINE=InnoDB;

Query OK, 0 rows affected (0.00 sec)

mysql> SET SESSION cte_max_recursion_depth = 5000;

Query OK, 0 rows affected (0.00 sec)

mysql> INSERT INTO btree_demo (id, region_code, created_at, amount, note)
    -> WITH RECURSIVE seq AS (
    ->     SELECT 1 AS n
    ->     UNION ALL
    ->     SELECT n + 1 FROM seq WHERE n < 4000
    -> )
    -> SELECT n,
    ->        CASE MOD(n, 4)
    ->            WHEN 0 THEN 'AP'
    ->            WHEN 1 THEN 'EU'
    ->            WHEN 2 THEN 'NA'
    ->            ELSE 'SA'
    ->        END,
    ->        TIMESTAMP('2026-01-01 00:00:00') + INTERVAL n MINUTE,
    ->        n * 1.25,
    ->        RPAD(CONCAT('row-', n), 80, 'x')
    -> FROM seq;

Query OK, 4000 rows affected (0.06 sec)
Records: 4000  Duplicates: 0  Warnings: 0

mysql> ANALYZE TABLE btree_demo;

+----------------------------+---------+----------+----------+
| Table                      | Op      | Msg_type | Msg_text |
+----------------------------+---------+----------+----------+
| mysql_tech_note.btree_demo | analyze | status   | OK       |
+----------------------------+---------+----------+----------+
1 row in set (0.02 sec)

mysql> SELECT COUNT(*) AS inserted_rows FROM btree_demo;

+---------------+
| inserted_rows |
+---------------+
|          4000 |
+---------------+
1 row in set (0.00 sec)
```

### 6.1 Clustered primary key point lookup

```sql
EXPLAIN
SELECT id, region_code, created_at, amount, note
FROM btree_demo
WHERE id = 2400;
```

실행 결과(MySQL 8.0.x):

```text
mysql> EXPLAIN
    -> SELECT id, region_code, created_at, amount, note
    -> FROM btree_demo
    -> WHERE id = 2400;

+----+-------------+------------+------------+-------+---------------+---------+---------+-------+------+----------+-------+
| id | select_type | table      | partitions | type  | possible_keys | key     | key_len | ref   | rows | filtered | Extra |
+----+-------------+------------+------------+-------+---------------+---------+---------+-------+------+----------+-------+
|  1 | SIMPLE      | btree_demo | NULL       | const | PRIMARY       | PRIMARY | 8       | const |    1 |   100.00 | NULL  |
+----+-------------+------------+------------+-------+---------------+---------+---------+-------+------+----------+-------+
1 row in set (0.01 sec)
```

`type=const`와 `key=PRIMARY`는 unique primary key로 한 row를 찾는 계획을 뜻한다. InnoDB는 primary B+Tree의 root에서 leaf로 내려가며, leaf record에 row 전체가 있으므로 별도의 table lookup이 필요하지 않다.

### 6.2 Covering secondary range scan

```sql
EXPLAIN
SELECT region_code, created_at, id
FROM btree_demo
WHERE region_code = 'AP'
  AND created_at >= '2026-01-02 00:00:00'
  AND created_at <  '2026-01-02 12:00:00';
```

실행 결과(MySQL 8.0.x):

```text
mysql> EXPLAIN
    -> SELECT region_code, created_at, id
    -> FROM btree_demo
    -> WHERE region_code = 'AP'
    ->   AND created_at >= '2026-01-02 00:00:00'
    ->   AND created_at <  '2026-01-02 12:00:00';

+----+-------------+------------+------------+-------+----------------------+----------------------+---------+------+------+----------+--------------------------+
| id | select_type | table      | partitions | type  | possible_keys        | key                  | key_len | ref  | rows | filtered | Extra                    |
+----+-------------+------------+------------+-------+----------------------+----------------------+---------+------+------+----------+--------------------------+
|  1 | SIMPLE      | btree_demo | NULL       | range | ix_region_created_id | ix_region_created_id | 13      | NULL |  180 |   100.00 | Using where; Using index |
+----+-------------+------------+------------+-------+----------------------+----------------------+---------+------+------+----------+--------------------------+
1 row in set (0.00 sec)
```

선택 column이 모두 `ix_region_created_id` leaf에서 해결되므로 실행 계획의 `Extra`에 `Using index`가 나타날 수 있다. 이는 “인덱스를 사용했다”는 일반적 의미가 아니라, 이 query가 secondary leaf만으로 필요한 column을 충족하는 covering access임을 뜻한다.

### 6.3 Non-covering secondary range scan

```sql
EXPLAIN
SELECT region_code, created_at, id, amount, note
FROM btree_demo
WHERE region_code = 'AP'
  AND created_at >= '2026-01-02 00:00:00'
  AND created_at <  '2026-01-02 12:00:00';
```

실행 결과(MySQL 8.0.x):

```text
mysql> EXPLAIN
    -> SELECT region_code, created_at, id, amount, note
    -> FROM btree_demo
    -> WHERE region_code = 'AP'
    ->   AND created_at >= '2026-01-02 00:00:00'
    ->   AND created_at <  '2026-01-02 12:00:00';

+----+-------------+------------+------------+-------+----------------------+----------------------+---------+------+------+----------+-----------------------+
| id | select_type | table      | partitions | type  | possible_keys        | key                  | key_len | ref  | rows | filtered | Extra                 |
+----+-------------+------------+------------+-------+----------------------+----------------------+---------+------+------+----------+-----------------------+
|  1 | SIMPLE      | btree_demo | NULL       | range | ix_region_created_id | ix_region_created_id | 13      | NULL |  180 |   100.00 | Using index condition |
+----+-------------+------------+------------+-------+----------------------+----------------------+---------+------+------+----------+-----------------------+
1 row in set (0.00 sec)
```

Predicate와 range는 같지만 `amount`, `note`가 secondary leaf에 없다. 일치한 secondary record마다 primary key `id`를 이용해 clustered index에서 row를 찾아야 한다. 실행 계획의 선택 index가 같아도 covering query와 실제 page 접근 비용이 같지 않은 이유다.

## 7. InnoDB metadata로 인덱스 구조 확인하기

`information_schema.INNODB_INDEXES`의 `PAGE_NO`는 해당 인덱스 B+Tree root page 번호다. 이 값을 인덱스의 전체 page 수나 height로 해석해서는 안 된다. `mysql.innodb_index_stats`의 `size`와 `n_leaf_pages`는 persistent statistics가 추정한 전체 page와 leaf page 관련 값이며, 통계 갱신 시점과 sampling의 영향을 받는다.

```sql
SELECT i.NAME AS index_name,
       i.TYPE AS index_type,
       i.N_FIELDS AS key_fields,
       i.PAGE_NO AS root_page_no,
       i.SPACE AS space_id
FROM information_schema.INNODB_INDEXES AS i
JOIN information_schema.INNODB_TABLES AS t
  ON t.TABLE_ID = i.TABLE_ID
WHERE t.NAME = 'mysql_tech_note/btree_demo'
ORDER BY i.NAME;

SELECT index_name,
       MAX(CASE WHEN stat_name = 'size' THEN stat_value END) AS total_pages,
       MAX(CASE WHEN stat_name = 'n_leaf_pages' THEN stat_value END) AS leaf_pages
FROM mysql.innodb_index_stats
WHERE database_name = 'mysql_tech_note'
  AND table_name = 'btree_demo'
  AND stat_name IN ('size', 'n_leaf_pages')
GROUP BY index_name
ORDER BY index_name;
```

실행 결과(MySQL 8.0.x):

```text
mysql> SELECT i.NAME AS index_name,
    ->        i.TYPE AS index_type,
    ->        i.N_FIELDS AS key_fields,
    ->        i.PAGE_NO AS root_page_no,
    ->        i.SPACE AS space_id
    -> FROM information_schema.INNODB_INDEXES AS i
    -> JOIN information_schema.INNODB_TABLES AS t
    ->   ON t.TABLE_ID = i.TABLE_ID
    -> WHERE t.NAME = 'mysql_tech_note/btree_demo'
    -> ORDER BY i.NAME;

+----------------------+------------+------------+--------------+----------+
| index_name           | index_type | key_fields | root_page_no | space_id |
+----------------------+------------+------------+--------------+----------+
| ix_region_created_id |          0 |          3 |            5 |        2 |
| PRIMARY              |          3 |          7 |            4 |        2 |
+----------------------+------------+------------+--------------+----------+
2 rows in set (0.00 sec)

mysql> SELECT index_name,
    ->        MAX(CASE WHEN stat_name = 'size' THEN stat_value END) AS total_pages,
    ->        MAX(CASE WHEN stat_name = 'n_leaf_pages' THEN stat_value END) AS leaf_pages
    -> FROM mysql.innodb_index_stats
    -> WHERE database_name = 'mysql_tech_note'
    ->   AND table_name = 'btree_demo'
    ->   AND stat_name IN ('size', 'n_leaf_pages')
    -> GROUP BY index_name
    -> ORDER BY index_name;

+----------------------+-------------+------------+
| index_name           | total_pages | leaf_pages |
+----------------------+-------------+------------+
| PRIMARY              |          97 |         33 |
| ix_region_created_id |           9 |          8 |
+----------------------+-------------+------------+
2 rows in set (0.00 sec)
```

이 통계는 capacity trend와 인덱스 간 상대 크기를 관찰하는 데 유용하지만, 한 번의 snapshot만으로 fragmentation이나 정확한 tree height를 단정하는 도구는 아니다. 운영 판단에는 데이터 증가 추세, query latency, Buffer Pool 지표, 실행 계획을 함께 사용해야 한다.

예제 테이블은 다음과 같이 정리한다.

```sql
DROP TABLE btree_demo;
```

실행 결과(MySQL 8.0.x):

```text
mysql> DROP TABLE btree_demo;

Query OK, 0 rows affected (0.00 sec)
```

## 8. Page split과 삽입 패턴

Leaf page에 새 record를 넣을 공간이 부족하면 InnoDB는 page split을 수행할 수 있다. 새 page를 확보하고 record를 분배하며 parent의 separator 정보도 갱신한다. split은 단순 row append보다 많은 page 변경을 만들고 redo, dirty page, latch 경쟁에 영향을 줄 수 있다.

### 8.1 증가형 primary key

증가형 key는 주로 오른쪽 끝 leaf에 삽입된다. locality가 좋고 page 사용 패턴을 예측하기 쉽지만, 매우 높은 동시 쓰기에서는 rightmost page가 hot spot이 될 수 있다. `AUTO_INCREMENT` 자체의 동시성 제어와 B+Tree leaf 경쟁은 구분해서 관찰해야 한다.

### 8.2 무작위 primary key

완전히 무작위인 넓은 key는 tree 전반의 leaf에 삽입을 분산한다. write locality가 낮아지고 page split, Buffer Pool churn, secondary index 비대화가 늘 수 있다. 특히 primary key가 길면 그 값이 모든 secondary leaf에 포함된다는 점이 중요하다.

### 8.3 순차성이 있는 분산형 key

시간 순서 특성을 가진 ID는 locality와 분산 사이의 절충안이 될 수 있다. 그러나 application에서 사용하는 ID 표현, collision 처리, 정렬 semantics, byte width까지 검토해야 한다. 단지 “UUID보다 빠르다”는 설명으로 key 설계를 결정해서는 안 된다.

## 9. Buffer Pool과 물리 I/O를 구분한다

B+Tree 탐색은 논리 page 접근 경로다. page가 Buffer Pool에 있으면 storage read 없이 memory에서 처리할 수 있다. page가 없으면 storage에서 읽어와야 하며, 읽을 공간을 확보하기 위한 eviction도 발생할 수 있다.

운영 해석은 다음 세 층을 구분하는 것이 좋다.

1. **Access path**: optimizer가 어떤 index와 scan 방식을 선택했는가.
2. **Logical work**: 몇 개의 index record, row, page를 검사했는가.
3. **Physical work**: Buffer Pool miss와 storage I/O가 얼마나 발생했는가.

`EXPLAIN`은 주로 첫 번째와 estimated row를 보여준다. `EXPLAIN ANALYZE`는 iterator별 실제 실행 시간과 row·loop 수를 보여주지만 page read를 직접 모두 설명하지는 않는다. Performance Schema statement 지표, `INNODB_METRICS`, Buffer Pool 상태, storage latency를 함께 관찰해야 한다.

운영 시스템에서 진단할 때는 query 실행 전후의 global counter 차이를 단일 query 비용으로 곧바로 귀속하지 않는다. 같은 시간에 다른 session도 counter를 증가시킬 수 있기 때문이다. 부하 재현 환경, statement digest, 짧은 관찰 구간, 반복 측정을 사용한다.

## 10. Optimizer가 인덱스를 선택하지 않을 수 있는 이유

인덱스가 존재해도 optimizer는 table scan이 더 저렴하다고 판단할 수 있다.

- predicate가 많은 row를 선택한다.
- secondary index가 covering되지 않아 clustered lookup이 많이 필요하다.
- 통계가 실제 분포를 제대로 반영하지 못한다.
- function이나 implicit conversion 때문에 predicate가 원하는 key range를 만들지 못한다.
- composite index의 leftmost prefix와 조건 순서가 맞지 않는다.
- 작은 테이블이어서 순차적인 전체 scan이 더 단순하다.

`FORCE INDEX`로 계획을 고정하기 전에 통계, cardinality, query shape, covering 가능성을 확인해야 한다. 강제 hint는 현재 데이터 분포에서 빠르더라도 성장 이후 불리한 계획을 고정할 수 있다.

## 11. Aurora MySQL에서의 운영 해석

Aurora MySQL도 SQL layer와 InnoDB 호환 access method 관점에서 clustered·secondary B+Tree의 기본 의미를 유지한다. 따라서 key width, covering index, range selectivity, clustered lookup에 관한 설계 원칙은 그대로 중요하다. 다만 storage가 인스턴스 로컬 디스크인 일반 MySQL과 동일하다고 가정해서는 안 된다.

- Buffer cache는 query를 실행하는 DB instance 관점에서 해석한다. writer와 reader는 동일한 query라도 cache 온도가 다를 수 있다.
- reader별 workload와 replica lag뿐 아니라 reader에서의 page read latency도 별도로 관찰한다.
- failover나 instance 교체 전후에는 cache 상태 변화가 latency에 미치는 영향을 고려한다.
- Aurora의 storage·I/O 지표와 Performance Insights 또는 Database Insights의 query 지표를 함께 본다.
- I/O 비용 모델은 선택한 Aurora 구성과 요금 방식에 따라 달라질 수 있으므로, 인덱스 추가를 query latency뿐 아니라 write amplification과 storage footprint 측면에서도 평가한다.

Aurora에서 storage 계층이 다르다고 해서 불필요한 secondary index의 비용이 사라지는 것은 아니다. secondary index는 write마다 유지되어야 하고, 긴 primary key는 secondary leaf를 키우며, 낮은 selectivity의 non-covering scan은 여전히 많은 논리 작업을 만든다.

## 12. 흔한 오해와 주의점

### “B+Tree 탐색은 O(log N)이므로 데이터가 커져도 항상 빠르다”

Point lookup의 탐색 level은 천천히 증가하지만, range query의 반환 건수와 clustered lookup 수는 별개다. low-selectivity predicate는 B+Tree를 사용해도 많은 leaf와 row를 읽는다.

### “EXPLAIN에 key가 나오면 충분하다”

선택된 `key`만 보지 말고 `type`, `key_len`, `rows`, `filtered`, `Extra`, covering 여부를 함께 확인한다. 가능하면 대표 데이터에서 `EXPLAIN ANALYZE`로 실제 row와 loop를 검증한다.

### “Root page 번호로 tree depth를 알 수 있다”

`INNODB_INDEXES.PAGE_NO`는 root page의 식별 번호이지 depth나 page count가 아니다. persistent index statistics의 `size`, `n_leaf_pages`도 정확한 실시간 height로 오해하지 않는다.

### “Primary key가 길어도 primary lookup만 보면 된다”

InnoDB secondary leaf는 primary key를 row locator로 포함한다. 긴 primary key는 secondary index가 많을수록 storage와 memory에 반복적인 부담을 준다.

### “인덱스를 많이 만들면 읽기가 모두 빨라진다”

각 secondary index는 insert, update, delete 때 유지해야 한다. 더 많은 B+Tree는 redo, dirty page, Buffer Pool 점유, DDL 시간, backup footprint를 증가시킨다. 실제 workload에서 사용되는 access path인지 확인해야 한다.

## 13. 설계·진단 체크리스트

### 인덱스 설계

- [ ] Primary key가 안정적이며 필요 이상으로 넓지 않은가?
- [ ] Composite index가 주요 predicate의 equality·range·order 요구와 맞는가?
- [ ] 자주 실행되는 query는 필요한 범위에서 covering할 수 있는가?
- [ ] covering을 위해 큰 column을 과도하게 추가해 fan-out을 낮추지 않았는가?
- [ ] 중복되거나 사용되지 않는 secondary index의 write 비용을 검토했는가?
- [ ] 증가형·무작위 key의 삽입 locality와 동시성 특성을 함께 평가했는가?

### 실행 계획 점검

- [ ] `key`뿐 아니라 `type`, `key_len`, `rows`, `filtered`, `Extra`를 확인했는가?
- [ ] point lookup, range scan, full scan을 구분했는가?
- [ ] `Using index`가 covering access를 의미하는 문맥인지 확인했는가?
- [ ] non-covering 결과 건수만큼 clustered lookup이 늘 수 있음을 반영했는가?
- [ ] estimate와 실제 데이터 분포가 다르면 통계와 `EXPLAIN ANALYZE`를 확인했는가?

### 운영 관측

- [ ] 논리 page 탐색과 실제 storage I/O를 구분했는가?
- [ ] Buffer Pool warm·cold 상태를 구분하여 비교했는가?
- [ ] global counter 변화를 다른 session의 작업과 혼동하지 않았는가?
- [ ] index size와 leaf page 추세를 시간 축으로 관찰했는가?
- [ ] Aurora에서는 writer와 reader의 cache·latency를 각각 확인했는가?

## 14. 맺음말

InnoDB B+Tree의 성능을 이해하려면 “인덱스를 탔다”는 표현을 root에서 leaf까지의 탐색, leaf range 이동, secondary-to-clustered lookup, Buffer Pool과 storage I/O로 분해해야 한다. Point lookup은 낮은 tree height와 큰 fan-out의 이점을 직접 얻지만, 넓은 range와 non-covering secondary scan은 방문 leaf 수와 clustered lookup 수가 비용을 지배할 수 있다.

다음 단계에서는 composite index의 column 순서, leftmost prefix, `key_len`을 연결해 살펴보면 optimizer가 어떤 검색 범위를 만들 수 있는지 더 구체적으로 이해할 수 있다. B+Tree page 구조는 그 판단을 뒷받침하는 기초 모델이다.