[SW Academy] 01.09

디스크와 파일

1. 기억장치 계층 구조

컴퓨터 시스템의 기억장치는 캐시와 주기억장치로 구성되는 1차 저장장치, 디스크 등으로 구성되는 2차 저장장치, 테이프 등으로 구성되는 3차 저장장치 등의 계층 구조로 구성된다.

2. 디스크

디스크는 컴퓨터 시스템에서 2차 저장장치를 구성하는 데이터 저장소로, 테이프 등의 3차 저장장치보다는 빠르지만 메모리 등의 1차 저장장치보다는 느린 임의 접근 가능 데이터 저장소이다.

HDD(Hard Disk Drive)

• 기계 장치가 포함된 저장장치로, 자기를 이용하여 데이터를 저장하고 읽음
• 순차 접근 방식이 아닌 직접 접근 방식

SSD(Solid State Drive)

• 플래시 메모리를 기반으로 한 저장 매체로, Random Access 가능한 빠른 속도의 저장 장치
• 모든 구성요소가 전기장치이며, 기계 장치를 가지지 않음

 

3. 디스크의 성능

 

HDD

• DBMS가 작업을 수행하려면 데이터는 주 기억장치에 있어야 함
• 디스크와 주 기억장치 간의 데이터 전송 단위는 HDD의 경우 블록이므로 블록 내의 항목 중 하나만 필요한 경우라도 블록 또는 페이지의 전체 데이터가 전송되어야 함
• 블록과 페이지 입출력은 데이터 위치에 좌우됨
  접근 시간 = 탐색시간 + 회전 지연 시간 + 전송 시간
  -> 데이터가 디스크에 저장되어 있는 형태에 따라 데이터베이스 연산에 영향을 미친다.

SSD

• HDD와는 다르게 탐색 지연 시간, 회전 지연 시간이 없이 전송 시간만 소요되므로 임의적 읽기에서도 일정한 응답 속도가 보장됨
• 쓰기의 경우 비어있는 공간이 없으면 공간을 초기화하고, 이 작업 시간 동안 해당 공간에 대한 I/O 작업이 대기 상태가 됨

 

4. 디스크 공간 관리

 

비어 있는 블록의 추적 감시

• 레코드를 삽입함에 따라 데이터베이스를 확장되고 축소됨
• DBMS는 사용중인 디스크 블록과 어떤 블록에 존재하는지 추적 감시함
• 추적 감시
• 비어있는 블록들의 리스트를 유지
• 디스크 블록마다 1 비트씩 블록의 사용 여부를 나타내는 비트맵을 유지

운영체제 파일 시스템

• 운영체제는 디스크 공간을 관리함
  • 운영체제는 파일을 바이트의 순서(Sequence)로 고수준 서비스를 제공
  • 고수준의 요청을 운영체제에 따른 저수준 명령어로 바꾸어 처리함
• DBMS는 운영체제 파일 시스템을 바탕으로 데이터베이스를 관리하기도 함
• 대부분의 DBMS는 운영체제의 파일 시스템에 의존하지 않음
  • 특정 운영체제의 세부적 사양에 맞추면 다양한 운영체제에서 동작하는 DBMS를 만들기 어려움
  • 운영체제는 최대 파일 크기를 제한하는 경우가 있음
  • 운영체제 파일은 여러 디스크로 분할되지 못함
  • 페이지 참조 패턴을 일반적인 운영체제보다 더 정확히 예측해야 함
  • 페이지를 디스크에 기록하는 시점에 대해 더 많은 제어를 해 주어야 함

 

5. 버퍼 관리자

 

버퍼 풀

가용한 주 기억장치 공간을 페이지라는 단위로 분할한 데이터 적재 공간

버퍼 풀내의 페이지를 프레임이라고 하는데, 프레임은 페이지를 담을 수 있는 슬롯이다.

만약 어떤 페이지가 요청되었을 경우엔 버퍼 관리자는

1. 버퍼 풀을 점검하여 요청된 페이지가 있는지를 조사한다. 페이지가 풀에 없으면 버퍼 관리자는 다음과 같은 작업을 통해 페이지를 가져온다.
   1. 정해진 페이지 교체 전략에 따라 교체할 프레임을 선택
   2. 교체할 프레임의 dirty 비트가 true인 경우 프레임의 페이지를 디스크에 저장
   3. 요청 페이지를 해당 프레임으로 로드
2. 요청 페이지를 담고 있는 프레임의 pin_count를 1 증가시키고 프레임의 기억장치내 주소를 반환
   이러한 작업을 수행한다.

버퍼 교체 전략

요청된 페이지가 버퍼 풀에 있지 않고 버퍼 풀에 비어있는 페이지가 없는 경우, pin_count의 값이 0인 페이지 중 하나를 교체용으로 선정한다. 이 과정에서 버퍼 관리자는 버퍼 교체 전략에 따라 선정한다.

• LRU (Least Recently Used)
  가장 최근에 사용한 페이지를 교체하는 전략,
  pin_count가 0인 프레임들에 대란 포인터로 큐를 생성
• Clock
  LRU의 변형으로, 1부터 N 사이의 값인 current 변수를 사용하여 교체용 페이지를 선정
• FIFO (First In First Out), MRU(Most Recently Used), Random등의 방식을 사용

버퍼 관리 기법 비교

• 운영체제의 가상 메모리와 DBMS의 버퍼 관리자는 매우 비슷함
• DBMS는 페이지 참조 패턴을 일반적인 운영체제 환경보다 더 정확히 예측해야 함
  • DBMS는 참조 패턴을 예측할 수 있으므로 페이지 우선 적재 전략을 사용할 수 있음
• DBMS는 페이지를 디스크에 강제 출력할 수 있어야 함
  • 손상 복구를 위한 WAL 규약을 실현할 수 있음

 

6. 레코드 형식

 

1. 고정 길이 레코드

• 각 필드의 길이가 고정적이고 필드의 수도 고정된 레코드 형식
• 필드를 레코드에 연속적으로 저장
  

2. 가변 길이 레코드

• 필드의 길이가 가변적인 경우 해당 레코드의 길이가 가변적이 됨
• 필드를 분리자로 구분하여 연속적으로 저장
  
• 레코드의 앞부분에 정수로 된 오프셋들을 배열로 저장

image:./images/image08.png[] 

 

7. 페이지

 

1. 페이지 형식

• 페이지는 레코드가 탑재되는 슬롯의 모임으로 생각할 수 있음
• 레코드는 <페이지 번호, 슬롯 번호>의 쌍으로 식별됨
• <페이지 번호, 슬롯 번호>의 쌍을 RID라고 하며, 레코드의 포인터 역할을 수행

2. 고정 길이 레코드

• 고정 길이 레코드에만 탑재 될 경우 슬롯은 같은 형태이며, 연속적으로 배치 가능하다.
• 레코드가 페이지로 삽입될 때는 빈 슬롯을 할당하고 할당된 슬롯에 레코드를 삽입
• 빈 슬롯(자유 슬롯)을 어떻게 알 수 있는지에 대한 두 가지 방법
  

3. 가변 길이 레코드

• 레코드가 가변 길이이면 페이지를 고정된 길이의 슬롯으로 분할할 수 없음
• 슬롯 마다 <레코드 오프셋, 레코드 길이>의 형태로 슬롯 디렉토리를 유지
• 빈 공간의 시간을 가리키는 포인터 유지
  

 

8. 파일과 인덱스

 

힙 파일

• 가장 간단한 파일 구조로, 레코드가 파일의 빈 공간에 순서 없이 저장
• 페이지 내의 데이터가 어떠한 형태로도 정렬되지 않으며, 파일의 모든 레코드를 검색하면 다음 레코드를 되풀이해서 요청해야 함
• 파일의 레코드는 각기 유일한 rid를 가지며, 한 파일에 속하는 페이지는 크기가 모두 같음
• 파일의 생성(Create)과 제거(Destroy), 레코드의 삽입(Insert)과 rid를 통한 레코드 삭제(Delete), rid를 통한 레코드 선택(get), 파일 내의 모든 레코드 스캔(Scan) 연산 지원

인덱스 개요

• 대부분의 자료 구조에서는 저장된 데이터의 rid를 직접 알 수 없음
• 정렬되지 않은 자료 구조에서 동등 검색을 수행할 경우, 전체 자료 구조를 스캔해야 함
• 인덱스(Index)
  선택(Selection) 조건에 맞는 rid를 구할 수 있도록 만든 보조 자료 구조
  

ISAM

• 색인 순차 접근 방식(Indexed Sequential Access Method) 파일
• 데이터를 순서대로 저장하거나 특정 항목을 색인으로 처리할 수 있는 파일 처리 방법
• 인덱스를 순차적으로 구성하여 큰 인덱스의 성능 문제를 해결
  • 인덱스 파일이 클 경우, 인덱스를 계층화하여 인덱스에 대한 인덱스를 생성
  • 완전한 정적 구조로, 인덱스 계층의 페이지가 수정되지 않음
• 파일 구조
  • 인덱스 구역(비 단말 페이지)
    기본 구역에 있는 레코드들의 위치를 찾아가는 인덱스가 기록되는 구역
  • 기본 구역(기본 단말 페이지)
    실제 레코드들을 기록하는 부분으로, 각 레코드는 키 값 순으로 저장
  • 오버플로우 구역(오버 플로우 페이지)
    기본 구역에 빈 공간이 없을 경우 새 레코드의 삽입을 위한 예비적 구역

 

9. B+ 트리

• ISAM의 오버 플로의 단점을 개선한 동적 트리 자료구조
• 내부 노드들이 탐색 경로를 유도하고 단말 노드들이 데이터 엔트리를 가지는 균형 트리
  • 트리에서 삽입, 삭제를 수행해도 트리의 균형이 유지됨
  • 레코드를 탐색할 때 루트로부터 알맞은 단말 까지만 가면 됨
• 일반적으로 ISAM보다 우수한 구조
  

 

10. 시스템 카탈로그

• 데이터베이스는 자신이 가지고 있는 모든 데이터에 대한 설명 정보를 저장함
• 관계형 데이터베이스 관리 시스템은 생성된 모든 릴레이션과 인덱스에 대한 정보를 유지 관리
• 시스템 카탈로그(System Catalog), 데이터 사전(Data Dictionary), 마스터 데이터베이스(Master Database), 메타데이터(Metadata)라고도 부름

 

파일 조직과 인덱스

 

1. 비용 모델과 파일 조작법

 

비용 모델 개요

• 데이터베이스에서는 질의가 요청될 때 여러 실행계획을 세우고 최적화된 방법을 찾아 실행
• 쿼리 최적화기는 쿼리 기반, 비용 기반 등의 모델로 실행 계획을 비교
• 비용 측정
  • 데이터 페이지의 개수 B, 페이지에 속한 레코드의 개수 R, 디스크 페이지를 하나를 읽는 시간을 D로 가정
  • 디스크 페이지 하나를 쓰는데 걸리는 평균 시간 D, 한 레코드를 처리하는데 걸리는 시간 C
  • 한 레코드에 해시 함수를 적용하는데 걸리는 시간 H
• 여기에서는 파일 입출력 비용만 감안하여 파일 조직 별 비용을 비교

파일 조직법 비교 기준 연산

• 스캔(Scan)
  파일에 있는 모든 레코드를 가져옴. 파일에 있는 페이지들은 디스크로 부터 버퍼 풀로 반입 되어야함
• 동등 셀렉션(Equality Selection)
  질의에서 요구하는 검색어와 같은 문자열임을 만족하는 모든 레코드를 가져옴
• 범위 셀렉션(Range Selection)
  1에서 10까지, 홍길동에서 이순신까지 등 범위에 해당하는 모든 레코드를 가져옴
• 삽입(Insertion)
  주어진 레코드를 파일에 삽입
• 삭제(Deletion)
  RID로 명세된 레코드 삭제

힙 파일

• 정렬되지 않은 단순한 형태의 파일
• 스캔 B(D+RC)
• 동등 셀렉션 후보 키에 대한 연산일 경우 0.5B(D+RC). 후보 키가 아닌 경우 스캔과 동일
• 범위 셀렉션 스캔과 동일
• 삽입 레코드가 항상 파일의 끝에 삽입된다고 가정할 경우 2D+C
• 삭제 탐색 비용 + C + D

정렬 파일

• 특정 필드를 기준으로 정렬된 파일
• 스캔
  힙 파일과 다르지 않음. B(D+RC)
• 동등 셀렉션
  정럴 기준 필드로 검색할 경우 이진 탐색으로 Dlog2B + Clog2R. 정렬 필드가 아닌 경우 스캔과 동일
• 범위 셀렉션
  정렬 기준 필드로 검색할 경우 첫 레코드를 찾는데 동등 셀렉션과 동일. 이후 범위내 스캔
• 삽입
  정렬 순서를 유지하기 위해 레코드가 삽입될 위치를 검색 후 레코드 추가. 후속 페이지를 모두 로드하여 다시 저장. 탐색 비용 + B(D + RC)

해시 파일

• 특정 필드를 기준으로 정렬된 파일
• 스캔
  힙 파일과 다르지 않음. B(D+RC)
• 동등 셀렉션
  정럴 기준 필드로 검색할 경우 이진 탐색으로 Dlog2B + Clog2R. 정렬 필드가 아닌 경우 스캔과 동일
• 범위 셀렉션
  정렬 기준 필드로 검색할 경우 첫 레코드를 찾는데 동등 셀렉션과 동일. 이후 범위내 스캔
• 삽입
  정렬 순서를 유지하기 위해 레코드가 삽입될 위치를 검색 후 레코드 추가. 후속 페이지를 모두 로드하여 다시 저장. 탐색 비용 + B(D + RC)

파일 조직 선택

• 힙 파일은 저장 성능이 우수하고 스캔, 삽입, 삭제 연산이 빠르지만 탐색은 느리다.
• 정렬 파일은 저장 성능이 우수하고, 삽입과 삭제 연산이 느리지만 탐색은 매우 빠르다.
• 해시 파일은 저장 성능이 떨어지지만, 삽입과 삭제가 빠르며 동등 탐색에서 대단히 우수하다. 하지만 범위 탐색은 지원하지 못하며 스캔 성능이 떨어진다.

 

2. 인덱스

• 해당 파일의 기본적인 레코드 조직법으로는 효율적으로 지원되지 않는 연산의 속도를 높이기 위해 만드는 보조적인 자료구조
• 데이터 엔트리(Data Entry)들의 모임

클러스터드 인덱스

• 파일을 조직할 때 레코드의 순서를 파일에 대한 인덱스의 순서와 동일한 순서로 유지 (MySql PK)
• 파일의 재조직이 필요한 구조
• 데이터가 삽입/삭제될 때 마다 정렬 순서를 유지하기 위해서 그 주변의 데이터를 이동해야 함
• 파일이 동적으로 변하는 경우 유지 관리 오버헤드가 높음
  

Non 클러스터드 인덱스

• 하나의 데이터 파일은 하나의 탐색키에 대해서만 클러스터링 될 수 있음
• 하나의 데이터 파일에 대해 하나의 클러스드 인덱스만 만들 수 있음
• 클러스터드 인덱스 구조 파일의 키가 아닌 필드의 빠른 검색을 위한 보조 자료구조

기본 인덱스와 보조 인덱스

• 기본 키를 포함한 필드들에 대한 보조 인덱스를 기본 인덱스라고 부름
  • 기본 키가 존재하는 테이블은 기본 키가 클러스터드 인덱스가 되고 해당 자료구조로 테이블을 조직하는 DBMS도 있음
  • 기본 키를 희소, 클러스터드 인덱스로 지정하는 DBMS도 있음
• 기본 키 이외의 인덱스들을 보조 인덱스로 부름
  • 동일한 탐색 키 필드에 대해 데이터 엔트리가 두 개 존재하는 경우 중복되었다고 함
  • 키 필드가 아닌 필드에 대한 인덱스에는 중복이 나타날 수 있음
• 해당 탐색 키에 후보 키가 포함되는 경우, 그 키에 대한 인덱스를 유일 인덱스라고 부름

복합 키 인덱스

• 인덱스가 여러 개의 필드를 포함하는 경우 복합 키(Composite Key) 또는 접합 키(Concatenated Key)라고 부름
• 데이터 조직과 쿼리 형태에 따라 높은 성능을 보임