07 데이터베이스 물리적 설계

1. 보조 기억 장치

데이터베이스를 저장하는 물리적 저장 매체의 특성을 다룬다.

1.1. 저장 장치 종류

• 메인 메모리

  • 속도는 빠르지만 휘발성이고 용량이 작아 전체 DB 저장에는 부적합하다.

• 플래시 메모리(SSD)

  • 비휘발성, 블록 지향
  • HDD보다 빠르다. 최근 대용량화/저가화로 HDD를 대체 중이다.

• 자기 디스크(HDD)

  • 전통적인 대용량 보조 기억 장치
  • 트랙, 섹터, 실린더 구조로 되어 있다.
  • 디스크 접근 시간: 탐구 시간(Seek time) + 회전 지연 시간(Rotational delay) + 전송 시간(Transfer time)의 합으로 결정된다.

2. 버퍼 관리와 운영 체제

디스크 입출력(I/O) 성능을 최적화하기 위한 기법이다.

• 버퍼(Buffer): 디스크 블록을 임시로 저장하는 주기억 장치 공간
• 목적: 디스크 I/O는 시스템에서 가장 느린 작업이므로, 입출력 횟수를 줄여 DBMS 성능을 향상시키는 것이 핵심이다. 자주 참조되는 블록을 메모리에 상주시켜 성능을 높인다.

3. 디스크 상에서 파일의 레코드 배치

데이터를 물리적으로 디스크에 저장하고 배치하는 방법이다.

• 블록과 레코드

  • 연관된 필드가 모여 레코드가 되고, 레코드들이 모여 블록(화일)에 저장된다.

• 채우기 인수(Fill Factor)

  • 나중에 데이터가 삽입/수정될 때 이동을 최소화하기 위해 블록에 여유 공간을 남겨두는 비율

• 클러스터링(Clustering)

  • 화일 내(Intra-file): 함께 검색될 확률이 높은 레코드들을 물리적으로 인접하게 저장
  • 화일 간(Inter-file): 논리적으로 연관된(조인 등) 두 개 이상의 화일 레코드들을 가까운 곳에 저장

4. 파일 조직(File Organization)

데이터 파일 내에서 레코드를 조직화하는 방식과 성능 차이를 다룬다.

• 파일 조직: 레코드가 물리적으로 ㅈ
  • 힙 파일: 삽입된 순서대로 저장
  • 순차 파일: 탐색키 순서대로 정렬되어 저장

4.1 힙 파일(Heap File)

• 특징: 가장 단순한 구조로, 레코드가 삽입된 순서대로 저장된다. (정렬 X)

• 연산

  • 삽입: 파일의 가장 끝에 첨부하므로 매우 빠르다.
  • 검색: 특정 레코드를 찾기 위해 모든 블록을 순차적으로 읽어야 하므로 비효율적이다. (평균 $b/2$ 블록 접근, 조건 검색 시 $b$ 전체 접근)

• 용도: 데이터를 한꺼번에 적재(Bulk loading)하거나, 전체 검색 위주의 업무에 적합하다.

4.2 순차 파일(Sequential File)

• 특징: 레코드들이 탐색 키(Search Key) 값의 순서대로 정렬되어 저장된다.

• 연산

  • 삽입: 정렬 순서를 유지해야 하므로 데이터 이동이 발생하여 시간이 오래 걸린다.
  • 검색: 탐색 키를 이용한 검색 시 이진 탐색(Binary Search)이 가능하여 매우 빠르다. ($lo{g}_{2}b$ 수준) 단, 탐색 키가 아닌 다른 필드로 검색 시에는 전체 탐색을 해야 한다.

5. 단일단계 인덱스(Single-Level Index)

• 단일단계 인덱스: <탐색 키, 포인터>로 구성된 보조파일
  • 데이터 파일과는 별도로 빠른 검색을 위해 <탐색 키, 포인터> 쌍으로 구성된 보조 파일을 생성한다.
  • 엔트리들은 키 값으로 정렬된다.

5.1. 클러스터링 인덱스(Clustering Index)

• 클러스터링 인덱스: 데이터의 물리적 저장 순서를 결정하는 인덱스

• 조건: 데이터 파일이 탐색 키 순서로 정렬되어 있지만, 탐색 키가 기본 키가 아닌 경우(중복 값 허용) 생성한다.

• 특징: 범위 질의(Range Query)에 매우 유리하다. 인덱스를 통해 범위의 시작점을 찾으면, 그 이후 데이터는 물리적으로 인접해 있기 때문에 디스크 I/O가 최소화된다.

5.2. 기본 인덱스(Primary Index)

• 조건: 탐색 키가 기본 키(PK)이며, 데이터 파일이 기본 키 순서로 정렬되어 있을 때 생성한다.

• 구조: 희소 인덱스(Sparse Index) 방식을 사용한다.

  • 모든 레코드마다 인덱스를 만들지 않고, 각 데이터 블록의 첫 번째 레코드(앵커)에 대해서만 인덱스 엔트리를 만든다.

• 특징: 인덱스 크기가 작아 메모리 공간을 적게 차지하며 유지보수 오버헤드가 적다.

5.3. 보조 인덱스(Secondary Index)

• 조건: 데이터 파일의 정렬 순서와 상관없이 다른 컬럼으로 검색이 필요할 때 생성한다. (예: 사번으로 정렬된 파일에서 이름으로 검색)

• 구조: 밀집 인덱스(Dense Index) 방식을 사용한다.

  • 데이터 파일의 모든 레코드에 대해 인덱스 엔트리를 생성해야 한다.

• 특징: 한 테이블에 여러 개의 보조 인덱스를 만들 수 있다. 희소 인덱스보다 크기가 크고 검색 시 디스크 접근 횟수가 더 많을 수 있다.

6. 다단계 인덱스(Multi-Level Index)

• 다단계 인덱스: 단일단계 인덱스에 다시 인덱스

  • 인덱스 파일 자체의 크기가 커져서 검색 속도가 느려지는 문제를 해결하기 위한 구조이다.

• 개념: 단일 단계 인덱스를 하나의 순서 파일로 간주하고, 그 위에 다시 인덱스를 만드는 방식이다.

• 구조

  • 가장 상위 단계의 인덱스를 마스터 인덱스(Master Index)라고 하며, 한 블록 크기로 작아져 주기억 장치(RAM)에 상주할 수 있다.
  • 대부분의 다단계 인덱스는 B+ 트리(B+ Tree) 구조를 사용한다.

• 장점: 대용량 데이터에서 디스크 접근 횟수를 획기적으로 줄여 검색 속도를 높인다.

• SQL 정의

  • PRIMARY KEY 선언 시: DBMS가 자동으로 기본 인덱스 생성
  • UNIQUE 선언 시: DBMS가 자동으로 보조 인덱스 생성

7. 인덱스 선정 지침과 데이터베이스 튜닝

물리적 설계의 핵심은 효율적인 인덱스 선정과 쿼리 튜닝이다.

7.1 인덱스 선정 지침

1. 기본 키(PK)와 외래 키(FK)는 인덱스 생성의 최우선 후보이다.
2. 선별력(Selectivity)이 높은 컬럼에 인덱스를 만든다. (전체 투플 중 2~4% 미만을 반환하는 질의)
3. 갱신이 빈번한 속성에는 인덱스를 피한다. (유지보수 비용 증가)
4. 작은 파일이나 대량 데이터 삽입(Bulk Insert) 시에는 인덱스가 오히려 성능을 저하시킬 수 있다.
5. 가변 길이(VARCHAR)보다는 정수형 속성에 인덱스를 생성하는 것이 좋다.
6. ORDER BY나 GROUP BY 절에 자주 사용되는 컬럼도 인덱스 후보이다.

7.2 인덱스가 사용되지 않는 경우

다음과 같은 경우에는 인덱스가 있어도 DBMS가 사용하지 못할 수 있다.

• 인덱스 컬럼에 산술 연산을 적용한 경우 (예: WHERE SALARY * 12 > 4000)
• 인덱스 컬럼에 내장 함수를 사용한 경우 (예: WHERE SUBSTR(NAME, 1, 1) = '김')

7.3 질의 튜닝 지침

• DISTINCT, GROUP BY, HAVING 절의 사용을 최소화하여 정렬 연산 부하를 줄인다.
• 임시 릴레이션 사용을 피한다.
• SELECT * 대신 필요한 구체적인 속성 이름을 명시한다.

8. 비용 계산

8.1. 기본 환경 설정

항목	값 / 공식	비고
총 레코드 수 ($N$)	1,000만 개 ($10^7$)	대용량 데이터
레코드 크기 ($R$)	200 Bytes	-
블록 크기 ($B$)	4,096 Bytes (4KB)	-
디스크 I/O 시간	10ms	탐색 + 회전 + 전송
블록킹 인수 ($bfr$)	$20$ 개/블록	$\lfloor 4,096/200\rfloor$
총 데이터 블록 수 ($b$)	500,000 블록	$10,000,000/20$

$\text{총 데이터 블록 수}=\frac{\text{총 레코드 수}}{\text{블로킹 인수}=\lfloor \frac{\text{블록 크기}}{\text{레코드 크기}}\rfloor }$

8.2. 인덱스가 없는 경우

A. 힙 파일

• 상태: 정렬되지 않은 데이터
• 방식: 순차 검색 (Linear Search) - 처음부터 다 뒤짐
• 비용: 전체 블록의 50%($b/2$) 스캔
  • $250,000\text{ blocks}\times 10ms=2,500,000ms$

B. 순차 파일

• 상태: 탐색 키 기준 정렬된 데이터
• 방식: 이진 탐색 (Binary Search)
• 비용: $\lceil {\log }_{2}b\rceil$
  • $\lceil {\log }_{2}500,000\rceil =19\text{ blocks}$
  • $19\times 10ms=190ms$

8.3. 단일 단계 인덱스

• 인덱스 엔트리: 24 Byte (키 20 + 포인터 4)
• 인덱스 블록킹 인수 ($bf{r}_{idx}$): $\lfloor 4,096/24\rfloor =170$

A. 희소 인덱스

• 특징: 데이터 블록당 1개의 엔트리만 생성 (블록의 대표값)
• 인덱스 크기: 데이터 블록 수(50만)만큼 엔트리 필요
  • 총 인덱스 블록: $500,000/170\approx 2,942\text{ blocks}$
• 비용: 인덱스 이진 탐색 + 데이터 접근 1회
  • $(\lceil {\log }_{2}2,942\rceil +1)\times 10ms=130ms$

B. 밀집 인덱스

• 특징: 모든 레코드마다 1개의 엔트리 생성 (보조 인덱스 등)
• 인덱스 크기: 레코드 수(1,000만)만큼 엔트리 필요
  • 총 인덱스 블록: $10,000,000/170\approx 58,824\text{ blocks}$
• 비용: 인덱스 이진 탐색 + 데이터 접근 1회
  • $(\lceil {\log }_{2}58,824\rceil +1)\times 10ms=170ms$

8.4. 다단계 인덱스

• 구조

  1. 1단계: 2,942 블록 (기본 희소 인덱스)
  2. 2단계: $2,942/170\approx 18$ 블록 (1단계의 요약)
  3. 3단계(Root): $18/170=1$ 블록 (최상위 마스터 인덱스)

• 비용: Root $\to$ 2단계 $\to$ 1단계 $\to$ 데이터 블록

  • 인덱스 탐색(3회) + 데이터 접근(1회) = 4회 접근
  • $4\times 10ms=40ms$