[Database] File Organization
File Organization
DB는 file의 구조를 이용해서 데이터를 저장합니다. 파일은 정해진 규격, 규칙이 있기 때문에 사용하기 유용합니다.
Fixed-Length Records
이때 record는 tuple이라고 볼 수 있는데, tuple은 저장될 때 검색의 기준이 되는 key와 나머지 값들인 value 혹은 record로 저장됩니다.
만약 데이터의 type이 변하지 않고 고정되어있는 경우, 고정된 길이의 record를 다룰 때는 간단하게 나열하는 방법을 사용합니다. 예를 들어 record의 크기가 n이고 record i까지를 저장하기 위해서는 n * (i - 1) byte크기의 파일이 있으면 됩니다. 이를 그림으로 나타내면 다음과 같습니다:
만약 이때 record 3을 제거하는 경우, 해당 공간을 다루는 경우가 3가지가 존재합니다.
1. move records i+1, ..., n to i, ..., n-1
빈 공간에 그 이전의 record를 넣어주고, 이를 마지막 record까지 반복합니다. 하지만 이는 선형적인 시간복잡도를 갖기 때문에 비용이 큽니다.
2. move record n to i
빈 공간에 가장 마지막의 record를 넣어줍니다. 이렇게 하면 하나의 record만을 움직이기 때문에 이전 방법에 비해 시간이 덜 소모됩니다. 하지만 원래 record가 정렬상태였다면, 정렬이 흐트러질 수 있다는 단점이 존재합니다.
3. do not move records, but link all free records on a free list
record를 움직이지 않고 free list를 관리합니다. 빈 공간들을 linked list를 이용해 관리하는 것입니다. 이를 통해 새로운 record가 삽입되는 경우 빠르게 위치를 찾고 대응할 수 있습니다.
Variable-Length Records
하지만 고정된 길이가 아닌 길이가 변경될 수 있는 record는 어떻게 저장할 수 있을까요? 길이가 변하는 record는 file에 다양한 type이 존재하는 경우, 혹은 varchar과 같은 attr.가 variable type을 허용하는 경우 발생할 수 있습니다. 이는 pointer를 이용하며, pointer는 실제 데이터가 저장되어있는 위치를 뜻하는 offset과, 데이터의 길이를 뜻하는 length의 pair로 이루어집니다. 이를 그림으로 나타내면 다음과 같습니다.
null값의 경우는 null bitmap을 이용해서 표현할 수 있습니다. 또한 attr.의 개수가 늘어나면 header의 길이가 늘어날 수도 있습니다.
Variable-Length Records: Slotted Page Structure
가변 길이의 record를 다루는 대표적인 방법은 slotted page입니다. 이는 record는 하나의 page(일반적으로 4KB)에 저장되며, page는 크게 block header와 free space, records들로 구성됩니다.
slotted page의 header에는 record의 전체 수, free space가 끝나는 지점과 각 record들의 위치와 크기 정보가 들어있습니다. header에 존재하는 pointer들을 이용해 실제 record에 접근할 수 있습니다.
Slotted page는 다음과 같은 구조입니다:
record들은 key값에 의해 정렬되며, key값을 포함한 attr.들은 page의 오른쪽인 record에 저장됩니다. 이 데이터를 가르키는 record offset은 header의 다음에 이어지며, metadata와 record offset array를 포함한 부분을 slot header라고 부릅니다. 만약 새로운 데이터가 추가된다면 record offset array는 오른쪽으로, record content area는 왼쪽으로 확장되며 free space를 먹어 들어갑니다.
해당 record들은 key값에 의해 정렬되며, 실제 데이터의 정렬은 offset을 이용합니다. 예를 들어:
다음과 같이 30과 50사이에 40을 key 값으로 갖는 record가 들어온다면, record content area에는 순서대로 저장되지만, record offset array에서의 offset은 그 사이에 들어가 정렬 상태를 유지합니다.
Storing Large Objects
blob/clob과 같이 큰 데이터를 저장하는 경우 세 가지 방법이 존재합니다:
- Store as files in file systems; file system에 데이터를 저장합니다. 이는 DB의 공간을 많이 잡아먹지 않는다는 장점이 있지만, inconsistency등 다양한 문제들이 있을 수 있습니다.
- Store as files managed by database; DB안에서 관리합니다. 이는 DB의 공간을 많이 잡아먹는다는 단점이 있습니다.
- Break into pieces and store in multiple tuples in seperate relation
Organization of Records in Files
파일에서 record들을 관리하는 방법에는 다음의 세 가지가 존재합니다(추가로 존재하긴 하지만 추후 다룸):
- Heap - record can be placed anywhere in the file where there is space. 공간이 되는 곳에 그냥 저장합니다.
- Sequential - store records in sequential order, based on the value of the search key of each record. search key를 기준으로 순서대로 저장합니다.
- multitable clustering file organization - records of several different relations can be stored in the same file. 서로 다른 relation에 존재하는 record들을 하나의 파일에 저장합니다.
- B+ tree (in Chapter 14)
- Hashing (in Chapter 14)
Heap File Organization
그냥 비는 공간에 추가하며, 해당 records들은 pointer를 통해 관리합니다.
이 경우 빈 공간을 찾는 것이 매우 중요합니다. 그래서 free-space map을 관리합니다. 이는 각 data block의 빈 공간을 나타내는 자료구조로, 다음의 예시가 있습니다:
위 예시의 경우 3-bit을 이용해 각 data block의 빈 공간을 나타냅니다. 3-bit는 0~7까지의 수 밖에 표현할 수 없기에 data block의 빈 공간을 ÷8하여 빈 공간의 비율을 나타냅니다. 예를 들어 free-space map에서의 값이 2라면, 2/8= 1/4=25%의 공간이 남았다는 뜻입니다. 여기에서 한 번 더 나아가 4개씩 묶어서 가장 큰 여유공간을 갖는 fraction을 모아 저장할 수 있습니다(위 예시에서는 4726).
만약 새로운 record를 넣기 위해 필요한 공간이 6이라면, 두 번째 뽑힌 map에서 6보다 큰 수를 찾습니다. 이때 가장 먼저 찾는 수를 first fit이라고 하며, 정확히 6에 해당하는 수를 best fit이라고 부릅니다. first bit이든 best fit이든 선택한 후 해당 묶음으로 다시 내려가 또 fit한 entry를 찾은 후 빈 공간에 저장합니다. *성능적으로는 빈 공간이 좀 생기더라도 first fit에 저장하는 것이 효율적입니다.
Sequential File Organization
search key를 기준으로 정렬하여 file에 records들을 저장합니다. 또한 이들을 pointer를 통해 연결합니다.
이때 record를 삭제하는 경우 pointer chain을 수정하여 sequential한 record들을 유지할 수 있으며, 추가하는 경우 pointer를 통해 삽입하는 효과를 내어 sequential한 record를 유지합니다.
이런 식의 insertion이 계속해서 반복된다면 pointer chain이 매우 복잡해지기 때문에 일정한 시간에 한 번씩 reorganization이 필요합니다.
Multitable Clustering File Organization
join연산과 같인 table간의 연산이 많은 경우 서로 다른 파일에 저장하면 join연산의 비용이 매우 커집니다. 그렇기 때문에 미리 file수준에서 하나의 file에 두 table을 동시에 저장합니다.
앞서 말했듯 이는 join연산이 많은 table간에서 사용하는 것이 좋으며, 일반적인 쿼리가 많이 쓰이는 테이블을 이런 식으로 저장하는 것은 성능 부분에서 좋지 않습니다.
Column-Oriented Storage
Columnar representation이라고도 불리는 저장 방식은 column, 즉 attr.을 기준으로 따로 저장하는 것입니다. 이는 table에서 특정 attr.값을 끼리의 연산이나 분석이 필요한 경우 많이 사용될 수 있습니다.
Data Dictionary
system catalog라고도 불리는 data dictionary는 metadata를 저장하는 용도로 사용됩니다. metadata로는 다음이 있습니다:
- Information about relations
- User and accounting information, including password
- Statistical and descriptive data
- Physical file organization information
- etc.
이를 ER diagram으로도 나타낼 수 있으며 다음의 예시가 존재합니다:
*GPT가 말하는 File과 Page의 차이, slotted page와 file organization의 차이
✅ 1. 핵심 용어 정리
🔹 Table (논리적 개념)
- 사용자나 SQL 관점에서 바라보는 릴레이션(관계).
- 사용자는 SELECT * FROM Student 같은 쿼리를 통해 table 단위로 데이터를 조회.
- 내부적으로는 여러 개의 record(row, tuple)로 구성됨.
🔹 Record (또는 Tuple)
- 테이블의 한 행(row), 즉 하나의 데이터 단위.
- slotted page structure는 이 record 단위로 데이터를 저장하고 관리함.
🔹 Page (물리적 저장 단위)
- 보통 고정 크기(예: 4KB)의 디스크 블록 단위.
- 여러 개의 record를 하나의 page 안에 저장.
- 페이지 안에서는 slotted page 구조를 통해 record들을 효율적으로 관리.
🔹 File
- 같은 테이블의 여러 페이지들을 모아 놓은 것.
- 즉, 하나의 테이블에 대한 모든 데이터를 담고 있는 물리적 단위.
- DBMS에서는 보통 한 테이블 = 한 파일 구조로 관리하며, 그 안에 여러 page가 있음.
✅ 2. 슬롯 페이지 구조(Slotted Page Structure)
- 페이지 내부에서 레코드들을 정리하는 구조.
- 각 레코드는 페이지 내의 가변 위치에 있고, 레코드 위치는 **슬롯 디렉터리(slot directory)**에 저장됨.
- 삽입/삭제/압축 등의 연산이 효율적으로 일어나도록 설계됨.
✅ 3. 질문에 대한 정리된 답변
❓ slotted page structure에서 관리하는 records들은 table 수준인가요?
➡️ 네, 맞습니다.
슬롯 페이지 구조는 DBMS 내부에서 테이블의 레코드(행)를 저장하고 관리하는 기본 구조입니다.
즉, "이 테이블의 레코드들을 어떻게 페이지에 배치할까?"를 관리하는 것이 slotted page structure입니다.
❓ DBMS는 file에 데이터를 저장한다고 하는데, 그러면 page가 file인가요?
➡️ 아니요, 정확히는 page는 file 안에 포함된 단위입니다.
- 하나의 table → 하나의 file
- 그 file 안에 여러 개의 page
- 각 page 안에 여러 개의 record
- 각 record는 slotted page structure로 저장됨
구조 요약 (상위 → 하위):
✅ 시각화 (간단한 도식)
✅ 보너스: 관련 개념
| Record | 가장 작음 | Slotted Page | 데이터 단위 |
| Page | 수 KB | Buffer Manager | 디스크 I/O 최소화 |
| File | 수 MB 이상 | File Manager | 전체 테이블 저장 |
| Table | 논리 단위 | Catalog/Query Processor | SQL 대상 |
✅ 결론
- slotted page structure는 page 내부에서 테이블의 record들을 효율적으로 관리하는 방식입니다.
- Page는 file 안에 여러 개 존재하며, 하나의 file은 하나의 table에 대응합니다.
- 따라서, 슬롯 페이지 구조는 테이블 수준의 record 저장을 위한 핵심 구조입니다.