DB에 인덱싱을 적용하면 왜 빨라질까?

1. 인덱스란 무엇인가?

• 테이블의 특정 컬럼에 대한 검색용 색인 역할을 하는 별도의 자료구조
• 일반적으로 B-Tree(또는 해시), B+Tree를 사용하여 키 값을 정렬된 상태로 관리
• 리프 노드에는 (키 값, ROWID 또는 포인터) 쌍이 저장되어 있어 원하는 행으로 곧바로 접근 가능

2. 인덱스 생성 시 내부 변화

1. 인덱스 세그먼트(index segment) 추가
   • 테이블 데이터와 별도로 저장 공간이 할당된다.
2. B-Tree 구조 구성
   • 루트 → 분기(branch) → 리프(leaf) 노드로 이루어진 트리가 만들어지고,
   • 리프 노드에 (키, ROWID) 쌍이 정렬된 상태로 보관된다.
3. 시스템 카탈로그 갱신
   • 어떤 테이블의 어떤 컬럼을 인덱스로 사용할지 메타데이터에 기록된다.
    

출처 : 코딩애플

3. B+Tree란 무엇인가?

• B-Tree 계열의 변형으로, 대부분의 RDBMS가 인덱스 구현에 사용
• 내부 노드
  • 오직 분기용 키(key) 만 저장
  • 자식 노드를 가리키는 포인터만 보유
• 리프 노드
  • 실제 (키 값, ROWID) 쌍을 모두 저장
  • 서로 연결 리스트(Linked List) 형태로 이어져 있어 범위 검색에 최적화
• 장점
  1. 낮은 트리 높이
     • 내부 노드가 분기 키만 담으므로 한 노드당 더 많은 키를 관리
     • 디스크 페이지 접근 횟수가 줄어든다
  2. 효율적인 범위 검색
     • 리프 노드 간 순차 탐색으로 BETWEEN, ORDER BY 범위 처리 시 인접 페이지를 순차 읽기
     • 디스크 I/O 연속성이 높아 대량 레코드 조회에 유리
  3. 노드 관리 단순화
     • 삽입/삭제 시 리프 노드에서만 데이터 변경, 내부 노드는 분기 키 조정만 수행

4. 쿼리 성능 향상의 핵심 메커니즘

1. 탐색 범위 축소
   • 풀 테이블 스캔: 전체 행 수 n에 비례하여 검색(O(n))
   • 인덱스 스캔: B+Tree 높이에 비례한 탐색(O(log n))
2. 디스크 I/O 감소
   • 필요한 블록만 선택적으로 읽으므로 디스크(또는 SSD) 접근 횟수가 획기적으로 줄어든다.
3. 정렬·그룹화 최적화
   • 인덱스 자체가 정렬된 상태를 유지하므로 ORDER BY, GROUP BY 시 추가 정렬 작업 없이 바로 처리 가능
4. 커버링 인덱스 활용
   • 인덱스에 쿼리에서 필요한 모든 컬럼이 포함된 경우, 실제 테이블 본문 접근 없이 인덱스만으로 결과 반환

5. 옵티마이저의 실행 계획 변화

• 인덱스가 존재하면 쿼리 옵티마이저가
  1. 인덱스 스캔 또는 인덱스 + 테이블 액세스 조합을 비용 기반으로 평가
  2. 총 I/O 비용이 더 낮은 경로를 선택

6. 주의할 점: 트레이드오프

• 쓰기 성능 저하
  • INSERT/UPDATE/DELETE 시 인덱스도 함께 갱신되므로 쓰기 작업 비용이 늘어남
• 디스크 공간 증가
  • 인덱스용 추가 저장 공간이 필요
• 인덱스 설계의 복잡성
  • 너무 많은 인덱스는 오히려 성능 저하를 유발하므로, 사용 빈도가 높은 컬럼 위주로 신중하게 생성