Post

6. 저장 구조와 인덱싱

Posted
By noir1458
16 min read
6. 저장 구조와 인덱싱

물리적 저장 구조

저장 장치 계층

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

              속도 ↑    용량 ↓    비용 ↑
┌──────────────────────────────────────┐
│       CPU 레지스터 / 캐시             │  ← 휘발성
├──────────────────────────────────────┤
│       메인 메모리 (RAM)              │  ← 휘발성
├──────────────────────────────────────┤
│       SSD (Flash Memory)            │  ← 비휘발성
├──────────────────────────────────────┤
│       HDD (자기 디스크)              │  ← 비휘발성
├──────────────────────────────────────┤
│       테이프 (백업)                   │  ← 비휘발성
└──────────────────────────────────────┘

DB는 주로 디스크(SSD/HDD)에 저장, 필요한 부분만 메모리로 올려서 처리
→ 디스크 I/O 최소화가 성능의 핵심

디스크 접근

1
2
3
4
5
6
7
8
9
10
11
12

HDD 접근 시간 = 탐색 시간(Seek Time) + 회전 지연(Rotational Latency) + 전송 시간(Transfer Time)

- 탐색 시간: 헤드를 해당 트랙으로 이동 (~5ms)
- 회전 지연: 원하는 섹터가 헤드 아래로 올 때까지 대기 (~4ms)
- 전송 시간: 데이터 전송 (~0.1ms)

SSD: 탐색 시간/회전 지연 없음 → Random I/O에서 HDD 대비 100배 이상 빠름

블록(Page):
  - 디스크 I/O의 기본 단위 (보통 4KB ~ 16KB)
  - 한 번의 I/O로 한 블록을 읽고/씀
  - 레코드가 아닌 블록 단위로 데이터를 관리

파일 구성

1
2
3
4
5
6
7
8
9
10
11
12
13
14

1. 힙 파일 (Heap File)
   - 레코드를 삽입 순서대로 저장
   - 삽입: O(1), 검색: O(N)
   - 정렬되지 않음

2. 순차 파일 (Sequential File)
   - 검색 키 순서로 정렬하여 저장
   - 범위 검색 유리
   - 삽입/삭제 시 재정렬 필요 (오버플로우 블록 사용)

3. 해시 파일 (Hash File)
   - 해시 함수로 레코드 위치 결정
   - 동등 검색: O(1) 평균
   - 범위 검색 불가

인덱스 (Index)

데이터 검색 속도를 높이기 위한 자료 구조. 책의 색인(Index)과 같은 역할.

인덱스의 기본 개념

1
2
3
4
5
6
7
8
9
10
11

인덱스 없이 검색: Full Table Scan → O(N)
인덱스 사용 검색: 인덱스 탐색 → O(log N) 또는 O(1)

인덱스 구성:
  (검색 키, 포인터) 쌍의 집합
  검색 키 → 실제 데이터가 저장된 블록의 주소

트레이드오프:
  ✅ 검색 속도 향상
  ❌ 삽입/삭제/수정 시 인덱스도 갱신 (오버헤드)
  ❌ 추가 저장 공간 필요

인덱스 분류

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

구조 기준:
  1. 순서 인덱스 (Ordered Index): 검색 키가 정렬된 순서
  2. 해시 인덱스 (Hash Index): 해시 함수 기반

밀집도 기준:
  1. 밀집 인덱스 (Dense Index): 모든 레코드에 대해 인덱스 엔트리
  2. 희소 인덱스 (Sparse Index): 일부 레코드에 대해서만 인덱스 엔트리

레벨 기준:
  1. 단일 레벨 인덱스
  2. 다중 레벨 인덱스 (B-Tree, B+ Tree)

기본 vs 보조:
  1. 기본 인덱스 (Primary/Clustering Index): 데이터 정렬 순서와 일치
  2. 보조 인덱스 (Secondary/Non-clustering Index): 데이터 정렬 순서와 무관

밀집 vs 희소 인덱스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

밀집 인덱스 (Dense Index):
┌───────┐         ┌─────────────┐
│ 10 ●──┼────→    │ 10, 홍길동   │
│ 20 ●──┼────→    │ 20, 김영희   │
│ 30 ●──┼────→    │ 30, 이철수   │
│ 40 ●──┼────→    │ 40, 박민수   │
└───────┘         └─────────────┘
- 모든 레코드에 인덱스 엔트리
- 검색 빠름, 공간 많이 사용

희소 인덱스 (Sparse Index):
┌───────┐         ┌─────────────┐
│ 10 ●──┼────→    │ 10, 홍길동   │
│       │         │ 20, 김영희   │
│ 30 ●──┼────→    │ 30, 이철수   │
│       │         │ 40, 박민수   │
└───────┘         └─────────────┘
- 블록당 하나의 인덱스 엔트리
- 공간 절약, 데이터가 정렬되어 있어야 함
- 기본 인덱스에서만 사용 가능

B-Tree

구조

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

B-Tree of order m:
- 루트를 제외한 모든 노드: ⌈m/2⌉ ~ m개의 자식
- 루트: 2 ~ m개의 자식 (또는 리프)
- 모든 리프 노드는 같은 깊이
- 내부 노드에도 데이터 저장

예: B-Tree of order 3 (2-3 Tree)
            [30]
           ╱    ╲
       [10,20]  [40,50]
      ╱  │  ╲   ╱  │  ╲
    [5] [15] [25] [35] [45] [55]

검색: O(log N)
삽입: 노드가 가득 차면 분할 (Split)
삭제: 노드가 최소 키 수 미만이면 병합 (Merge) 또는 재분배

B-Tree 연산

1
2
3
4
5
6
7
8
9
10
11
12

검색: 루트에서 시작하여 키 비교로 자식 선택 → 리프까지
삽입:
  1. 적절한 리프 노드 찾기
  2. 키 삽입
  3. 노드 오버플로우 시 → 중간 키를 부모로 올리고 분할

삭제:
  1. 키 찾기
  2. 리프에서 삭제
  3. 언더플로우 시:
     - 형제에서 빌리기 (Redistribution)
     - 형제와 병합 (Merge, 부모 키 내려옴)

B+ Tree

실제 DBMS에서 가장 널리 사용되는 인덱스 구조.

B-Tree와 B+ Tree 차이

1
2
3
4
5
6
7
8
9

B-Tree:
  - 내부 노드에도 데이터 저장
  - 검색 시 중간에서 끝날 수 있음

B+ Tree:
  - 내부 노드에는 키만 저장 (데이터는 리프에만)
  - 리프 노드가 연결 리스트로 연결
  - 범위 검색에 효율적
  - 내부 노드에 더 많은 키 저장 가능 → 트리 높이 낮음

B+ Tree 구조

1
2
3
4
5
6
7
8
9
10
11
12

                    [30]                    ← 내부 노드 (키만)
                   ╱    ╲
            [10, 20]    [40, 50]            ← 내부 노드 (키만)
           ╱   │   ╲   ╱   │   ╲
         [5,8][10,15][20,25][30,35][40,45][50,55]  ← 리프 노드 (데이터)
          ↔     ↔      ↔     ↔      ↔      ↔      ← 리프 간 연결 리스트

특징:
- 모든 데이터가 리프 노드에 존재
- 리프 노드 간 Linked List → 범위 검색 효율적
- 내부 노드는 검색 경로 안내 역할만
- 실제 DBMS: MySQL InnoDB, PostgreSQL 등

B+ Tree 성능

1
2
3
4
5
6
7
8
9
10
11
12

높이 h인 B+ Tree (차수 m):
- 최대 키 수: m^h - 1
- 검색: O(log_m N) = O(h)
- 삽입/삭제: O(log_m N)

예: m = 100, N = 1억
  h = log_100(10^8) = 4
  → 최대 4번의 디스크 I/O로 검색 가능

실제 DBMS에서:
  - 루트와 상위 노드는 메모리에 캐시
  - 디스크 I/O는 보통 1~2회

해시 인덱스

정적 해싱

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

h(key) → bucket number

버킷: 하나 이상의 블록으로 구성된 저장 단위

┌─────────────────────┐
│ h(key) = key mod 4  │
├─────────────────────┤
│ Bucket 0: 8, 12, 20 │
│ Bucket 1: 5, 9, 21  │
│ Bucket 2: 2, 6, 14  │
│ Bucket 3: 3, 7, 11  │
└─────────────────────┘

장점: 동등 검색(=) O(1) 평균
단점:
  - 범위 검색 불가
  - 버킷 오버플로우 시 성능 저하
  - 데이터 증가에 따른 재해싱 필요

확장 가능 해싱 (Extendible Hashing)

1
2
3
4
5
6
7

디렉토리를 사용하여 동적으로 버킷 수 조절

글로벌 깊이(Global Depth): 디렉토리 크기 결정 (2^d)
로컬 깊이(Local Depth): 각 버킷의 해시 비트 수

장점: 점진적 확장, 전체 재해싱 불필요
단점: 디렉토리 추가 공간, 포인터 간접 참조

인덱스 설계 지침

인덱스를 생성해야 하는 경우

1
2
3
4
5

1. WHERE 절에 자주 사용되는 컬럼
2. JOIN 조건에 사용되는 컬럼
3. ORDER BY, GROUP BY에 사용되는 컬럼
4. 선택도(Selectivity)가 높은 컬럼 (고유 값이 많은)
5. 외래키 컬럼

인덱스를 피해야 하는 경우

1
2
3
4
5

1. 테이블 크기가 작은 경우 (Full Scan이 더 빠름)
2. 삽입/수정/삭제가 빈번한 컬럼 (인덱스 유지 비용)
3. 선택도가 낮은 컬럼 (예: 성별 - M/F 두 값)
4. NULL이 많은 컬럼
5. 넓은 범위 조회가 대부분인 경우

인덱스 유형별 SQL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

-- 단일 컬럼 인덱스
CREATE INDEX idx_name ON Student(name);

-- 복합 인덱스 (Multi-column Index)
CREATE INDEX idx_dept_grade ON Student(dept, grade);
-- 주의: 선행 컬럼(dept) 조건이 있어야 인덱스 사용
-- WHERE dept = 'CS' AND grade = 4  → 사용 ✅
-- WHERE dept = 'CS'                → 사용 ✅
-- WHERE grade = 4                  → 사용 ❌ (선행 컬럼 없음)

-- 유니크 인덱스
CREATE UNIQUE INDEX idx_email ON Student(email);

-- 인덱스 삭제
DROP INDEX idx_name;

클러스터드 vs 논클러스터드 인덱스

1
2
3
4
5
6
7
8
9
10
11

클러스터드 인덱스 (Clustered Index):
  - 데이터가 인덱스 순서대로 물리적으로 정렬
  - 테이블당 하나만 가능
  - 보통 PK에 자동 생성
  - 범위 검색에 매우 유리

논클러스터드 인덱스 (Non-clustered Index):
  - 인덱스와 데이터가 별도 저장
  - 인덱스 리프에 데이터의 포인터 저장
  - 테이블당 여러 개 가능
  - 포인터 참조 → 추가 I/O 발생 가능

핵심 정리

1
2
3
4
5
6
7

1. 디스크 I/O 최소화가 DB 성능의 핵심
2. 인덱스: 검색 키 + 포인터 → O(log N) 검색
3. B+ Tree: 리프에만 데이터, 리프 간 연결 → 범위 검색 최적
4. B-Tree vs B+ Tree: 내부 노드 데이터 유무, 리프 연결 리스트
5. 해시 인덱스: 동등 검색 O(1), 범위 검색 불가
6. 클러스터드: 물리 정렬 일치 (1개), 논클러스터드: 별도 저장 (여러 개)
7. 인덱스 생성: 선택도 높은 WHERE/JOIN 조건 컬럼

면접 포인트

자주 나오는 질문

Q1. B-Tree와 B+ Tree의 차이는?

  • B-Tree: 내부 노드에도 데이터 저장, 검색이 중간에서 끝날 수 있음
  • B+ Tree: 데이터는 리프에만, 리프 간 연결 리스트, 범위 검색 효율적
  • B+ Tree가 실무에서 더 많이 사용됨 (MySQL, PostgreSQL 등)

Q2. 인덱스를 쓰면 무조건 빨라지는가?

  • 아님. 삽입/수정/삭제 시 인덱스 유지 비용이 추가됨
  • 테이블이 작거나 대부분의 행을 조회하면 Full Scan이 더 빠를 수 있음
  • 선택도가 낮은 컬럼에 인덱스를 만들면 효과가 적음

Q3. 클러스터드 인덱스와 논클러스터드 인덱스의 차이는?

  • 클러스터드: 데이터가 인덱스 순서대로 물리적 정렬, 테이블당 1개
  • 논클러스터드: 별도 인덱스 구조, 리프에 데이터 포인터, 여러 개 가능
  • PK에 보통 클러스터드 인덱스가 자동 생성

Q4. 복합 인덱스에서 컬럼 순서가 중요한 이유는?

  • (A, B, C) 인덱스: A로 정렬 → 같은 A 내에서 B 정렬 → 같은 B 내에서 C 정렬
  • WHERE A = ? → 사용 가능
  • WHERE A = ? AND B = ? → 사용 가능
  • WHERE B = ? → 사용 불가 (선행 컬럼 A 조건 없음)
  • 가장 선택도가 높은(카디널리티가 큰) 컬럼을 앞에 배치

Q5. 해시 인덱스의 장단점은?

  • 장점: 동등 검색(=) O(1), 매우 빠름
  • 단점: 범위 검색(>, <, BETWEEN) 불가, 정렬 불가
  • B+ Tree가 범용적으로 더 유용하여 기본 인덱스로 사용됨

Q6. 인덱스가 사용되지 않는 경우는?

  • 컬럼에 함수/연산 적용: WHERE YEAR(date) = 2025 (함수 인덱스 필요)
  • LIKE ‘%keyword’ (앞에 와일드카드)
  • 묵시적 형변환 발생
  • 옵티마이저가 Full Scan이 더 효율적이라 판단
  • 복합 인덱스의 선행 컬럼 조건 누락
database
database
This post is licensed under CC BY 4.0 by the author.