Chapter 16: 디스크 저장 및 기본 파일 구조

개요

물리적 데이터베이스 디자인

저장 계층 구조
디스크 아키텍처
버퍼 관리

기본 파일 구조: 기본 파일 조직

힙 파일
정렬 파일
해시 파일 (시간이 남을 경우에 다룸, 그렇지 않으면 대학원 수업에서 다룸)

Introduction (소개)

데이터베이스는 일반적으로 자기계단 디스크에 저장됩니다.

데이터베이스는 물리적 데이터베이스 파일 구조를 사용하여 액세스됩니다.

물리적 데이터베이스 디자인의 과정은 다양한 옵션 중에서 애플리케이션 요구 사항과 가장 적합한 데이터 조직 기술을 선택하는 것을 포함합니다.

오늘과 다음 수업에서는 다음과 같은 내용을 공부합니다.

저장소에 데이터베이스의 주요 구성
파일에 레코드를 물리적으로 저장하는 방법
다양한 알고리즘을 사용하여 효율적으로 데이터에 액세스하는 방법
일부 알고리즘은 색인이라고 불리는 보조 데이터 구조를 필요로 합니다.

Storage Hierarchy (저장 계층)

데이터베이스를 구성하는 데이터 모음은 어떤 컴퓨터 저장 매체에 물리적으로 저장되어야 합니다.

DBMS(예: Oracle) 소프트웨어는 이 데이터를 필요에 따라 검색, 업데이트 및 처리할 수 있습니다.

컴퓨터 저장 매체는 저장 계층을 형성합니다.

주 저장소: 중앙 처리 장치(CPU)가 작동하는 곳

CPU(레지스터), 캐시 메모리, RAM(랜덤 액세스 메모리)

보조 저장소: 비휘발성으로, 주 저장소보다 저렴

하드 디스크 드라이브 (HDD), (USB) 플래시 메모리, 솔리드 스테이트 드라이브 (SSD)

제 3 저장소: 가장 저렴하지만 가장 느림

탈착식 미디어: 테이프, 광학 디스크 (CD-ROM, DVD 등)

Storage Organization of Databases (데이터베이스의 저장 구성)

영구 데이터 (비휘발성)

대부분의 데이터베이스는 일반적으로 오랜 기간 동안 지속되는 대량의 데이터를 저장합니다.
주로 자기계단 및/또는 SSD 디스크의 보조 저장소에 저장됩니다. 왜?

일반적으로 DB는 전체적으로 주 메모리에 맞지 않습니다.

비휘발성; 전원이 꺼져도 사라지지 않음

데이터 단위당 저장 비용: 주 저장소보다 10배 저렴합니다.

데이터의 일부는 처리를 위해 디스크에서 RAM으로 로드되고 디스크로 다시 기록됩니다.
디스크에 저장된 데이터는 레코드 파일로 구성됩니다.
각 레코드는 엔터티에 대한 사실을 나타내는 데이터 값의 모음입니다.
레코드는 효율적인 액세스를 위해 디스크에 잘 배치되어야 합니다.
휘발성 데이터와 대조적인 일시적 데이터 (휘발성 데이터) 존재. 프로그램 실행 중에만 존재하며, malloc() 등이 해당됨.

Primary file organization (기본 파일 조직)

힙 파일 (비순서 파일)

레코드를 임의로 배치합니다.

정렬 파일 (순차 파일)

레코드를 정렬 기준 필드에 값을 추가하여 파일 끝에 추가합니다.

해시 파일

해시 키 필드에 해시 함수를 적용하여 디스크에 배치합니다.

트리 구조 파일 (B-트리)

열 기반 파일

기본 파일 조직은 파일 레코드가 디스크에 물리적으로 배치되는 방식과 레코드에 어떻게 액세스할 수 있는지를 결정합니다.

Secondary organization (or auxiliary access structure) (보조 조직 또는 보조 액세스 구조)

기본 파일 조직과는 다른 필드를 기반으로 파일 레코드에 효율적으로 액세스할 수 있도록 허용합니다.

이러한 대부분은 인덱스입니다.

무정렬 순차 파일 (Unsorted Sequential File):

디스크에 특별한 순서 없이 레코드를 배치합니다.
새로운 레코드는 파일의 끝에 추가됩니다.

정렬 순차 파일 (Sorted Sequential File):

정렬 키 필드의 값에 따라 레코드 순서를 유지합니다.
이 방식은 레코드를 특정 키 필드의 값에 따라 정렬하여 저장합니다.

해시 파일 (Hashed File):

해시 키 필드에 적용된 해시 함수를 사용하여 디스크 상의 위치를 결정합니다.
이 방식은 해시 함수를 사용하여 각 레코드의 저장 위치를 결정하며, 빠른 검색을 위해 사용됩니다.

SECONDARY STORAGE DEVICES (보조 저장 장치)

Disk Storage: 비휘발성, 회전하는 자기 저장 매체

디스크: 무작위 액세스 가능한 장치
RAM과 데이터를 디스크 블록의 단위로 전송할 수 있음
블록(또는 섹터) 주소는 실린더 번호, 트랙 번호(플래터 내에서), 블록 번호(트랙 내에서)로 구성됨 (또는 블록 내의 섹터 번호)
블록 주소는 디스크 I/O 컨트롤러에 제공됨
많은 현대 디스크 드라이브에서는 컨트롤러에 의해 논리 블록 주소(LBA, Logical Block Address)가 자동으로 올바른 블록에 매핑됨

Disk read (디스크 읽기)

원하는 디스크 블록을 LBA와 함께 디스크 드라이브 버퍼로 복사함

Disk write (디스크 쓰기)

버퍼의 내용이 LBA를 가진 디스크 블록으로 복사됨

Disk Storage: Internal Architecture (디스크 저장소: 내부 아키텍처)

실린더

디스크는 자기 플래터의 스택입니다.
각 플래터의 표면은 여러 트랙으로 구성됨
트랙은 섹터로 나뉨
섹터: 저장의 기본 단위로 구성되며 섹터 ID, 데이터 (일반적으로 512 바이트), 오류 수정 코드, 동기화 필드 또는 갭(다음 섹터의 섹터 번호)를 포함함
블록(또는 페이지): 섹터의 그룹 (읽기/쓰기 단위로), 일반적으로 4K 바이트

Actuator (액추에이터)

동일한 실린더 내의 원하는 트랙으로 디스크 헤드를 이동하려면 스핀들이 회전하여 원하는 섹터를 찾아야 함

대부분의 디스크 컨트롤러에는 성능 향상을 위한 내장 캐시가 있음

Disk Access Time (디스크 액세스 시간)

세 가지 주요 구성 요소

시크 타임: 디스크 헤드를 원하는 트랙으로 이동하는 데 걸리는 시간
회전 지연: 원하는 섹터가 회전하여 (읽기/쓰기) 헤드 아래로 이동하기를 기다리는 시간

보통 전체 회전 시간의 절반으로 가정됨 (왜냐하면?)

전송 시간: 비트 단위의 디스크 블록을 전송하는 데 걸리는 시간

섹터 크기, 회전 속도 및 기록 밀도에 따라 다름
100 (랜덤 읽기/쓰기) ~ 500 (순차 읽기/쓰기) MB/초

또한 다른 액세스가 존재하거나 디스크 컨트롤러 오버헤드로 인한 "대기 시간"이 있을 수 있음

예: 512B 섹터, 7,200rpm, 4ms 평균 시크 타임, 100MB/s 전송률, 0.2ms 컨트롤러 오버헤드, 비활성화된 디스크

질문: 이 디스크에서 섹터를 "읽을" (또는 "쓸") 때 기대되는 시간은 어떻게 될까요?

BUFFERING OF BLOCKS (블록 버퍼링)

버퍼는 디스크 블록을 받아들일 수 있는 주 메모리의 일부를 가리킵니다.

Buffer Management (버퍼 관리)

DBMS (데이터베이스 관리 시스템)의 버퍼 관리자 (BM)

데이터 요청에 응답

(i) 어떤 버퍼를 사용할 것인지 및 (ii) 새로운 페이지를 수용하기 위해 버퍼에서 교체해야 할 페이지를 결정합니다.

사용 가능한 주 메모리 저장 공간을 버퍼 풀로 간주합니다.

각 페이지에 대한 두 가지 유형의 정보를 유지합니다.

핀 카운트 (Pin-count): 페이지가 요청된 횟수 (또는 해당 페이지의 동시 사용자 수); 초기에는 0

핀 카운트 증가 (Pinning): 핀 카운트를 증가시킵니다.

카운트가 0으로 떨어지면 언핀됩니다. 그렇지 않으면 연결된 페이지를 제거할 수 없습니다.

더티 비트 (Dirty bit): 초기에는 0이지만 프로그램에 의해 해당 페이지가 업데이트될 때 1로 설정됨

특정 페이지가 요청될 때...

버퍼 관리자는 요청된 페이지가 이미 버퍼 풀의 버퍼에 있는지 확인합니다.

페이지가 존재하면 관리자는 해당 페이지의 핀 카운트를 증가시키고 페이지를 해제합니다.

페이지가 존재하지 않고 풀이 가득 찬 경우, 관리자는 다음과 같은 작업을 수행합니다. a) 교체 페이지를 선택하고 교체 정책을 사용하여 해당 페이지의 핀 카운트를 증가시킵니다 (곧 논의됨). b) 교체 페이지의 더티 비트가 ON인 경우, 관리자는 해당 페이지를 디스크에 기록하여 (디스크의 이전 복사본을 대체함) 디스크에 기록합니다. (비트가 OFF인 경우 디스크로 다시 기록할 필요가 없습니다. 왜냐하면?) c) 요청된 블록을 방금 해제된 (클린) 페이지로 읽어옵니다. d) 새 페이지의 주 메모리 주소가 요청자에게 전달됩니다.

언핀된 페이지가 없고 버퍼 풀에서 요청된 페이지를 사용할 수 없는 경우, 관리자는 (페이지가 사용 가능할 때까지) 대기해야 합니다.

Buffer Replacement Strategies (버퍼 교체 전략)

인기 있는 버퍼 교체 전략

가장 최근에 사용되지 않은 페이지를 제거하는 "최근에 사용하지 않은 것" (LRU) (가장 일반적인 방법)
가장 오래된 시간 동안 사용되지 않은 페이지를 제거합니다.
먼저 들어온 것을 먼저 내보내는 "먼저 들어온 것" (FIFO)
가장 오랫동안 사용된 페이지를 교체합니다.
[주의] 인덱스의 루트 블록이 제거될 수 있지만 대부분 다시 가져올 것입니다...
시계 정책 (Clock policy): LRU의 라운드 로빈 변형
각 버퍼가 사용되지 않음(0) 또는 사용됨(1)의 값을 가질 수 있다고 가정합니다.
0 값을 가진 플래그가 있는 버퍼를 라운드 로빈 방식으로 찾습니다. 어떻게?
시계 바늘이 "현재 버퍼"에 위치합니다.
새 블록의 버퍼가 요청되면 버퍼 관리자는 0 값을 가진 버퍼를 찾을 때까지 바늘을 회전시킵니다.
시계가 1을 가진 버퍼를 지나가면 그 값을 0으로 설정합니다.
버퍼의 블록은 손이 한 바퀴 회전하고 다시 돌아와 0으로 설정된 마지막 블록을 찾을 때만 교체됩니다.

File and File Header (파일 및 파일 헤더)

파일: 레코드의 연속입니다.

파일 헤더 (디스크립터)

파일 레코드에 접근하는 시스템 프로그램에서 필요한 파일에 대한 정보를 포함합니다.

어떤 정보?

파일 블록의 디스크 주소를 결정하기 위한 정보
레코드 형식에 대한 설명을 기록합니다. (예: 필드 길이, 레코드 내 필드 순서, 고정 길이의 레코드의 경우 필드 유형 코드, 구분 문자 및 가변 길이 레코드의 경우 레코드 유형 코드)

데이터베이스 (테이블) 파일

헤더 레코드 1 레코드 2

헤더

레코드 1

레코드 2

레코드 k

Records and Record Type (레코드 및 레코드 유형)

레코드: "관련된" 데이터 값 또는 항목의 집합

값은 레코드 필드 (또는 튜플 속성)에 해당합니다.

레코드 유형 (형식)

(i) 필드 이름 및 (ii) 해당 데이터 유형을 포함하는 집합

예: C 스타일 표기법에서의 EMPLOYEE 레코드 유형

데이터 유형: 숫자, 문자열, 부울, 날짜/시간 등...

이진 대형 객체 (BLOBs): 구조화되지 않은 객체 (이미지, 비디오 또는 오디오 스트림)

BLOB 데이터 항목: 레코드와 별도로 디스크 블록 풀에 저장되며, 레코드 내의 BLOB에 대한 포인터가 유지됩니다.

문자 대형 객체 (CLOBs): 자유 텍스트 저장에 사용

Fixed-Length Records vs Variable-Length Records (고정 길이 레코드 대 가변 길이 레코드)

고정 길이 레코드

파일의 모든 레코드는 정확히 동일한 크기 (바이트)를 가집니다.

가변 길이 레코드

파일 내에서 서로 다른 레코드는 서로 다른 크기를 가집니다.

가변 길이 레코드를 사용하는 이유는 다음과 같습니다.

하나 이상의 필드가 가변 길이를 가짐: 예를 들어 VARCHAR

하나 이상의 필드가 반복됨: 예를 들어 배열

하나 이상의 필드가 선택적임

파일에 서로 다른 유형의 레코드가 포함되어 있음

Record Blocking and Spanned vs. Unspanned Records (레코드 블로킹 및 스펀드 vs. 언스판 레코드)

파일의 레코드는 반드시 디스크 블록에 할당되어야 합니다.

왜냐하면? 블록은 디스크와 메모리 간의 데이터 전송 단위이기 때문입니다.

|block| >= |record| 인 경우, 각 블록에는 여러 레코드가 포함됩니다.

스펀드 레코드

하나의 블록 (페이지: 4K 또는 8K)보다 큽니다.
블록을 넘어가는 것이 가능합니다.
첫 번째 블록 끝에있는 포인터는 나머지 레코드를 가리키도록 설정됩니다.

언스판 레코드

레코드가 블록보다 작을 때 사용됩니다.
레코드는 블록 경계를 넘어갈 수 없습니다.

Blocking factor (블록 팩터): 파일당 블록 당 평균 레코드 수

일부 미사용 공간 = B - (bfr * R) 바이트, 여기서

B: 블록 크기, R: 레코드 크기 및 bfr: 파일의 블록 팩터

bfr은 r 레코드를 포함하는 파일에 필요한 블록 수 b를 계산하는 데 사용될 수 있습니다.

b = 올림(r / bfr) 블록, 여기서

r: 파일의 레코드 수

Q: 1000 개의 레코드를 포함하는 파일을 저장하는 데 몇 개의 블록이 필요한가요?

레코드 크기: 16 바이트

블록 크기: 4 K바이트

사용되지 않는 공간: 0 바이트 (편의상)

bfr은 얼마인가요?

FILES OF UNORDERED RECORDS (HEAP FILES) (정렬되지 않은 레코드 파일)

힙 (또는 파일) 파일

가장 간단하고 기본적인 유형의 구조

레코드는 그들이 삽입된 순서대로 파일에 배치됩니다.

새 레코드는 파일의 끝에 삽입됩니다.

새로운 레코드를 삽입하는 것은 매우 효율적입니다.

파일의 마지막 디스크 블록이 버퍼로 복사됩니다.

새 레코드가 추가됩니다.

그런 다음 블록이 디스크로 다시 기록됩니다.

마지막 파일 블록의 주소가 파일 버퍼에 유지됩니다.

그러나 레코드를 "검색"하는 것은 선형 검색 때문에 비효율적입니다.

평균적으로 (b / 2)이며, 여기서 b는 파일의 블록 수입니다.

최악의 경우, b 파일 블록이 방문됩니다.

Heap (or Pile) File (힙 또는 파일 파일) (계속)

레코드를 "삭제"하는 한 가지 방법은 프로그램이 해당 블록을 찾아야 합니다.

블록을 버퍼로 복사합니다.

레코드를 버퍼에서 삭제하고 마지막으로 블록을 디스크로 다시 기록합니다.

다른 방법: 삭제 표시자 사용

각 레코드와 함께 추가 비트 또는 바이트를 저장합니다.

특정 값을 설정하여 레코드를 삭제합니다.

마커의 다른 값은 유효한 레코드를 나타냅니다.

검색은 블록 내의 유효한 레코드만 고려합니다.

두 가지 접근 방식 모두 삭제된 레코드의 미사용 공간을 정기적으로 재조직하여 회수해야 함을 의미하며, 기존에 삭제되지 않은 레코드의 패킹을 포함합니다.

세 번째 방법: 삭제된 레코드의 공간을 삽입에 사용하는 방법

Heap File Implementation (힙 파일 구현):

목록 사용 (page id)

어떤 문제가 있을까요?

가득 찬 페이지

빈 공간이 있는 페이지

데이터 페이지

데이터 페이지

데이터 페이지

헤더 페이지

데이터 페이지

데이터 페이지

데이터 페이지

<힙 파일 이름, 페이지 1 주소>는 어딘가에 저장되어야 합니다.

DBMS는 디스크에 이러한 쌍을 포함하는 테이블을 유지할 수 있습니다.

각 페이지에는 데이터와 함께 2 개의 포인터 (또는 페이지 ID)가 포함됩니다.

Heap File Implementation (힙 파일 구현): 2) 페이지 디렉터리 사용 (헤더 페이지, 데이터 페이지 1, 데이터 페이지 2, 디렉토리)

각 디렉터리 항목은 힙 파일에서 페이지 (예: 페이지 ID X)를 식별합니다.

페이지의 항목은 페이지의 빈 바이트 수를 포함할 수 있습니다.

디렉터리는 페이지의 컬렉션입니다. 연결 목록 구현은 대안 중 하나입니다.

이점: 모든 HF (힙 파일) 페이지의 링크 목록보다 훨씬 짧습니다.

Sorted (Sequential) Files (정렬된 (순차) 파일):

파일의 레코드를 디스크상에서 하나의 필드, 즉 정렬 필드(ordering field)의 값에 따라 "물리적으로" 정렬(정렬)합니다.

정렬 키(ordering key): 정렬 필드가 파일의 키 필드인 경우

중복되지 않는 이름을 가정한 경우, 정렬 키 필드로 Name을 사용하여 정렬된 파일을 나타냅니다.

이로써 된 파일의 장점(힙 파일 대비)

정렬 키를 기준으로 레코드를 읽는 것이 매우 효율적입니다.

정렬이 필요하지 않으며 키에 대한 검색/범위 조건에 우수합니다.

다음 레코드를 찾는 것은 블록에 대한 추가적인 액세스가 필요하지 않습니다(레코드가 블록의 마지막인 경우 제외).

이로 인해 정렬 키의 값을 기준으로 검색을 수행하기 위해 이진 검색 기술을 사용할 수 있으므로 "빠른 액세스"가 가능합니다.

정렬 키를 사용한 이진 검색 기술 예시:


l = 1; u = b; // b: 블록 수
while (u >= l) {
    i = (l+u)/2;
    파일의 i번째 블록을 버퍼에 읽어옴.
    if (K < i번째 블록의 첫 번째 레코드의 정렬 키 필드 값) then u = i-1;
    else if (K > i번째 블록의 마지막 레코드의 정렬 키 필드 값) then l = i+1;
    else if (K == 정렬 키 필드 값) then break; // 찾음
    else break; // 찾지 못함
}

삭제: 포인터 체인 또는 삭제 표시자 활용

삽입: 레코드를 삽입할 위치를 찾음

여유 공간이 있는 경우 해당 위치에 삽입

여유 공간이 없는 경우 레코드를 오버플로우(또는 트랜잭션) 블록에 삽입

어느 경우든지 포인터 체인을 업데이트해야 함

순차적인 순서를 복원하기 위해 파일을 때때로 재조직해야 함

평균 액세스 시간 (basic file organizations의 블록 수 b에 대한 평균 액세스 시간):

주요 포인트:

메모리 계층의 특성

보조 저장 장치

디스크 구조 및 디스크 액세스 시간

버퍼 관리: 더블 버퍼링과 버퍼 풀링

파일 레코드를 디스크에 배치하는 방법: 고정 길이와 가변 길이

여러 가지 주요 파일 구성