인덱스 구조와 접근 경로

1. 인덱스의 목적

인덱스는 검색 조건이나 정렬에 자주 사용하는 열의 값을 별도 구조로 저장해 원하는 행의 위치를 빠르게 찾도록 돕는다. 책의 색인처럼 전체 데이터를 처음부터 읽는 대신 필요한 위치를 찾는다.

인덱스가 없을 때
[행1] → [행2] → [행3] → ... → [행N]
         전체 또는 넓은 범위 확인

인덱스가 있을 때
검색값 → 인덱스 탐색 → 행 위치 또는 기본키 → 필요한 행 접근

인덱스는 조회를 빠르게 할 수 있지만 INSERT·UPDATE·DELETE 때 인덱스도 함께 변경해야 하므로 쓰기 비용과 저장공간이 증가한다.

2. B+Tree 인덱스

관계형 DBMS의 일반적인 범위 검색 인덱스는 B+Tree 계열이다. 루트와 브랜치 노드는 탐색 경로를 안내하고, 리프 노드에 정렬된 키와 행 위치 또는 기본키가 저장된다.

                   [Root]
              /      |      \
         [Branch] [Branch] [Branch]
          /   \       |       /   \
       [Leaf]-[Leaf]-[Leaf]-[Leaf]-[Leaf]
         10     20     30     40     50

리프 노드는 정렬된 순서로 연결되어 범위 검색에 유리하다.

탐색은 대체로 다음 순서이다.

검색 조건의 키
    ↓
Root에서 범위 선택
    ↓
Branch를 따라 이동
    ↓
Leaf에서 시작 위치 확인
    ↓
필요한 범위의 Leaf 순차 탐색
    ↓
테이블 행 접근 또는 인덱스만으로 결과 반환

대표 접근 형태는 다음과 같다.

• Unique Scan: 유일 인덱스에 동등 조건을 적용해 최대 한 행을 찾는다.
• Range Scan: =, 범위, 전방 일치 LIKE 'ABC%' 등으로 일부 리프 구간을 읽는다.
• Full Scan: 인덱스 전체를 순서대로 읽는다.
• Fast Full Scan: DBMS가 지원하는 경우 인덱스를 테이블처럼 여러 블록 단위로 읽는다. 정렬 순서는 보장되지 않을 수 있다.

3. 해시 인덱스

해시 인덱스는 키에 해시함수를 적용해 버킷 위치를 찾는다.

key ──hash(key)──► bucket ──► row

동등 검색에는 유리할 수 있지만 키의 정렬 순서를 유지하지 않으므로 범위 검색과 정렬에는 일반적으로 적합하지 않다. 실제 지원 방식은 DBMS와 저장 엔진에 따라 다르다.

4. 복합 인덱스와 선두 열

CREATE INDEX idx_employee_dept_salary
    ON employee (dept_id, salary);

복합 인덱스는 (dept_id, salary) 순서로 정렬된다. 일반적으로 다음 조건은 활용하기 쉽다.

WHERE dept_id = 10
WHERE dept_id = 10 AND salary >= 5000

반면 salary만 조건으로 사용하면 선두 열 dept_id가 빠져 있어 효율적인 범위 시작점을 찾기 어렵다. 일부 DBMS는 skip scan 등 다른 방식을 사용할 수 있지만 기본 원리는 선두 열부터 연속적으로 조건이 연결될수록 유리하다는 것이다.

복합 인덱스에서 앞쪽 열이 범위 조건이 되면 그 뒤 열은 인덱스 탐색 범위를 더 좁히는 데 제한적으로 사용될 수 있다.

5. 선택도와 클러스터링

• 선택도: 조건을 만족하는 행의 비율이다. 소수 행만 선택할수록 인덱스의 이점이 커지는 경우가 많다.
• 카디널리티: 조건 결과 행 수 또는 열의 서로 다른 값 수라는 문맥으로 사용된다. 문제에서 의미를 확인한다.
• 클러스터링 상태: 인덱스 순서와 테이블 행의 물리적 위치가 비슷할수록 범위 검색의 테이블 접근이 효율적이다.

성별처럼 값 종류가 매우 적은 열의 단일 인덱스는 많은 행을 읽어야 하므로 항상 유리하지 않다. 반대로 기본키·이메일처럼 고유성이 높은 열은 동등 검색에 유리하다.

6. 커버링 인덱스와 실행계획

쿼리에 필요한 열이 모두 인덱스에 있으면 테이블 행을 추가로 읽지 않고 결과를 반환할 수 있다. 이를 커버링 인덱스 또는 index-only access라고 부른다.

CREATE INDEX idx_employee_dept_name
    ON employee (dept_id, emp_name);

SELECT emp_name
FROM employee
WHERE dept_id = 10;

실행계획에서는 다음 항목을 구분한다.

TABLE FULL SCAN
    └─ 테이블의 많은 블록을 직접 읽음

INDEX RANGE SCAN
    └─ 인덱스에서 대상 위치 탐색
          └─ TABLE ACCESS BY ROWID 또는 기본키 조회

옵티마이저는 인덱스 존재 여부만 보는 것이 아니라 예상 행 수, 통계정보, 테이블·인덱스 크기, 정렬 필요성, 랜덤 접근 비용 등을 비교한다.

7. 인덱스가 불리할 수 있는 경우

• 조건 결과가 테이블의 매우 큰 비율인 경우
• 인덱스 열에 함수나 연산을 적용해 탐색 가능한 형태가 깨진 경우
• 선행 와일드카드 검색: LIKE '%ABC'
• 작은 테이블에서 대부분의 행을 읽는 경우
• 갱신이 매우 빈번하고 조회 이득이 작은 경우
• 통계정보가 부정확한 경우

함수 기반 인덱스를 지원하는 DBMS에서는 표현식이 정확히 일치하면 함수 조건도 인덱스를 사용할 수 있다.

8. B+Tree 높이와 범위 탐색

             Root
        /      |      \
     Branch  Branch  Branch
       │        │       │
   [10..29]→[30..49]→[50..69]  leaf links

키 35~55를 찾으면 루트에서 35가 있는 리프까지 내려간 뒤 연결된 리프를 55까지 순차 읽는다. 팬아웃이 크므로 매우 많은 엔트리도 낮은 높이로 관리할 수 있다.

9. 복합 인덱스와 SARGability

-- 대표 후보: (customer_id,status,order_date)
WHERE customer_id = :c
  AND status = 'Y'
  AND order_date >= :from_date
  AND order_date <  :to_date
ORDER BY order_date;

동등 조건을 앞에 두고 범위·정렬 열을 뒤에 두는 것이 전형적인 출발점이다. 실제 순서는 선택도와 전체 쿼리군을 함께 검증한다.

-- 일반 열 인덱스의 탐색성을 떨어뜨릴 수 있음
WHERE EXTRACT(YEAR FROM order_date)=2026

-- 같은 의미의 범위 조건
WHERE order_date>=DATE '2026-01-01'
  AND order_date< DATE '2027-01-01'

10. 인덱스 비용을 수치로 비교하기

트리 탐색 3페이지 + 리프 20페이지 + 테이블 랜덤 800페이지
= 약 823페이지
테이블 전체 순차 스캔 = 500페이지

반환량이 크고 클러스터링이 나쁘면 인덱스가 있어도 전체 스캔이 더 저렴할 수 있다. 커버링 인덱스는 테이블 접근을 줄이지만 MVCC 가시성 확인 때문에 일부 DBMS에서는 테이블 페이지를 확인할 수 있다.

11. 갱신 비용과 특수 인덱스

중간 키 삽입으로 리프가 가득 차면 페이지 분할과 상위 구분 키 전파가 발생한다. 비트맵 인덱스는 저카디널리티 분석 조건 결합에는 유리하지만 동시 갱신이 많은 OLTP에서는 넓은 경합을 만들 수 있다.

확인 문제

1. 복합 인덱스 선두 열이 중요한 이유는?
2. SARGable 날짜 연도 조건의 예는?
3. 인덱스가 있어도 전체 스캔이 유리할 수 있는 때는?
4. 페이지 분할은 언제 발생하는가?
5. 커버링이어도 테이블을 읽을 수 있는 이유는?