[ DB ] Chapter 13. Data Storage Structures

1. File Organization

 

데이터베이스는 여러 파일들로 이루어져 있으며 이는 영구적으로 디스크에 저장된다. 파일은 record로 이루어져 있으며 이들은 디스크 block에 mapping 되어있다. 대부분 블록의 크기는 4KB 혹은 8KB이다. record들이 어떻게 저장되는지 살펴보자.

Fixed-Length Records

이는 record의 길이가 고정되어있는 table이다. 간단하지만 길이가 고정되어 있어 넣을 수 있는 data가 한정적이다.

deletion을 하는 3가지 방법이 있다.

• 지우고 밑에 있는 record들 땡기기 → 순서는 유지되지만 오버헤드가 크다
• 지우고 마지막에 있는 레코드 빈자리에 넣기 → 순서가 유지 되지 않는다
• free list : 빈공간들끼리 linked list로 관리한다.

 

Variable-Length Records

다양한 레코드 타입을 수용하기 위해 길이가 고정되지 않은 레코드를 사용한다. 레코드마다 <offset, length> 값을 고정된 길이에 저장하여 레코드의 위치와 길이를 기록한다.

 

Slotted page struct

우리는 Slotted page struct를 이용하면 가변길이의 레코드를 정렬된 형태로 저장할 수 있다.

 

Block header에는 다음와 같은 정보가 들어있다

• 저장된 레코드의 개수
• free space의 끝 위치
• 레코드의 크기와 offset

 

레코드는 free space의 뒤에서 부터 채워지고 레코드에 대한 정보는 free space의 앞에서부터 채워진다.

새로운 레코드가 들어오면 레코드는 들어온 순서대로 free space의 뒤에서부터 채워지고 그에 대한 정보는 free space의 앞에, key에 대해 정렬된 상태로 삽입된다.

 

Storing large object

하나의 page크기를 넘길만큼 큰 객체가 들어오면 다음과같이 처리할 수 있다.

• 파일시스템에 파일로 저장하기
• DB가 관리하는 파일로 저장하기
• 분할해서 여러개의 page에 보관하기

 

---

 

2. Organization of Records in Files

 

record들이 어떻게 저장되는지를 봤다. 이번에는 이 레코드들이 모여져서 만든 relation이 어떻게 저장되는지 살펴보자.

 

Heap File Organization

여기서는 레코드는 파일의 어디든 저장될 수 있으며 한번 저장되면 이동하지 않는다. 항상 파일의 끝에 새로운 레코드를 추가한다. 이 때 DB는 모든 블럭을 순차적으로 검색할 필요 없이 빈 블럭을 효율적으로 찾을 수 있어야한다.

 

빈 블럭을 효율적으로 찾기 위해 Free-space map을 사용한다.

 

각 블럭에 빈 공간의 개수를 모아 배열을 만든다. 블럭이 많아지면 이 또한 오버헤드가 커진다.

그 후로는 배열을 4개씩 잘라 그 중 최대값만 모아 second-free space map을 만든다.

 

Sequential File Organization

이는 search-key를 기준으로 정렬되어있어, 순차적으로 파일을 읽어야할 때 효율적이다.

여기서 search-key는 super key거나 primary key일 필요는 없다.

각 레코드가 다음 레코드를 순차적으로 가르키고 있는 형태이다. 블록 액세스 수를 최소화 하기 위해 키 순서에 따라 물리적으로도 가깝게 저장하고자 한다.

이는 우리가 아는 linked list의 형태이다. 삽입, 삭제 모두 linked list와 동일한 형태이고 삽입할 공간이 부족해지면 overflow block을 사용한다.

 

Multitable Clustering File Organization

이는 여러개의 relation을 하나의 파일에 저장하는 방법이다. 보통 한 파일에 한 relation이 저장되지만 가끔은 한 파일에 두개의 relation이 들어있는게 더 효율적일 때도 있다.

두개의 relation을 natural join한 형태와 관련된 쿼리를 수행할 때는 매우 적합하지만, 하나의 relation에만 접근할때는 비효율적이다.

 

Column-Oriented Storage

 

이는 relation의 열별로 저장하는 방법이다.

 

Data Dictionary

이는 data dictionary라는 구조에는 data의 data인 metadata가 들어있다. 이는 system catalog라고도 부르며 metadata를 relation처럼 저장하고있다. metadata에는 relation의 정보와 유저정보, 파일 정보 등을 담고 있다.