인덱스 구조 - B*Tree 와 클러스터링 팩터

이 장에서 배우는 것

앞 장에서는 SQL 한 문장이 블록을 몇 번 읽는지, 그 읽기가 논리 읽기인지 물리 읽기인지를 살펴봤다. 이번 장은 그 블록 읽기 횟수를 결정하는 자료구조인 B*Tree(비트리) 인덱스를 다룬다. 인덱스는 "있으면 빠르다"가 아니라 "어떻게 만들어졌고 테이블과 어떤 관계에 있는가"에 따라 결과가 크게 달라진다. 특히 클러스터링 팩터(clustering factor)는 같은 선택도의 조건이라도 테이블 액세스 비용을 수십 배 차이 나게 만드는 값이다.

• B*Tree 인덱스의 루트·브랜치·리프 구조와 ROWID 역할을 설명할 수 있다
• USER_INDEXES 의 BLEVEL·LEAF_BLOCKS·CLUSTERING_FACTOR 값을 읽고 의미를 해석할 수 있다
• 인덱스 탐색 비용을 어림 계산하는 공식을 이해하고 직접 계산할 수 있다
• 클러스터링 팩터가 낮은 인덱스와 높은 인덱스가 실행계획 Cost 에 어떻게 다르게 반영되는지 설명할 수 있다

문제 상황

온라인 서점의 주문 테이블 ORDERS 는 1천만 건 규모다. 배치 담당자가 회원별 주문 내역 조회를 빠르게 하려고 MEMBER_ID 에 인덱스를 만들었다. 그런데 비슷한 비율의 행을 가져오는 주문일자 조건 조회보다 훨씬 느렸다. 인덱스가 분명히 있고 실행계획에도 INDEX RANGE SCAN 이 찍히는데 왜 느린지 담당자는 이해하지 못했다. 이 장에서 다룰 예제는 그 원인을 숫자로 확인하는 데 필요한 최소 구조만 남긴 것이다.

이 장에서 사용하는 ORDERS 테이블 구조

컬럼명	자료형	인덱스
ORDER_ID	NUMBER	기본키(PK)
MEMBER_ID	NUMBER	IX_ORDERS_MEMBER_ID
ORDER_DATE	DATE	IX_ORDERS_ORDER_DATE
STATUS	VARCHAR2(10)	없음
TOTAL_AMOUNT	NUMBER(10)	없음

B*Tree 인덱스의 구조

오라클의 일반 인덱스는 대부분 B*Tree 구조다. 키 값을 정렬된 상태로 유지하면서 탐색·삽입·삭제를 모두 비슷한 비용으로 처리하도록 설계된 트리다.

루트에서 리프까지

루트 블록(root block)은 트리의 진입점이다. 루트는 자식 블록의 범위를 가리키는 항목만 담고 있어서, "이 값은 왼쪽 자식에, 저 값은 오른쪽 자식에 있다"는 안내판 역할만 한다. 브랜치 블록(branch block)은 루트와 리프 사이에 있는 중간 단계로, 트리가 커질수록 여러 단계로 늘어날 수 있다. 리프 블록(leaf block)은 실제 키 값과 그 키를 가진 행의 위치 정보가 정렬된 채로 쌍을 이뤄 저장되는 곳이다. 리프 블록끼리는 키 순서대로 양방향으로 연결되어 있어서, 범위 조건을 처리할 때 리프 블록만 옆으로 훑으면 된다.

중요한 점은 1천만 건짜리 테이블이라도 트리 높이가 그리 깊어지지 않는다는 것이다. 한 브랜치 블록이 수백 개의 자식을 가리킬 수 있기 때문에, 보통은 루트에서 리프까지 2~4단계면 충분하다. USER_INDEXES.BLEVEL 은 루트부터 리프 직전 단계까지의 층 수를 나타내는 값으로, 트리가 얼마나 깊은지 바로 확인할 수 있다.

ROWID 가 가리키는 것

리프 블록의 각 항목은 키 값과 함께 ROWID(행 위치 식별자)를 담고 있다. ROWID 는 그 행이 어느 데이터 파일, 어느 블록, 그 블록 안 몇 번째 위치에 있는지를 나타내는 값이다. 인덱스로 원하는 키를 찾은 다음에는 이 ROWID 를 이용해 테이블 블록을 곧바로 읽으면 되므로, 테이블 전체를 훑지 않아도 된다. 문제는 이 "곧바로 읽는" 과정이 조건을 만족하는 행 수만큼 반복된다는 점이고, 그 반복이 몇 번의 물리적인 블록 읽기로 이어지는지를 결정하는 값이 바로 클러스터링 팩터다.

인덱스 탐색 비용 계산

옵티마이저(optimizer)가 인덱스 레인지 스캔의 비용을 어림잡는 방식은 대략 다음 식으로 이해할 수 있다.

비용 ≈ BLEVEL + ceil(LEAF_BLOCKS × 선택도) + ceil(CLUSTERING_FACTOR × 선택도)

첫 항 BLEVEL 은 루트에서 리프 직전까지 내려가는 단계 수로, 보통 1~2 정도라 전체 비용에서 차지하는 비중이 작다. 둘째 항은 조건을 만족하는 리프 블록을 읽는 비용이다. 셋째 항은 그 리프가 가리키는 ROWID 를 따라가며 테이블 블록을 읽는 비용인데, 이때 실제로 곱해지는 값이 테이블 전체 블록 수가 아니라 클러스터링 팩터(clustering factor)라는 점이 핵심이다.

예를 들어 ORDER_DATE 인덱스의 LEAF_BLOCKS 가 209, CLUSTERING_FACTOR 가 604 이고, 조건을 만족하는 행이 전체의 2.1%(2100건)라면 다음과 같이 어림 계산할 수 있다.

인덱스 읽기 비용 = 1 + ceil(209 × 0.021) = 1 + 5 = 6
테이블 읽기 포함 총 비용 = 6 + ceil(604 × 0.021) = 6 + 13 = 19

같은 방식으로 클러스터링 팩터가 훨씬 큰 인덱스를 계산해 보면 왜 문제 상황에서 본 것과 같은 차이가 나는지 뒤에서 직접 확인한다.

클러스터링 팩터가 테이블 액세스 비용에 미치는 영향

클러스터링 팩터는 인덱스 리프 블록을 키 순서대로 읽어 나갈 때, ROWID 가 가리키는 테이블 블록이 직전 행과 다른 블록으로 바뀌는 횟수를 어림잡은 값이다. 행이 인덱스 키 순서와 비슷하게 테이블에 물리적으로 쌓여 있으면 이 값은 테이블 블록 수에 가깝게 낮아지고, 키 순서와 무관하게 이곳저곳에 흩어져 있으면 행 수에 가깝게 높아진다.

ORDERS 테이블은 주문이 들어온 순서대로 쌓이므로 ORDER_DATE 는 삽입 순서와 거의 일치한다. 반면 MEMBER_ID 는 어느 회원이 언제 주문할지 알 수 없으므로 삽입 순서와 무관하게 뒤섞인다. 결과적으로 같은 테이블이라도 어떤 컬럼에 인덱스를 만드느냐에 따라 클러스터링 팩터가 완전히 다르게 나온다.

클러스터링 팩터가 높은 인덱스는 쓸모없는 것이 아니다. 조건이 아주 적은 행만 골라낼 때는 어차피 읽는 테이블 블록 수 자체가 적어서 차이가 크게 드러나지 않는다. 문제는 조건을 만족하는 행 비율이 커질수록, 즉 선택도가 나빠질수록 클러스터링 팩터가 높은 인덱스의 비용이 급격히 불어난다는 점이다.

오라클과 MySQL 차이

테이블 저장 구조 자체가 다르기 때문에 클러스터링 팩터라는 통계의 의미도 서로 다르게 이해해야 한다.

클러스터링 팩터와 관련해 오라클과 MySQL이 다른 점

항목	Oracle 19c	MySQL 8(InnoDB)
테이블 저장 구조	힙(heap) 구조, 기본키 없이도 저장 가능	기본키 기준 클러스터드 인덱스로 저장
보조 인덱스가 담는 값	ROWID(블록 위치)	기본키 값
클러스터링 팩터 확인	USER_INDEXES.CLUSTERING_FACTOR 로 직접 조회	별도 통계 없음, 실행계획과 실측으로 유추
보조 인덱스 크기	기본키 길이와 무관	기본키가 길수록 모든 보조 인덱스가 커짐

완성 코드

1천만 건 규모의 실제 운영 테이블을 그대로 실습하기는 어려우므로, 같은 원리가 드러나는 10만 건 규모로 축소한 스크립트를 사용한다. Oracle 19c SQL*Plus 에서 순서대로 실행할 수 있다.

-- ① 이전 실습 객체 정리 (없으면 무시)
BEGIN
   EXECUTE IMMEDIATE 'DROP TABLE orders PURGE';
EXCEPTION
   WHEN OTHERS THEN
      IF SQLCODE != -942 THEN
         RAISE;
      END IF;
END;
/

-- ② 실습용 ORDERS 테이블과 인덱스 두 개 생성
CREATE TABLE orders (
    order_id      NUMBER        PRIMARY KEY,
    member_id     NUMBER        NOT NULL,
    order_date    DATE          NOT NULL,
    status        VARCHAR2(10)  NOT NULL,
    total_amount  NUMBER(10)    NOT NULL
);

CREATE INDEX ix_orders_order_date ON orders (order_date);
CREATE INDEX ix_orders_member_id  ON orders (member_id);

-- ③ 10만 건 적재. member_id 는 뒤섞이게, order_date 는 입력 순서와 비슷하게 증가하도록 만든다
BEGIN
    FOR i IN 1 .. 100000 LOOP
        INSERT INTO orders (order_id, member_id, order_date, status, total_amount)
        VALUES (
            i,
            MOD(i * 7919, 20000) + 1,
            DATE '2024-01-01' + TRUNC((i - 1) / 300),
            CASE WHEN MOD(i, 7) = 0 THEN 'CANCELLED' ELSE 'PAID' END,
            MOD(i * 37, 80000) + 9000
        );
    END LOOP;
    COMMIT;
END;
/

-- ④ 통계 수집 후 클러스터링 팩터 확인
EXEC DBMS_STATS.GATHER_TABLE_STATS(ownname => USER, tabname => 'ORDERS', cascade => TRUE);

SELECT index_name, blevel, leaf_blocks, clustering_factor, num_rows
FROM   user_indexes
WHERE  table_name = 'ORDERS' AND index_name LIKE 'IX_ORDERS%'
ORDER  BY index_name;

-- ⑤ 전체의 1~2%를 반환하는 두 조건의 실행계획 비교
EXPLAIN PLAN FOR
SELECT /*+ INDEX(o ix_orders_order_date) */ order_id, total_amount
FROM   orders o
WHERE  order_date BETWEEN DATE '2024-06-01' AND DATE '2024-06-07';

SELECT * FROM TABLE(DBMS_XPLAN.DISPLAY(NULL, NULL, 'BASIC ROWS COST'));

EXPLAIN PLAN FOR
SELECT /*+ INDEX(o ix_orders_member_id) */ order_id, total_amount
FROM   orders o
WHERE  member_id BETWEEN 1000 AND 1300;

SELECT * FROM TABLE(DBMS_XPLAN.DISPLAY(NULL, NULL, 'BASIC ROWS COST'));

줄별 해설

• ① 이전 실습에서 만든 ORDERS 가 남아 있으면 지우고, 없으면(ORA-00942) 조용히 넘어간다. 스크립트를 여러 번 실행해도 오류로 멈추지 않게 하기 위한 처리다.
• ② ORDER_DATE 와 MEMBER_ID 에 각각 단일 컬럼 인덱스를 하나씩 만든다. 두 인덱스가 같은 테이블, 같은 행 수를 대상으로 얼마나 다르게 동작하는지 비교하는 것이 이번 실습의 목적이다.
• ③ member_id 는 곱셈과 나머지 연산으로 뒤섞어 삽입 순서와 무관하게 만들고, order_date 는 300건마다 하루씩 늘려 삽입 순서와 거의 일치하게 만든다. 실무의 두 상황(입력 순서를 따라가는 컬럼과 그렇지 않은 컬럼)을 그대로 재현한 것이다.
• ④ 통계를 최신으로 만든 뒤 CLUSTERING_FACTOR 를 직접 확인한다. 대량 적재 직후 통계를 갱신하지 않으면 이 값이 예전 상태로 남아 실행계획이 잘못 세워질 수 있다.
• ⑤ 두 쿼리 모두 힌트로 각자의 인덱스를 쓰도록 강제하고, 비슷한 비율(약 1.5~2.1%)의 행을 반환하도록 조건을 맞췄다. 행 비율이 비슷한데도 Cost 가 얼마나 벌어지는지가 이번 실습의 핵심 관찰 포인트다.

실행 결과

클러스터링 팩터 조회 결과부터 확인한다.

SQL> SELECT index_name, blevel, leaf_blocks, clustering_factor, num_rows
  2  FROM   user_indexes
  3  WHERE  table_name = 'ORDERS' AND index_name LIKE 'IX_ORDERS%'
  4  ORDER  BY index_name;

INDEX_NAME                    BLEVEL LEAF_BLOCKS CLUSTERING_FACTOR   NUM_ROWS
------------------------------ ------ ----------- ----------------- ----------
IX_ORDERS_MEMBER_ID                 1         181             99150     100000
IX_ORDERS_ORDER_DATE                1         209               604     100000

ORDER_DATE 인덱스는 클러스터링 팩터가 테이블 블록 수와 비슷한 604, MEMBER_ID 인덱스는 전체 행 수(100000)에 거의 맞먹는 99150 이다. 두 실행계획을 비교하면 이 차이가 Cost 에 그대로 나타난다.

SQL> EXPLAIN PLAN FOR
  2  SELECT /*+ INDEX(o ix_orders_order_date) */ order_id, total_amount
  3  FROM   orders o
  4  WHERE  order_date BETWEEN DATE '2024-06-01' AND DATE '2024-06-07';

Explained.

SQL> SELECT * FROM TABLE(DBMS_XPLAN.DISPLAY(NULL, NULL, 'BASIC ROWS COST'));

PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
Plan hash value: 2451397620

--------------------------------------------------------------------------------------
| Id  | Operation                            | Name                  | Rows | Cost |
--------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                     |                       |      |   19 |
|   1 |  TABLE ACCESS BY INDEX ROWID BATCHED | ORDERS                | 2100 |   19 |
|*  2 |   INDEX RANGE SCAN                   | IX_ORDERS_ORDER_DATE  | 2100 |    6 |
--------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access("ORDER_DATE">=DATE '2024-06-01' AND "ORDER_DATE"<=DATE '2024-06-07')

SQL> EXPLAIN PLAN FOR
  2  SELECT /*+ INDEX(o ix_orders_member_id) */ order_id, total_amount
  3  FROM   orders o
  4  WHERE  member_id BETWEEN 1000 AND 1300;

Explained.

SQL> SELECT * FROM TABLE(DBMS_XPLAN.DISPLAY(NULL, NULL, 'BASIC ROWS COST'));

PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
Plan hash value: 3208514477

--------------------------------------------------------------------------------------
| Id  | Operation                            | Name                  | Rows | Cost |
--------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                     |                       |      | 1497 |
|   1 |  TABLE ACCESS BY INDEX ROWID BATCHED | ORDERS                | 1505 | 1497 |
|*  2 |   INDEX RANGE SCAN                   | IX_ORDERS_MEMBER_ID   | 1505 |    4 |
--------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access("MEMBER_ID">=1000 AND "MEMBER_ID"<=1300)

인덱스 자체를 읽는 비용(Id 2)은 6과 4로 큰 차이가 없다. 차이는 전부 테이블 액세스 단계(Id 1)에서 발생하며, 이는 앞서 계산한 어림값(19 와 1497)과 방향이 일치한다.

실무에서 자주 틀리는 것

선택도만 보고 인덱스 효율을 판단한다

조건을 만족하는 행 비율이 낮으니 인덱스를 쓰면 무조건 빠를 것이라 가정하고 힌트로 강제하는 경우가 많다. 클러스터링 팩터를 확인하지 않으면 오히려 풀 스캔보다 느린 계획을 강제하게 된다.

-- 잘못된 습관: 클러스터링 팩터를 확인하지 않고 무조건 힌트로 강제
SELECT /*+ INDEX(o ix_orders_member_id) */ *
FROM   orders o
WHERE  member_id BETWEEN 1 AND 5000;

-- 고친 방향: 인덱스를 쓰기 전에 클러스터링 팩터부터 확인
SELECT index_name, clustering_factor, num_rows
FROM   user_indexes
WHERE  table_name = 'ORDERS' AND index_name = 'IX_ORDERS_MEMBER_ID';
-- CLUSTERING_FACTOR 가 NUM_ROWS 에 가깝고 조건이 넓다면
-- 힌트를 빼고 옵티마이저 판단(풀 스캔 포함)에 맡긴다

대량 재적재 후 통계를 갱신하지 않는다

배치로 데이터를 다시 밀어 넣으면 물리적인 행 배치가 바뀌어 클러스터링 팩터도 달라지는데, 통계를 갱신하지 않으면 옵티마이저는 예전 값을 그대로 믿는다.

-- 잘못된 습관: 재적재만 하고 통계 갱신을 잊음
TRUNCATE TABLE orders;
-- 대량 INSERT ... (생략)
COMMIT;

-- 고친 코드: 재적재 직후 통계를 다시 수집
TRUNCATE TABLE orders;
-- 대량 INSERT ... (생략)
COMMIT;
EXEC DBMS_STATS.GATHER_TABLE_STATS(ownname => USER, tabname => 'ORDERS', cascade => TRUE);

MySQL 에서도 ROWID 기반 보조 인덱스를 가정한다

오라클 경험만으로 MySQL 인덱스를 설계하면 기본키를 길게 잡는 실수를 하기 쉽다. InnoDB 보조 인덱스는 ROWID 대신 기본키 값을 저장하므로, 기본키가 길수록 모든 보조 인덱스가 함께 커진다.

-- 잘못된 설계: 긴 문자열을 기본키로 사용
CREATE TABLE reviews (
    review_uuid VARCHAR(36) PRIMARY KEY,
    book_id     BIGINT NOT NULL,
    rating      TINYINT NOT NULL
);
CREATE INDEX ix_reviews_book_id ON reviews (book_id);
-- ix_reviews_book_id 의 각 항목마다 36바이트 PK 값을 함께 저장

-- 고친 설계: 짧은 대리키를 기본키로 두고 UUID 는 별도 컬럼으로 보관
CREATE TABLE reviews (
    review_id   BIGINT PRIMARY KEY,
    review_uuid VARCHAR(36) NOT NULL,
    book_id     BIGINT NOT NULL,
    rating      TINYINT NOT NULL
);
CREATE INDEX ix_reviews_book_id ON reviews (book_id);

클러스터링 팩터가 나쁘면 인덱스를 바로 버린다

클러스터링 팩터가 높다고 해서 그 인덱스가 항상 무용한 것은 아니다. 조건을 더 좁혀서 반환 행을 줄이거나, 자주 쓰는 컬럼을 인덱스에 포함해 테이블 접근 자체를 줄이는 방법이 먼저다.

-- 과잉 대응: 클러스터링 팩터가 나쁘다고 인덱스를 바로 제거
DROP INDEX ix_orders_member_id;

-- 대안: 조건을 좁히거나 필요한 컬럼을 인덱스에 포함해 테이블 접근을 줄인다
SELECT order_id, total_amount
FROM   orders
WHERE  member_id = :member_id
AND    order_date >= TRUNC(SYSDATE) - 90;

한눈에 보기

B*Tree 구조와 클러스터링 팩터 핵심 정리

항목	의미	확인 방법
루트/브랜치/리프	루트에서 브랜치를 거쳐 리프까지 내려가며 키를 찾는 트리 구조	실행계획의 INDEX RANGE SCAN
ROWID	리프에 저장된, 행의 물리적 위치 정보	테이블 액세스 단계에서 참조
BLEVEL	루트에서 리프 직전까지의 단계 수	USER_INDEXES.BLEVEL
LEAF_BLOCKS	인덱스가 차지하는 리프 블록 수	USER_INDEXES.LEAF_BLOCKS
CLUSTERING_FACTOR	인덱스 순서와 테이블 저장 순서가 어긋나는 정도	USER_INDEXES.CLUSTERING_FACTOR
탐색 비용 어림값	BLEVEL + 리프 읽기 + 테이블 읽기(CF 반영)	실행계획의 Cost 열

연습 문제

1. 리프 블록에 저장되는 두 가지 정보는 무엇이며, 리프 블록끼리 양방향으로 연결해 두는 이유는 무엇인가.
2. REVIEWS 테이블의 행 수가 500000건이고, BOOK_ID 인덱스의 LEAF_BLOCKS 가 730, CLUSTERING_FACTOR 가 463200, BLEVEL 이 1이다. 특정 BOOK_ID 조건이 전체의 0.4%(2000건)를 반환한다고 할 때, 인덱스 읽기 비용과 테이블 읽기를 포함한 총 비용을 어림 계산하라.
3. 같은 테이블에서 인덱스 A 의 CLUSTERING_FACTOR 가 테이블 블록 수와 비슷하고, 인덱스 B 의 CLUSTERING_FACTOR 가 전체 행 수와 비슷하다. 두 인덱스 중 어느 컬럼이 데이터 입력 순서와 더 비슷하게 저장되어 있다고 볼 수 있는가.
4. 대량 재적재 배치를 마친 다음 날부터 특정 조회 쿼리가 갑자기 느려졌다는 보고를 받았다. 인덱스는 그대로이고 쿼리도 바뀌지 않았다면 가장 먼저 의심해 볼 부분과 확인 방법을 서술하라.

정답과 해설

1. 리프 블록에는 정렬된 키 값과 그 키를 가진 행의 ROWID 가 쌍으로 저장된다. 양방향 연결은 범위 조건(BETWEEN, 부등호, ORDER BY 등)을 처리할 때 리프 블록을 순서대로 이어서 읽을 수 있게 하기 위함이다. 이 연결이 없다면 매번 브랜치로 되돌아가 다음 키를 다시 찾아야 한다.

2. 선택도는 2000/500000 = 0.004 다. 인덱스 읽기 비용은 1 + ceil(730 × 0.004) = 1 + 3 = 4, 테이블 읽기를 포함한 총 비용은 4 + ceil(463200 × 0.004) = 4 + 1853 = 1857 이다. 인덱스 자체를 읽는 비용은 작지만 클러스터링 팩터가 커서 테이블 접근 비용이 전체를 지배한다.

3. 인덱스 A 다. 클러스터링 팩터가 테이블 블록 수에 가깝다는 것은 인덱스를 순서대로 읽을 때 같은 테이블 블록에서 연속으로 여러 행을 찾는 경우가 많다는 뜻이며, 이는 그 컬럼 값이 입력 순서(물리적 저장 순서)와 비슷하게 증가한다는 의미다.

4. 가장 먼저 의심할 부분은 통계다. 재적재로 행의 물리적 배치가 바뀌면 클러스터링 팩터를 포함한 인덱스·테이블 통계가 달라지는데, DBMS_STATS 를 다시 수집하지 않았다면 옵티마이저는 예전 통계를 근거로 예전과 같은 실행계획을 그대로 쓴다. USER_INDEXES 와 USER_TABLES 의 LAST_ANALYZED 시점을 확인하고, 필요하면 DBMS_STATS.GATHER_TABLE_STATS 로 통계를 갱신한 뒤 실행계획이 바뀌는지 비교한다.