Data Storage Structures

File Organization

데이터 베이스는 file형태로 저장됩니다.

각 file은 record의 일련입니다. 

record는 field의 일련입니다.

 

simple approach

record 사이즈가 고정된다고 가정합니다. (ex 53 byte)

각 file은 하나의 특별한 type을 가지는 record를 가집니다.

서로 다른 relation에는 서로 다른 file이 사용됩니다.

 

이러한 case는 간단한 구조입니다. 우리는 나중에 variable한 record 형태를 배우게 될 것입니다.

 

우리는 disk block(ex 512 byte)보다 작은 record를 가정해봅니다.

각 문자는 1 byte를 차지합니다. 

그리고 numeric(8, 2)는 8 byte를 차지합니다.

우리는 각 attribute가 최대 byte를 할당한다고 가정합니다.

그러면 instructor record는 최대 53 byte를 가질 수 있습니다. 

위에서 본 simple approach은 첫 record에 53 byte를 사용하고 다음 53 byte는 두번째 record를 위한것입니다.

 

Fixed-Length Records

i번째 record는 n * (i -1) byte 부터 시작합니다. n은 각 record의 size입니다. (ex : 53 byte)

block 경계를 record 끼리 넘을 수 없습니다.

예를 들어 block = 100 byte일 때 1개의 record = 53 byte이면 2 block이 1 block을 넘어가게 됩니다.

2 record = 106 이고 6 byte가 넘어가게 됩니다.

Deletion of record i : i번째 record 삭제 (ex 3번째 record 삭제)

1) i + 1 번째 record 부터 n-1번째 record 까지 한칸 씩 땡깁니다.

3번째 record가 삭제되므로 비워진 자리를 4번째 record부터 하나하나 이동시켜 땡기기 때문에 오래 걸립니다.

2) n번째 record 에서 i번째 record로 이동합니다.

마지막 record가 삭제된 record위치로 채워줍니다. 1번째 방법 보다는 좋습니다.

3) record를 이동하지 않고 free된 record 끼리 link 해 놓습니다.

가장 좋은 방법입니다.

Variable-Length Records

variable-length record는 데이터베이스 시스템에서 몇몇 방식으로 나타납니다.

attribute들은 정렬된 방식으로 저장됩니다.

variable length attribute들은 (offset, length) 된 형태로 고정된 형태로 나타냅니다.

NULL 값은 null 값 bitmap으로 표현됩니다.

(ex : 0001이면 1번째 attribute가 null인경우, 0101이면 1번째, 3번째 attribute가 null인경우)

 

Variable-Length Records : Slotted Page Structure

header는 record의 개수, free space의 끝 지점, 각 record의 위치와 크기를 갖습니다.

 

page내에서 record를 이동하여 빈 공간없이 연속적으로 유지할 수 있습니다.

그럴 경우 header의 항목을 업데이트 해야합니다.

block에 공간이 있는 한 record를 확대하거나 축소할 수 있습니다.

block의 크기가 제한되어 있기 때문에 record를 이동하는데 드는 비용은 그리 높지않습니다.

일반적인 값은 약 4 ~ 8 kb입니다.

포인터는 record를 직접 가리키면 안됩니다. 대신에 header의 record에 대한 항목을 가리켜야 합니다.

 

Organization of Records in Files

file안에 record를 저장하는 방식입니다.

Heap, Sequential, B+ tree, Hashing

 

Heap File Organization

사용 가능한 공간이 있는 file의 아무곳에나 record를 배치할 수 있습니다.

record는 일반적으로 한번 할당되면 이동하지 않습니다.

file내에서 사용 가능한 공간을 효율적으로 찾을 수 있는 것이 중요합니다.

 

Free-space map

record를 저장할 수 있는 여유 공간이 있는 block을 추적하는 것입니다.

한 칸 당 free한 공간을 나타냅니다.

만약 4이면 4개의 free공간이 있다는 것입니다. 

2단계 free-space map을 가질 수 있습니다.

위의 2단계 free-space map은 1단계 free-space map의 4개 항목에서 최대값을 저장합니다.

disk에 주기적으로 기록되는 free space map 일부 항목에 대해 잘못된(이전)값이 있으면 확인(탐지 및 수정)

 

Sequential File Organization

전체 file을 순차적으로 처리해야하는 응용프로그램에 적합합니다.

search-key로 record를 정렬합니다.

아래의 record는 맨 왼쪽의 primary key에 따라 정렬됩니다.

pointer 체인을 사용해 delete, insetion합니다.

만약 record가 많아져 block을 초과(overflow)할 경우 새로운 block을 생성해 거기다가 record를 넣습니다.

순차적인 순서를 유지하기 위해 file을 수시로 update해야 합니다.