09. 인덱싱¶

학습 목표¶

인덱싱이 데이터베이스 성능에 중요한 이유 이해
정렬된 인덱스(Ordered Indices) 구분: 주 인덱스(Primary), 클러스터링(Clustering), 보조 인덱스(Secondary)
B-Tree와 B+Tree 구조, 연산 및 복잡도 마스터
해시 기반 인덱싱 기법: 정적(Static), 확장가능(Extendible), 선형 해싱(Linear Hashing)
비트맵 인덱스(Bitmap Indices)와 다차원 인덱스 구조 이해
실무에서 인덱스 설계 지침 적용

1. 인덱싱이 중요한 이유¶

기본 문제¶

100만 개의 행을 가진 employees 테이블이 디스크에 저장되어 있다고 가정하자. 각 디스크 블록은 10개의 행을 담으므로, 테이블은 10만 개의 블록을 차지한다. ID로 직원 한 명을 찾으려면:

인덱스 없이:  모든 10만 개 블록 스캔  →  O(n) 디스크 I/O
인덱스 사용:  인덱스 포인터 따라가기  →  O(log n) 디스크 I/O

10만 블록의 경우: - 순차 스캔: 최대 10만 번의 블록 읽기 - B+Tree 인덱스 (분기 계수 200): 대략 log_200(1,000,000) ≈ 3 블록 읽기

이는 33,000배의 I/O 비용 개선이다.

순차 vs. 인덱스 접근¶

순차 접근 (테이블 스캔):
┌──────┬──────┬──────┬──────┬──────┬──────┬──────┐
│ Blk1 │ Blk2 │ Blk3 │ Blk4 │ Blk5 │ ...  │ BlkN │
└──────┴──────┴──────┴──────┴──────┴──────┴──────┘
  ↑ 모든 블록을 순차적으로 읽음

인덱스 접근:
┌─────────────────┐
│   인덱스 루트    │  ← 1 I/O
│  [50│100│150]    │
└──┬──────┬──────┬─┘
   ↓      ↓      ↓
 ┌────┐ ┌────┐ ┌────┐
 │리프│ │리프│ │리프│  ← 1 I/O (포인터 따라가기)
 └──┬─┘ └────┘ └────┘
    ↓
 ┌──────┐
 │ 데이터│  ← 1 I/O (실제 레코드 가져오기)
 │ 블록 │
 └──────┘

인덱스를 사용하지 않아야 할 때¶

인덱스가 항상 유익한 것은 아니다:

작은 테이블: 몇 개의 블록을 순차 스캔하는 것이 인덱스 탐색 오버헤드보다 빠름
높은 선택도 쿼리(High Selectivity Queries): 쿼리가 대부분의 행(예: 테이블의 15-20% 이상)을 반환하면, 전체 스캔이 더 저렴함
빈번한 쓰기: 모든 INSERT, UPDATE, DELETE는 인덱스도 업데이트해야 함
낮은 카디널리티 컬럼: B+Tree로 불린 컬럼을 인덱싱하는 것은 낭비임 (비트맵 인덱스가 적절할 수 있음)

비용 모델 기초¶

디스크 접근 비용이 쿼리 성능을 지배한다. 블록 전송(Block Transfers) (디스크 블록 읽기/쓰기)과 탐색(Seeks) (디스크 헤드 이동) 단위로 측정한다.

다음과 같이 정의하자: - b = 파일의 블록 수 - n = 레코드 수 - f = 블로킹 팩터(Blocking Factor) (블록당 레코드 수), 따라서 b = ⌈n/f⌉

접근 방법	평균 비용 (동등 검색)
선형 스캔 (미정렬)	b/2 블록 전송
선형 스캔 (정렬)	⌈log₂(b)⌉ (이진 검색)
주 인덱스 (정렬)	⌈log₂(b_i)⌉ + 1, 여기서 b_i = 인덱스 블록
B+Tree	⌈log_p(b)⌉ + 1, 여기서 p = 분기 계수
해시 인덱스	1 (이상적) ~ 2 (오버플로우 포함)

2. 정렬된 인덱스¶

인덱스 구조 기본¶

인덱스(Index)는 검색 키 값(Search Key Values)을 포인터(Pointers) (레코드 식별자 또는 블록 주소)에 매핑하는 데이터 구조다. 검색 키는 반드시 기본 키일 필요는 없다 -- 어떤 속성이나 속성 집합이든 검색 키로 사용될 수 있다.

인덱스 엔트리 형식:
┌─────────────┬─────────────┐
│ 검색 키 값   │ 레코드      │
│             │ 포인터      │
└─────────────┴─────────────┘

2.1 주 인덱스¶

주 인덱스(Primary Index)는 순차적으로 정렬된 파일의 정렬 키(Ordering Key)에 구축된다. 파일은 인덱싱된 속성으로 물리적으로 정렬된다.

직원 ID에 대한 주 인덱스 (파일이 ID로 정렬됨):

인덱스:                         데이터 파일:
┌─────┬──────┐                 ┌───────────────────┐
│ 100 │  ──────────────────→  │ 100 │ Alice │ ... │ 블록 1
├─────┼──────┤                 │ 105 │ Bob   │ ... │
│ 200 │  ──────┐               ├───────────────────┤
├─────┼──────┤  └───────────→  │ 200 │ Carol │ ... │ 블록 2
│ 300 │  ──────┐               │ 210 │ Dave  │ ... │
└─────┴──────┘  │              ├───────────────────┤
                 └───────────→ │ 300 │ Eve   │ ... │ 블록 3
                               │ 350 │ Frank │ ... │
                               └───────────────────┘

특성: - 블록당 하나의 인덱스 엔트리 (레코드당이 아님) -- 이것은 희소 인덱스(Sparse Index) - 검색 키는 파일이 정렬된 것과 동일한 속성 - 동등 검색과 범위 쿼리에 매우 효율적 - 테이블당 하나의 주 인덱스만 존재 (파일은 한 가지 방법으로만 정렬 가능)

2.2 클러스터링 인덱스¶

클러스터링 인덱스(Clustering Index)는 파일이 물리적으로 정렬된 비-키 속성에 구축된다. 여러 레코드가 동일한 검색 키 값을 공유할 수 있다.

부서에 대한 클러스터링 인덱스:

인덱스:                         데이터 파일 (부서로 정렬):
┌──────────┬──────┐            ┌───────────────────────────┐
│ Acctg    │  ──────────────→ │ Acctg  │ Alice │ 60000   │
├──────────┼──────┤            │ Acctg  │ Bob   │ 55000   │
│ Eng      │  ──────┐          ├───────────────────────────┤
├──────────┼──────┤  └──────→ │ Eng    │ Carol │ 80000   │
│ Sales    │  ──────┐          │ Eng    │ Dave  │ 75000   │
└──────────┴──────┘  │         │ Eng    │ Eve   │ 72000   │
                      │        ├───────────────────────────┤
                      └─────→  │ Sales  │ Frank │ 50000   │
                               │ Sales  │ Grace │ 52000   │
                               └───────────────────────────┘

특성: - 검색 키의 고유 값당 하나의 인덱스 엔트리 - 각 포인터는 해당 값을 포함하는 첫 번째 블록으로 이어짐 - 그룹화 및 집계 쿼리에 효율적

2.3 보조 인덱스¶

보조 인덱스(Secondary Index)는 비-정렬 속성에 대한 대체 접근 경로를 제공한다. 파일은 이 속성으로 정렬되어 있지 않다.

급여에 대한 보조 인덱스:

인덱스 (급여로 정렬):      데이터 파일 (ID로 정렬, 급여로는 정렬 안 됨):
┌───────┬──────┐               ┌───────────────────────────┐
│ 50000 │  ──────────────────→ │ 100 │ Alice │ 60000     │ 블록 1
├───────┼──────┤               │ 105 │ Bob   │ 50000     │
│ 55000 │  ──────┐              ├───────────────────────────┤
├───────┼──────┤  │            │ 200 │ Carol │ 80000     │ 블록 2
│ 60000 │  ──────┐│            │ 210 │ Dave  │ 55000     │
├───────┼──────┤  ││           ├───────────────────────────┤
│ 72000 │  ──┐    ││           │ 300 │ Eve   │ 72000     │ 블록 3
│ ...   │    │    ││           │ 350 │ Frank │ 75000     │
└───────┴────┘    ││           └───────────────────────────┘
                  │││  (포인터가 블록 경계를 넘음)

특성: - 밀집 인덱스(Dense Index)여야 함 (레코드당 하나의 엔트리, 블록당이 아님) - 데이터가 검색 키로 정렬되어 있지 않기 때문 - 동일한 테이블에 여러 보조 인덱스가 존재할 수 있음 - 범위 쿼리에 덜 효율적 (비순차 데이터로 인한 랜덤 I/O 패턴) - 중복 키 값에 대해 추가 간접 수준(포인터 버킷)이 사용되기도 함

밀집 vs. 희소 인덱스¶

밀집 인덱스(Dense Index): 데이터 파일의 모든 레코드에 대해 하나의 인덱스 엔트리.

밀집 인덱스:
┌─────┬───┐     ┌──────────────┐
│ 100 │ ──┼───→ │ 100 │ Alice  │
├─────┼───┤     │ 105 │ Bob    │ ←── 105에 대한 엔트리 존재
│ 105 │ ──┼───→ │              │
├─────┼───┤     ├──────────────┤
│ 200 │ ──┼───→ │ 200 │ Carol  │
├─────┼───┤     │ 210 │ Dave   │
│ 210 │ ──┼───→ │              │
└─────┴───┘     └──────────────┘

희소 인덱스(Sparse Index): 일부 레코드에 대한 하나의 인덱스 엔트리 (일반적으로 블록당 하나).

희소 인덱스:
┌─────┬───┐     ┌──────────────┐
│ 100 │ ──┼───→ │ 100 │ Alice  │  블록 1
│     │   │     │ 105 │ Bob    │  (105에 대한 엔트리 없음)
├─────┼───┤     ├──────────────┤
│ 200 │ ──┼───→ │ 200 │ Carol  │  블록 2
│     │   │     │ 210 │ Dave   │  (210에 대한 엔트리 없음)
└─────┴───┘     └──────────────┘

비교:

측면	밀집 인덱스	희소 인덱스
공간	더 큼 (레코드당 엔트리)	더 작음 (블록당 엔트리)
검색	직접 조회 가능	블록 내 스캔 필요할 수 있음
요구사항	미정렬 파일에서 작동	정렬된 데이터 파일 필요
유지보수	삽입/삭제 시 더 많은 업데이트	더 적은 업데이트
사용 사례	보조 인덱스	주 인덱스

다단계 인덱스¶

인덱스 자체가 메모리에 맞지 않을 정도로 크면, 인덱스에 대한 인덱스를 구축할 수 있다:

레벨 2 (외부 인덱스):
┌──────┬───┐
│  1   │ ──┼───→ ┌──────┬───┐
│ 500  │ ──┼─┐   │  1   │ ──┼───→ 데이터 블록 1
└──────┴───┘ │   │ 100  │ ──┼───→ 데이터 블록 2
              │   │ 200  │ ──┼───→ 데이터 블록 3
              │   │ ...  │   │
              │   └──────┴───┘
              │   레벨 1 (내부 인덱스, 파트 1)
              │
              └→ ┌──────┬───┐
                 │ 500  │ ──┼───→ 데이터 블록 K
                 │ 600  │ ──┼───→ 데이터 블록 K+1
                 │ ...  │   │
                 └──────┴───┘
                 레벨 1 (내부 인덱스, 파트 2)

이는 자연스럽게 트리 구조 인덱스, 특히 B-Tree와 B+Tree로 이어진다.

3. B-Tree¶

3.1 구조¶

차수 m의 B-Tree (또는 degree m의 B-Tree)는 다음을 만족한다:

모든 노드는 최대 m개의 자식을 가짐
모든 내부 노드(루트 제외)는 최소 ⌈m/2⌉개의 자식을 가짐
루트는 최소 2개의 자식을 가짐 (리프가 아닌 경우)
모든 리프는 동일한 레벨에 나타남
k개의 자식을 가진 비-리프 노드는 k-1개의 키를 포함

차수 4의 B-Tree (각 노드는 최대 3개의 키 보유):

                    ┌─────────┐
                    │   30     │
                    └──┬───┬──┘
                  ┌────┘   └────┐
           ┌──────┴──┐    ┌────┴──────┐
           │ 10 │ 20 │    │ 40 │ 50   │
           └┬───┬───┬┘    └┬───┬────┬─┘
            ↓   ↓   ↓      ↓   ↓    ↓
          ┌──┐┌──┐┌──┐  ┌──┐┌──┐ ┌───┐
          │5 ││15││25│  │35││45│ │55  │
          │8 ││  ││  │  │  ││  │ │60  │
          └──┘└──┘└──┘  └──┘└──┘ └───┘

참고: B-Tree에서는 (B+Tree와 달리) 데이터 포인터가
모든 노드에 존재하며, 리프만이 아님.

노드 구조 (n개의 키를 가진 내부 노드):

┌────┬─────┬────┬─────┬────┬─────┬────┐
│ P₁ │ K₁  │ P₂ │ K₂  │ P₃ │ ... │ Pₙ₊₁│
│    │ D₁  │    │ D₂  │    │     │    │
└────┴─────┴────┴─────┴────┴─────┴────┘
  ↓          ↓          ↓            ↓
부트리    부트리    부트리      부트리
< K₁     [K₁,K₂)   [K₂,K₃)      ≥ Kₙ

여기서:
  Pᵢ = 자식 노드에 대한 포인터 (또는 리프의 경우 데이터 블록)
  Kᵢ = 검색 키 값
  Dᵢ = 키 Kᵢ를 가진 데이터 레코드에 대한 포인터

3.2 검색¶

키 K에 대한 B-Tree 검색:

BTREE-SEARCH(node, K):
    i = 1
    while i ≤ node.n and K > node.key[i]:
        i = i + 1

    if i ≤ node.n and K == node.key[i]:
        return (node, i)           // 이 노드에서 발견

    if node is a leaf:
        return NOT_FOUND

    // 디스크에서 자식 읽기
    DISK-READ(node.child[i])
    return BTREE-SEARCH(node.child[i], K)

복잡도: O(log_m n) 디스크 I/O, 여기서 n은 키의 수이고 m은 차수.

3.3 삽입¶

차수 m의 B-Tree에 키 K 삽입:

찾기: 검색을 사용하여 적절한 리프 노드 찾기
삽입: 리프 내에 정렬된 순서로 키 삽입
노드가 오버플로우하면 (m개의 키를 가짐):
중간 키에서 노드를 두 노드로 분할
중간 키를 부모로 승격
필요시 부모 오버플로우를 재귀적으로 처리

예: 차수 3의 B-Tree에 25 삽입 (노드당 최대 2개의 키):

이전:
        ┌────┐
        │ 20 │
        └─┬──┘
     ┌────┴─────┐
  ┌─────┐   ┌──────┐
  │10│15│   │22│30 │  ← 노드가 꽉 참
  └─────┘   └──────┘

단계 1: 키 25는 오른쪽 리프 [22, 30]에 속함.
단계 2: 삽입 → [22, 25, 30] — 오버플로우! (3개의 키 > 최대 2)
단계 3: 중간값(25)에서 분할. 25를 부모로 승격.

이후:
        ┌──────┐
        │20│25 │
        └┬──┬──┘
    ┌────┘  │  └────┐
 ┌─────┐ ┌──┐  ┌──┐
 │10│15│ │22│  │30│
 └─────┘ └──┘  └──┘

3.4 삭제¶

차수 m의 B-Tree에서 키 K 삭제:

K를 포함하는 노드 찾기
K가 리프에 있으면: 직접 제거
K가 내부 노드에 있으면: 리프에서 선행자(또는 후속자)로 교체한 다음 리프에서 삭제
노드가 언더플로우하면 (⌈m/2⌉ - 1개 미만의 키):
가능하면 형제에서 재분배 (빌리기)
그렇지 않으면 형제와 병합하고 부모에서 키를 내림
부모 언더플로우를 재귀적으로 처리

예: 위 트리에서 20 삭제 (차수 3, 비-루트 노드당 최소 1개의 키):

이전:
        ┌──────┐
        │20│25 │
        └┬──┬──┘
    ┌────┘  │  └────┐
 ┌─────┐ ┌──┐  ┌──┐
 │10│15│ │22│  │30│
 └─────┘ └──┘  └──┘

단계 1: 키 20은 내부 노드에 있음.
단계 2: 중위 선행자(15)로 교체.
단계 3: 리프에서 15 삭제.

교체 후:
        ┌──────┐
        │15│25 │
        └┬──┬──┘
    ┌────┘  │  └────┐
 ┌──┐   ┌──┐   ┌──┐
 │10│   │22│   │30│
 └──┘   └──┘   └──┘

3.5 복잡도 분석¶

n개의 키를 가진 차수 m의 B-Tree:

연산	디스크 I/O	CPU 시간
검색	O(log_m n)	O(m · log_m n)
삽입	O(log_m n)	O(m · log_m n)
삭제	O(log_m n)	O(m · log_m n)

높이 한계: n ≥ 1개의 키와 최소 차수 t = ⌈m/2⌉에 대해:

h ≤ log_t((n+1)/2)

일반적인 분기 계수 100-200으로, 높이 3-4의 트리는 수십억개의 레코드를 인덱싱할 수 있다.

4. B+Tree¶

4.1 구조와 특성¶

B+Tree는 관계형 데이터베이스에서 가장 널리 사용되는 인덱스 구조다 (PostgreSQL, MySQL InnoDB, Oracle, SQL Server 모두 B+Tree 사용). B-Tree와 중요한 차이점:

모든 데이터 포인터는 리프 노드에 있음 -- 내부 노드는 키와 자식 포인터만 저장
리프 노드가 연결됨 -- 효율적인 범위 스캔을 위한 이중 연결 리스트
내부 노드의 키가 리프에 중복됨 (내부 키는 가이드 역할만)

B+Tree 구조:

내부 노드 (가이드 키만):
                    ┌────────────┐
                    │  30  │  60  │
                    └──┬───┬──┬──┘
              ┌────────┘   │  └────────┐
              ↓            ↓           ↓
        ┌─────────┐  ┌─────────┐  ┌─────────┐
        │ 10 │ 20 │  │ 40 │ 50 │  │ 70 │ 80 │
        └─┬──┬──┬─┘  └─┬──┬──┬─┘  └─┬──┬──┬─┘
          ↓  ↓  ↓      ↓  ↓  ↓      ↓  ↓  ↓

리프 노드 (실제 데이터, 연결됨):
┌─────┐  ┌─────┐  ┌─────┐  ┌─────┐  ┌─────┐  ┌─────┐  ┌─────┐  ┌─────┐  ┌─────┐
│ 5,8 │↔│10,15│↔│20,25│↔│30,35│↔│40,45│↔│50,55│↔│60,65│↔│70,75│↔│80,85│
│     │  │     │  │     │  │     │  │     │  │     │  │     │  │     │  │     │
│ D*  │  │ D*  │  │ D*  │  │ D*  │  │ D*  │  │ D*  │  │ D*  │  │ D*  │  │ D*  │
└─────┘  └─────┘  └─────┘  └─────┘  └─────┘  └─────┘  └─────┘  └─────┘  └─────┘
  ↑                                                                          ↑
Head                                              리프 체인 (이중 연결)     Tail

D* = 실제 데이터 레코드에 대한 포인터

노드 형식¶

내부 노드 (차수 m, 최대 m개의 포인터, m-1개의 키):

┌────┬─────┬────┬─────┬────┬─────┬────┐
│ P₁ │ K₁  │ P₂ │ K₂  │ P₃ │ ... │ Pₘ│
└────┴─────┴────┴─────┴────┴─────┴────┘
subtree(P₁)의 모든 키 < K₁
K₁ ≤ subtree(P₂)의 모든 키 < K₂
...
Kₘ₋₁ ≤ subtree(Pₘ)의 모든 키

리프 노드 (최대 m-1개의 키-포인터 쌍, 형제 포인터 포함):

┌──────┬──────┬──────┬──────┬─────────┐
│K₁,D₁│K₂,D₂│K₃,D₃│ ...  │ Pₙₑₓₜ  │
└──────┴──────┴──────┴──────┴─────────┘
Dᵢ = 키 Kᵢ를 가진 레코드에 대한 포인터
Pₙₑₓₜ = 다음 리프 노드에 대한 포인터

4.2 B+Tree vs. B-Tree 비교¶

특징	B-Tree	B+Tree
데이터 포인터	모든 노드에	리프 노드에만
키 중복	중복 없음	내부 키가 리프에 중복됨
리프 연결	연결 안 됨	이중 연결 리스트
범위 쿼리	트리를 여러 번 탐색해야 함	리프 체인을 따라감
분기 계수(Fan-out)	낮음 (데이터 포인터가 공간 차지)	높음 (내부 노드가 더 날씬함)
동등 검색	내부 노드에서 조기 종료 가능	항상 리프까지 감
공간 사용	전체적으로 약간 적음	약간 많음 (키 중복)
실제 사용	데이터베이스에서 거의 사용 안 됨	모든 주요 RDBMS에서 표준

4.3 B+Tree에서 검색¶

키 K에 대한 동등 검색:

BPLUS-SEARCH(root, K):
    node = root
    while node is not a leaf:
        i = smallest index such that K < node.key[i]
        if no such i exists:
            node = node.child[last]   // 가장 오른쪽 자식
        else:
            node = node.child[i]      // 자식 i로 이동

    // 이제 리프에 도달: K 스캔
    for each (key, pointer) in node:
        if key == K:
            return pointer
    return NOT_FOUND

범위 검색 [lo, hi]의 키:

BPLUS-RANGE-SEARCH(root, lo, hi):
    // 단계 1: lo를 포함하는 리프 찾기
    leaf = find leaf for lo (동등 검색 로직 사용)

    // 단계 2: 연결 리스트를 통해 리프 스캔
    results = []
    while leaf is not null:
        for each (key, pointer) in leaf:
            if key > hi:
                return results
            if key >= lo:
                results.append(pointer)
        leaf = leaf.next    // 리프 체인을 따라감!
    return results

이것이 B+Tree가 범위 쿼리에 뛰어난 이유다 -- 시작 리프를 찾으면, 연결 리스트를 따라가기만 하면 된다.

4.4 B+Tree에 삽입¶

데이터 포인터 D와 함께 키 K 삽입:

BPLUS-INSERT(root, K, D):
    leaf = find appropriate leaf node

    if leaf has room:
        insert (K, D) in sorted order in leaf
    else:
        // 리프 오버플로우: 분할
        Create new leaf L'
        Distribute entries evenly: first ⌈m/2⌉ stay, rest go to L'

        // 복사: L'의 첫 번째 키가 부모로 감
        parent-key = L'.key[1]
        INSERT-IN-PARENT(leaf, parent-key, L')

    Update leaf linked list pointers

INSERT-IN-PARENT(left, key, right):
    if parent has room:
        insert (key, right pointer) in parent
    else:
        // 내부 노드 오버플로우: 분할
        Create new internal node N'
        Distribute: first ⌈m/2⌉ pointers stay, rest go to N'

        // 푸시: 중간 키가 부모로 감 (복사되지 않음)
        middle-key = the key that separates the two halves
        INSERT-IN-PARENT(parent, middle-key, N')

중요한 구별: - 리프 분할: 복사 (분리 키가 리프와 부모 모두에 존재) - 내부 분할: 푸시 (분리 키가 부모로 이동하고 분할되는 노드에서 제거됨)

예: 차수 3의 B+Tree에 7 삽입 (리프당 최대 2개의 키):

이전:
           ┌────┐
           │ 5  │
           └┬───┘
       ┌────┘  └────┐
    ┌─────┐     ┌──────┐
    │ 3,4 │ ──→ │ 5,6  │
    └─────┘     └──────┘

단계 1: 키 7은 리프 [5, 6]에 속함. 리프가 꽉 참.
단계 2: 리프 분할: [5]와 [6, 7]. 키 6을 부모로 복사.

이후:
           ┌──────┐
           │ 5 │ 6│
           └┬──┬──┘
       ┌───┘  │  └───┐
    ┌─────┐ ┌───┐ ┌─────┐
    │ 3,4 │→│ 5 │→│ 6,7 │
    └─────┘ └───┘ └─────┘

4.5 B+Tree에서 삭제¶

키 K 삭제:

BPLUS-DELETE(root, K):
    leaf = find leaf containing K
    Remove K from leaf

    if leaf has enough keys (≥ ⌈(m-1)/2⌉):
        done (첫 번째 키가 변경되면 부모 키 업데이트 필요할 수 있음)
    else:
        // 언더플로우
        if sibling has extra keys:
            redistribute (형제에서 빌림)
            update parent key
        else:
            merge with sibling
            delete entry from parent
            recursively handle parent underflow

리프 병합은 부모에서 키를 제거한다. 내부 노드 병합은 부모에서 키를 내린다. 루트가 단일 자식만 남으면, 자식이 새 루트가 된다 (트리 높이 감소).

4.6 대량 로딩¶

빈 트리에서 하나씩 삽입하여 B+Tree를 구축하는 것은 비효율적이다. 대량 로딩(Bulk Loading)은 기존 데이터에 인덱스를 생성할 때 사용된다:

BULK-LOAD(sorted_data, m):
    // 단계 1: 검색 키로 데이터 정렬 (필요시 외부 정렬)

    // 단계 2: 리프 노드를 순차적으로 채움
    for each key in sorted_data:
        add to current leaf
        if leaf full:
            start new leaf
            add separator to parent level

    // 단계 3: 상향식으로 내부 레벨 구축
    repeat for each level until root is created

대량 로딩의 장점: - 랜덤 I/O 대신 순차 I/O - 채움 비율(Fill Factor) 제어 가능 (예: 향후 삽입을 위해 90% 채움) - O(n log_m n) 전체, 하지만 상수가 훨씬 더 좋음

PostgreSQL:

-- CREATE INDEX는 테이블에 데이터가 있을 때 내부적으로 대량 로딩 사용
CREATE INDEX idx_emp_salary ON employees(salary);

-- REINDEX는 인덱스를 재구축 (대량 업데이트 후 유용)
REINDEX INDEX idx_emp_salary;

4.7 높이와 성능 분석¶

n개의 검색 키 값을 가진 차수 m의 B+Tree:

최대 높이:

h ≤ ⌈log_{⌈m/2⌉}(n)⌉

실제 예:

주어진: - 블록 크기: 4 KB - 키 크기: 8바이트, 포인터 크기: 8바이트 - 내부 노드 분기 계수: m = 4096 / (8 + 8) = 256 - 리프 엔트리: (m-1) = 리프당 255

n = 100,000,000 (1억) 레코드의 경우:

높이 = ⌈log₁₂₈(100,000,000)⌉ = ⌈log₁₂₈(10⁸)⌉ ≈ ⌈8/2.1⌉ ≈ 4

따라서 1억 개 중 어떤 레코드든 4번의 디스크 읽기로 찾을 수 있다. 실제로 루트와 상위 레벨은 메모리에 캐시되어, 이를 1-2번의 디스크 읽기로 줄일 수 있다.

5. 해시 기반 인덱싱¶

5.1 정적 해싱¶

해시 인덱스는 해시 함수 h(K)를 사용하여 검색 키 값을 버킷 주소에 직접 매핑한다.

해시 함수 h가 키 K를 버킷 번호에 매핑:

Key: "Alice" → h("Alice") = 2
Key: "Bob"   → h("Bob")   = 0
Key: "Carol" → h("Carol") = 2  (충돌!)

버킷 배열:
┌─────────┐
│ 버킷 0  │ → [Bob, ...]
├─────────┤
│ 버킷 1  │ → [empty]
├─────────┤
│ 버킷 2  │ → [Alice, ...] → [Carol, ...]  (오버플로우 체인)
├─────────┤
│ 버킷 3  │ → [Dave, ...]
└─────────┘

특성: - 이상적인 경우: O(1) 조회 -- 한 번의 디스크 읽기 - 오버플로우 처리: 체이닝 (오버플로우 버킷의 연결 리스트) - 약점: 고정된 버킷 수. 파일이 증가하면 성능 저하

해시 함수 요구사항: 1. 균일 분포: 키가 버킷 전체에 균등하게 분산되어야 함 2. 결정적: 동일한 키는 항상 동일한 버킷에 매핑 3. 빠른 계산: O(1) 시간

5.2 확장 가능 해싱¶

확장 가능 해싱(Extendible Hashing)은 전체 파일을 재구성하지 않고 필요에 따라 크기가 2배가 되는 디렉토리를 사용하여 데이터 증가에 적응한다.

주요 개념: - 전역 깊이(Global Depth) (d): 디렉토리가 사용하는 해시 값의 비트 수 - 로컬 깊이(Local Depth) (dᵢ): 버킷 i가 사용하는 비트 수 - 디렉토리 크기 = 2^d 엔트리

전역 깊이 d = 2인 예:

해시 값 (2진수):        디렉토리 (d=2):
h(K₁) = 01001...            ┌────┬───────────┐
h(K₂) = 10110...            │ 00 │ ──→ 버킷 A (로컬 깊이 2)
h(K₃) = 00101...            │ 01 │ ──→ 버킷 B (로컬 깊이 2)
h(K₄) = 11010...            │ 10 │ ──→ 버킷 C (로컬 깊이 1)
h(K₅) = 10011...            │ 11 │ ──→ 버킷 C (로컬 깊이 1)
                             └────┴───────────┘

참고: 엔트리 10과 11 모두 버킷 C를 가리킴
C의 로컬 깊이 (1) < 전역 깊이 (2)이기 때문.
버킷 C에는 첫 번째 비트만 중요함.

버킷 오버플로우 시 버킷 분할:

버킷 B (로컬 깊이 2)가 오버플로우하면:

케이스 1: 로컬 깊이 < 전역 깊이
  → 버킷 분할, 로컬 깊이 증가
  → 엔트리 재분배
  → 디렉토리 포인터 업데이트

케이스 2: 로컬 깊이 == 전역 깊이
  → 디렉토리를 2배로 (전역 깊이 1 증가)
  → 버킷 분할, 로컬 깊이 증가
  → 엔트리 재분배
  → 디렉토리 포인터 업데이트

장점: - 오버플로우 체인 없음 (분할이 증가 처리) - 조회당 최대 2번의 디스크 접근 (디렉토리 1번, 버킷 1번) - 우아하게 증가

단점: - 데이터가 치우치면 디렉토리가 커질 수 있음 - 디렉토리 2배 확장은 비싸지만 드물게 발생

5.3 선형 해싱¶

선형 해싱(Linear Hashing)은 디렉토리를 완전히 피한다. 버킷은 분할 포인터로 제어되는 라운드 로빈 방식으로 한 번에 하나씩 분할된다.

핵심 아이디어: - 다음 분할할 버킷을 추적하는 분할 포인터 s 유지 - 두 개의 해시 함수 사용: h₀(K) = K mod N과 h₁(K) = K mod 2N - 버킷이 오버플로우하면, 분할 포인터의 버킷을 분할 (오버플로우된 버킷이 아님)

N=4 버킷, 분할 포인터 s=1인 상태:

버킷:
┌──────────┐
│ 버킷 0   │ → [h₁(K)=0인 레코드]    (이미 분할됨, h₁ 사용)
├──────────┤
│ 버킷 1   │ → [h₀(K)=1인 레코드]    ← 분할 포인터 s
├──────────┤
│ 버킷 2   │ → [h₀(K)=2인 레코드]    (아직 분할 안 됨, h₀ 사용)
├──────────┤
│ 버킷 3   │ → [h₀(K)=3인 레코드]    (아직 분할 안 됨, h₀ 사용)
├──────────┤
│ 버킷 4   │ → [h₁(K)=4인 레코드]    (버킷 0 분할로 생성됨)
└──────────┘

조회 알고리즘:
  b = h₀(K)          // 예: K mod 4
  if b < s:           // 버킷이 이미 분할됨
      b = h₁(K)      // 대신 K mod 8 사용
  search bucket b

언제 분할할까: - 어떤 버킷이 오버플로우하면 분할이 트리거됨 - 분할 포인터의 버킷이 분할됨 (오버플로우된 버킷이 아님!) - 오버플로우된 버킷은 임시로 오버플로우 체인 사용 - 분할 포인터 전진: s = s + 1 - s = N이면, 라운드 완료: N = 2N, s = 0, 해시 함수 전진

장점: - 디렉토리 불필요 - 부드러운 증가 (한 번에 하나의 버킷) - 보장된 O(1) 평균 접근

단점: - 임시 오버플로우 체인 - 분할이 실제 오버플로우된 버킷을 즉시 완화하지 못할 수 있음

해시 vs. B+Tree 비교¶

기준	해시 인덱스	B+Tree 인덱스
동등 쿼리	O(1) -- 우수	O(log n) -- 좋음
범위 쿼리	지원 안 함	우수 (리프 체인)
정렬된 순회	지원 안 함	자연스러움 (리프 스캔)
동적 증가	확장 가능/선형	분할과 병합
공간 사용	공간 낭비 가능 (빈 버킷)	좋은 활용 (~67%)
구현	더 단순	더 복잡
RDBMS에서 일반적	PostgreSQL (해시), Redis	모든 주요 RDBMS

6. 비트맵 인덱스¶

6.1 개념¶

비트맵 인덱스(Bitmap Index)는 인덱싱된 속성의 각 고유 값에 대해 비트 벡터를 생성한다. 각 비트는 테이블의 행에 해당한다.

테이블: employees (8개 행)
┌─────┬───────┬────────┬────────┐
│ RID │ Name  │ Dept   │ Gender │
├─────┼───────┼────────┼────────┤
│  0  │ Alice │ Eng    │ F      │
│  1  │ Bob   │ Sales  │ M      │
│  2  │ Carol │ Eng    │ F      │
│  3  │ Dave  │ HR     │ M      │
│  4  │ Eve   │ Eng    │ F      │
│  5  │ Frank │ Sales  │ M      │
│  6  │ Grace │ HR     │ F      │
│  7  │ Hank  │ Eng    │ M      │
└─────┴───────┴────────┴────────┘

Dept에 대한 비트맵 인덱스:
  Eng:   [1, 0, 1, 0, 1, 0, 0, 1]  (행 0,2,4,7)
  Sales: [0, 1, 0, 0, 0, 1, 0, 0]  (행 1,5)
  HR:    [0, 0, 0, 1, 0, 0, 1, 0]  (행 3,6)

Gender에 대한 비트맵 인덱스:
  F:     [1, 0, 1, 0, 1, 0, 1, 0]  (행 0,2,4,6)
  M:     [0, 1, 0, 1, 0, 1, 0, 1]  (행 1,3,5,7)

6.2 비트맵 연산¶

비트 연산을 사용하여 비트맵을 결합하여 쿼리에 답할 수 있다:

쿼리: 모든 여성 엔지니어 찾기

  Dept=Eng:  [1, 0, 1, 0, 1, 0, 0, 1]
  AND
  Gender=F:  [1, 0, 1, 0, 1, 0, 1, 0]
  ─────────────────────────────────────
  결과:      [1, 0, 1, 0, 1, 0, 0, 0]  → 행 0, 2, 4
                                         (Alice, Carol, Eve)

쿼리: Sales 또는 HR의 모든 직원 찾기

  Dept=Sales: [0, 1, 0, 0, 0, 1, 0, 0]
  OR
  Dept=HR:    [0, 0, 0, 1, 0, 0, 1, 0]
  ─────────────────────────────────────
  결과:       [0, 1, 0, 1, 0, 1, 1, 0]  → 행 1, 3, 5, 6

쿼리: 모든 비-엔지니어 찾기

  NOT Dept=Eng: NOT [1, 0, 1, 0, 1, 0, 0, 1]
  ─────────────────────────────────────────────
  결과:             [0, 1, 0, 1, 0, 1, 1, 0]  → 행 1, 3, 5, 6

6.3 비트맵 인덱스를 사용해야 할 때¶

이상적인 경우: - 낮은 카디널리티 속성 (Gender: 2개 값, Status: 3-5개 값) - 데이터 웨어하우징 - 대부분 읽기 전용 접근 - 복잡한 다중 속성 쿼리 (AND/OR 조합) - 카운트 쿼리 (WHERE가 있는 COUNT) -- 설정된 비트만 세기 - 스타 스키마(Star Schema) 팩트 테이블의 많은 차원 외래 키

이상적이지 않은 경우: - 높은 카디널리티 속성 (예: 고유 ID -- 값당 하나의 비트맵!) - OLTP - 빈번한 업데이트 (모든 삽입마다 비트맵 업데이트는 비쌈) - 높은 동시성 환경 (비트맵 잠금이 많은 행에 영향)

6.4 비트맵 압축¶

대형 테이블의 경우 비트맵이 매우 커질 수 있다. 압축 기법이 도움이 된다:

런 길이 인코딩(Run-Length Encoding, RLE):

원본:  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]
RLE:   (0, 11), (1, 1), (0, 4)    → "11개의 0, 1개의 1, 4개의 0"

워드 정렬 하이브리드(Word-Aligned Hybrid, WAH): Oracle 및 다른 시스템에서 사용. 동일한 워드(32 또는 64비트)의 시퀀스를 압축하면서 압축된 형태로 효율적인 비트 연산을 허용한다.

로어링 비트맵(Roaring Bitmaps): 비트맵을 청크로 분할하고 각 청크에 대해 최적의 표현(배열, 비트맵, 또는 런)을 사용하는 현대적인 압축 기법. Apache Lucene, Apache Spark 및 다른 시스템에서 널리 사용된다.

6.5 공간 분석¶

n개 행과 c개 고유 값을 가진 속성을 가진 테이블:

비압축 비트맵 크기 = n × c 비트 = nc/8 바이트

B+Tree와 비교:
B+Tree 인덱스 크기 ≈ n × (key_size + pointer_size) 바이트

예: 100만 행, 5개 값을 가진 속성: - 비트맵: 1,000,000 x 5 / 8 = 625,000 바이트 ≈ 610 KB - B+Tree: 1,000,000 x (8 + 8) = 16,000,000 바이트 ≈ 15.3 MB

낮은 카디널리티 속성의 경우 비트맵은 25배 더 작다.

7. 다차원 인덱싱¶

7.1 문제¶

표준 B+Tree와 해시 인덱스는 1차원 검색 키에 잘 작동한다. 하지만 많은 쿼리는 여러 차원을 포함한다:

-- 공간 쿼리
SELECT * FROM restaurants
WHERE latitude BETWEEN 37.7 AND 37.8
  AND longitude BETWEEN -122.5 AND -122.4;

-- 다중 속성 범위 쿼리
SELECT * FROM products
WHERE price BETWEEN 10 AND 50
  AND weight BETWEEN 0.5 AND 2.0;

(latitude, longitude)에 대한 B+Tree는 latitude에서 효율적으로 필터링할 수 있지만 longitude에 대해서는 일치하는 모든 엔트리를 스캔해야 한다. 진정한 다차원 인덱스는 두 차원을 동시에 처리한다.

7.2 R-Tree¶

R-Tree (Rectangle Tree)는 가장 널리 사용되는 공간 인덱스다. 최소 경계 사각형(Minimum Bounding Rectangles, MBR)을 사용하여 데이터를 구성한다.

R-Tree 구조:

루트: [MBR₁, MBR₂]
       ┌──────────────────────────────────────┐
       │   ┌───────────┐    ┌──────────────┐  │
       │   │   MBR₁    │    │    MBR₂      │  │
       │   │ ┌──┐ ┌──┐ │    │ ┌───┐  ┌──┐  │  │
       │   │ │P1│ │P2│ │    │ │P3 │  │P4│  │  │
       │   │ └──┘ └──┘ │    │ └───┘  └──┘  │  │
       │   │      ┌──┐ │    │     ┌──┐     │  │
       │   │      │P5│ │    │     │P6│     │  │
       │   │      └──┘ │    │     └──┘     │  │
       │   └───────────┘    └──────────────┘  │
       └──────────────────────────────────────┘

각 내부 노드: [MBR₁, ptr₁, MBR₂, ptr₂, ...]
각 리프 노드: [MBR₁, oid₁, MBR₂, oid₂, ...]

특성: - 균형 트리 (모든 리프가 동일한 레벨에) - 각 노드는 ⌈m/2⌉와 m 사이의 엔트리를 포함 - 주어진 레벨의 MBR이 겹칠 수 있음 - 검색은 여러 경로를 따라가야 할 수 있음 (B+Tree와 달리)

연산: - 검색: 루트에서 시작, MBR이 쿼리 사각형과 겹치는 모든 자식으로 내려감 - 삽입: MBR이 가장 적게 확대되어야 하는 부트리를 선택; 필요시 분할 - 사용처: PostgreSQL (GiST 인덱스), Oracle Spatial, PostGIS

7.3 kd-Tree¶

kd-tree (k-차원 트리)는 각 레벨에서 분할 차원을 교대로 하여 공간을 분할한다.

2D kd-tree 예 (x, 그 다음 y, 그 다음 x로 분할, ...):

데이터 포인트: (2,3), (5,4), (9,6), (4,7), (8,1), (7,2)

                    (7,2)          x=7에서 분할
                   /     \
              (5,4)       (9,6)    y=4, y=6에서 분할
             /    \          \
          (2,3)  (4,7)      (8,1)  x=2, x=4, x=8에서 분할

공간 분할:
┌───────────────────────┐
│           │            │
│  (2,3)    │   (9,6)   │
│    ·      │     ·     │
│───────(5,4)──────     │
│    ·  │   │           │
│ (4,7) │   │  (8,1)    │
│       │   │    ·      │
└───────┴───┴───────────┘
        x=7    (분할선)

특성: - 이진 트리 (각 노드가 공간을 반으로 분할) - 낮은 차원 데이터에 효율적 (d ≤ 20) - 검색: O(n^(1-1/d) + k) 여기서 k는 결과 수 - 동적 데이터에 대해 균형이 맞지 않음 (k-d-B 트리와 같은 변형 사용)

공간 인덱스 비교:

특징	R-Tree	kd-Tree
차원	어떤 d에도 작동	낮은 d에 최적
동적 업데이트	좋음 (이를 위해 설계됨)	나쁨 (불균형 가능)
디스크 기반	예 (이를 위해 설계됨)	원래 인-메모리
겹침	겹침 허용	겹침 없음
사용 사례	GIS, 공간 데이터베이스	k-NN 검색, 인-메모리

8. 인덱스 선택과 설계 지침¶

8.1 인덱스 선택 문제¶

올바른 인덱스를 선택하는 것은 성능에 중요하다. 인덱스 선택 문제는 다음을 묻는다: 워크로드(쿼리 집합)가 주어졌을 때, 어떤 인덱스를 생성해야 하는가?

고려할 요인: 1. 쿼리 패턴: WHERE, JOIN, ORDER BY, GROUP BY에 어떤 컬럼이 나타나는가? 2. 업데이트 빈도: INSERT, UPDATE, DELETE가 얼마나 자주 실행되는가? 3. 데이터 분포: 각 컬럼의 카디널리티와 선택도 4. 저장 예산: 각 인덱스는 디스크 공간과 유지보수 오버헤드가 듬 5. 상관관계: 자주 함께 쿼리되는 컬럼

8.2 커버링 인덱스¶

커버링 인덱스(Covering Index)는 쿼리에 필요한 모든 컬럼을 포함하므로, 데이터베이스가 테이블에 접근하지 않고 인덱스만으로 쿼리에 답할 수 있다 (인덱스 전용 스캔).

-- 쿼리:
SELECT name, salary FROM employees WHERE department = 'Eng';

-- 비-커버링 인덱스 (테이블 접근 필요):
CREATE INDEX idx_dept ON employees(department);
-- 인덱스를 통해 일치하는 행을 찾은 다음, 테이블에서 name, salary를 가져옴

-- 커버링 인덱스 (테이블 접근 불필요):
CREATE INDEX idx_dept_covering ON employees(department, name, salary);
-- 필요한 모든 컬럼이 인덱스에 있음

PostgreSQL INCLUDE 구문:

-- INCLUDE 컬럼은 리프 레벨에 저장되지만 검색 키에는 없음
CREATE INDEX idx_dept_incl ON employees(department) INCLUDE (name, salary);
-- department는 검색 키; name과 salary는 페이로드만

이점: - 테이블 접근 제거 (막대한 I/O 절감) - 자주 실행되는 쿼리에 특히 효과적

트레이드오프: - 더 큰 인덱스 크기 - 업데이트 시 더 많은 컬럼 유지보수

8.3 복합 (다중 컬럼) 인덱스¶

복합 인덱스(Composite Index)는 여러 컬럼에 구축된다. 컬럼 순서가 매우 중요하다.

CREATE INDEX idx_dept_salary ON employees(department, salary);

이 인덱스는 다음에 유용하다:

-- 전체 인덱스 사용 (두 컬럼 모두):
SELECT * FROM employees WHERE department = 'Eng' AND salary > 80000;

-- 인덱스 접두사 사용 (department만):
SELECT * FROM employees WHERE department = 'Eng';

-- 이 인덱스를 효율적으로 사용하지 않음:
SELECT * FROM employees WHERE salary > 80000;  -- salary는 접두사가 아님

최좌 접두사 규칙: (A, B, C)에 대한 복합 인덱스는 다음 쿼리에 사용될 수 있다: - A - A, B - A, B, C

하지만 다음에는 효율적이지 않다: - B 단독 - C 단독 - B, C

8.4 부분 인덱스¶

부분 인덱스(Partial Index)는 조건자로 정의된 행의 부분집합만 인덱싱한다.

-- 활성 직원만 인덱싱 (90%가 비활성이면 인덱스가 훨씬 작음)
CREATE INDEX idx_active_emp ON employees(name)
WHERE status = 'active';

-- 최근 주문만 인덱싱
CREATE INDEX idx_recent_orders ON orders(customer_id)
WHERE order_date > '2025-01-01';

-- 비-NULL 값만 인덱싱
CREATE INDEX idx_email ON users(email)
WHERE email IS NOT NULL;

이점: - 더 작은 인덱스 크기 (더 적은 엔트리) - 더 빠른 유지보수 (더 적은 업데이트) - 더 나은 캐시 활용

8.5 표현식 인덱스¶

일부 데이터베이스는 계산된 표현식 인덱싱을 지원한다:

-- PostgreSQL: 표현식 인덱스
CREATE INDEX idx_lower_email ON users(lower(email));

-- 대소문자 구분 없는 검색에 유용:
SELECT * FROM users WHERE lower(email) = 'alice@example.com';

-- 타임스탬프에서 연도 추출한 인덱스:
CREATE INDEX idx_order_year ON orders(EXTRACT(YEAR FROM order_date));

8.6 실용적 지침¶

규칙 1: WHERE, JOIN, ORDER BY의 컬럼 인덱싱

-- 이 쿼리는 customer_id, order_date, status의 인덱스로 이익
SELECT o.* FROM orders o
JOIN customers c ON o.customer_id = c.id
WHERE o.order_date > '2025-01-01'
ORDER BY o.status;

규칙 2: 선택도 고려 - 높은 선택도 (일치하는 행이 적음) = 좋은 인덱스 후보 - 낮은 선택도 (대부분의 행이 일치) = 나쁜 인덱스 후보 - 경험 법칙: 인덱스는 행의 15-20% 미만을 선택할 때 유용

규칙 3: 과도한 인덱싱 피하기

각 인덱스 비용:
- 디스크 공간 (인덱스 구조 크기)
- 삽입 오버헤드: ~인덱스당 1번의 B+Tree 삽입
- 업데이트 오버헤드: 인덱스당 구 삭제 + 신 삽입
- 진공/유지보수 오버헤드

일반적인 지침: 테이블당 3-5개 인덱스, 거의 10개를 넘지 않음

규칙 4: EXPLAIN을 사용하여 인덱스 사용 확인

EXPLAIN ANALYZE SELECT * FROM employees WHERE department = 'Eng';

-- 찾을 것:
-- "Index Scan" 또는 "Index Only Scan" → 인덱스가 사용됨
-- "Seq Scan" → 인덱스가 사용되지 않음 (또는 존재하지 않음)
-- "Bitmap Index Scan" → 다중 조건 쿼리에 비트맵 인덱스 사용됨

규칙 5: 인덱스 모니터링 및 유지보수

-- PostgreSQL: 인덱스 사용 통계 확인
SELECT schemaname, tablename, indexname, idx_scan, idx_tup_read
FROM pg_stat_user_indexes
ORDER BY idx_scan ASC;
-- idx_scan = 0인 인덱스는 사용되지 않으며 삭제 가능

-- 인덱스 크기 확인
SELECT pg_size_pretty(pg_relation_size('idx_emp_salary'));

-- 단편화된 인덱스 재구축
REINDEX INDEX idx_emp_salary;

9. 주요 데이터베이스의 인덱스 구조¶

PostgreSQL¶

-- B+Tree (기본값)
CREATE INDEX idx_btree ON table(column);

-- 해시 (동등 검색만, v10부터 WAL 로깅됨)
CREATE INDEX idx_hash ON table USING hash(column);

-- GiST (일반화된 검색 트리(Generalized Search Tree) -- R-Tree, 전문 검색 등)
CREATE INDEX idx_gist ON table USING gist(geom_column);

-- GIN (일반화된 역 인덱스(Generalized Inverted Index) -- 배열, JSONB, 전문 검색)
CREATE INDEX idx_gin ON table USING gin(jsonb_column);

-- BRIN (블록 범위 인덱스(Block Range Index) -- 대형 정렬 테이블)
CREATE INDEX idx_brin ON table USING brin(timestamp_column);

-- SP-GiST (공간 분할 GiST(Space-Partitioned GiST) -- kd-트리, 기수 트리)
CREATE INDEX idx_spgist ON table USING spgist(point_column);

MySQL InnoDB¶

- 기본 키 = 클러스터드 B+Tree 인덱스 (데이터가 리프 노드에 저장됨)
- 보조 인덱스는 기본 키 값을 저장 (행 포인터가 아님)
- 이는 보조 인덱스 조회가 두 번의 B+Tree 탐색을 필요로 함을 의미:
  1. 보조 인덱스 → 기본 키 값
  2. 기본 인덱스 → 실제 행 데이터

요약 표¶

인덱스 타입	최적 용도	한계
B+Tree	범용, 범위, ORDER BY	다차원에는 별로
해시	정확한 동등 조회	범위 지원 없음
비트맵	낮은 카디널리티, 분석	OLTP, 높은 카디널리티에 나쁨
GiST/R-Tree	공간, 기하 데이터	겹침이 검색을 느리게 할 수 있음
GIN	전문 검색, 배열, JSONB	큰 인덱스, 느린 업데이트
BRIN	매우 큰, 자연 정렬 테이블	낮은 정밀도

10. 연습문제¶

개념적 질문¶

연습문제 1: 보조 인덱스는 밀집해야 하는 반면 주 인덱스는 희소할 수 있는 이유를 설명하라 (레코드당 하나의 엔트리 vs. 블록당 하나의 엔트리).

연습문제 2: 테이블에 500,000개의 레코드가 각각 4 KB 블록에 저장되어 있다. 각 레코드는 200바이트다. 기본 키에 대한 B+Tree 인덱스는 8바이트 키와 8바이트 포인터를 사용한다. 각 인덱스 노드는 하나의 블록(4 KB)이다.

(a) 하나의 데이터 블록에 몇 개의 레코드가 맞는가? (b) 테이블은 몇 개의 데이터 블록을 차지하는가? (c) B+Tree의 최대 분기 계수(차수)는? (d) B+Tree의 최대 높이는? (e) 인덱스를 사용한 동등 검색 vs. 전체 테이블 스캔에 몇 번의 디스크 I/O가 필요한가?

연습문제 3: B-Tree와 B+Tree를 비교하라. 거의 모든 데이터베이스 시스템이 B-Tree 대신 B+Tree를 사용하는 이유는?

연습문제 4: 1천만 행을 가진 테이블에서 8개의 고유 값을 가진 color 컬럼에 비트맵 인덱스가 생성되었다.

(a) 비트맵 인덱스의 총 비압축 크기는? (b) 행의 0.1%만 color = 'purple'이면, 런 길이 인코딩을 사용하여 purple 비트맵을 얼마나 압축할 수 있는가? (c) 이를 동일한 컬럼의 B+Tree 인덱스와 비교하라.

실용적 질문¶

연습문제 5: 다음 쿼리 워크로드에 대한 인덱싱 전략을 설계하라:

-- Q1 (트래픽의 90%): 정확한 조회
SELECT * FROM users WHERE email = ?;

-- Q2 (트래픽의 5%): 정렬을 포함한 범위 스캔
SELECT name, created_at FROM users
WHERE created_at > ? ORDER BY created_at DESC LIMIT 20;

-- Q3 (트래픽의 3%): 다중 컬럼 필터
SELECT * FROM users
WHERE country = ? AND age BETWEEN ? AND ?;

-- Q4 (트래픽의 2%): 텍스트 검색
SELECT * FROM users WHERE name ILIKE '%smith%';

각 쿼리에 대해 명시하라: (a) 어떤 인덱스(또는 인덱스들)를 생성할 것인가? (b) 어떤 타입의 인덱스(B+Tree, 해시, GIN 등)? (c) 복합, 커버링, 또는 부분 인덱스를 사용할 것인가?

연습문제 6: 전역 깊이 2, 버킷 용량 2인 다음 확장 가능 해시 디렉토리가 주어졌다:

디렉토리:          버킷:
00 → 버킷 A [h=00110, h=00010]  (로컬 깊이 2)
01 → 버킷 B [h=01100]            (로컬 깊이 2)
10 → 버킷 C [h=10001, h=10110]  (로컬 깊이 2)
11 → 버킷 D [h=11000]            (로컬 깊이 2)

해시 값 h = 00001을 가진 레코드를 삽입한 후 디렉토리와 버킷의 상태를 보여라.

연습문제 7: 4개의 초기 버킷(N=4), 분할 포인터 s=0, 버킷 용량 2인 선형 해싱 방식을 고려하라. 해시 함수는 h₀(K) = K mod 4와 h₁(K) = K mod 8이다. 다음으로 시작:

버킷 0: [8, 16]   (꽉 참)
버킷 1: [5]
버킷 2: [10]
버킷 3: [7, 15]   (꽉 참)

키 12, 9, 3을 (하나씩) 삽입한 후 상태를 보여라.

분석 질문¶

연습문제 8: 차수 m과 n개의 키를 가진 B+Tree의 높이가 최대 ⌈log_{⌈m/2⌉}(n)⌉임을 증명하라.

연습문제 9: 데이터베이스 관리자가 5천만 행을 가진 테이블에서 SELECT COUNT(*) FROM orders WHERE status = 'pending' 쿼리가 2초 걸린다는 것을 발견했다. status 컬럼은 5개의 고유 값을 가진다. 인덱싱 전략을 권장하고 개선을 추정하라.

연습문제 10: sensor_data 테이블에 10억 개의 행, 컬럼 (sensor_id, timestamp, value, location_x, location_y)가 있고, 다음 쿼리 패턴이 있다:

시간 범위 쿼리: WHERE timestamp BETWEEN ? AND ?
센서별 쿼리: WHERE sensor_id = ? AND timestamp BETWEEN ? AND ?
공간 쿼리: WHERE location_x BETWEEN ? AND ? AND location_y BETWEEN ? AND ?
집계: SELECT sensor_id, AVG(value) FROM ... GROUP BY sensor_id

포괄적인 인덱싱 전략을 설계하라. B+Tree, BRIN, GiST, 복합 인덱스를 고려하라. 선택을 정당화하라.

이전: 질의 처리와 최적화 | 다음: 트랜잭션 이론