[CS186] Introduction to Database Systems - Week 2

⛅ Disk, Buffer, Files ⛅

1. Memory and Disk

 

https://cs186berkeley.net/resources/static/notes/n03-DisksFiles.pdf

 

Disk Space Management

• DBMS의 가장 밑에 있는 계층이며, 디스크의 공간을 관리한다

Disk Space Management는 파일 시스템 위에 위치하고 있다

 

2. Files, Pages, Records

• 관계형 데이터베이스의 가장 기본 데이터의 단위는 record(row)이다
• 릴레이션(테이블)들은 이런 records들로 구성되며, 메모리에 수정, 삭제, 검색 또는 생성이 가능하다

 

• 디스크의 가장 기본 데이터의 단위는 page이며, 디스크와 메모리 간의 최소 전송 단위이다
• 관계형 데이터베이스를 디스크와 호환 가능한 형식으로 표현하기 위해, 각 릴레이션은 별도의 파일에 저장되며, records는 파일안의 pages로 구성된다
• 데이터베이스는 릴레이션의 스키마와 접근 패턴에 따라 아래 4가지 내용을 결정한다
  • 1. 어떤 형식의 파일을 사용할 건지
  • 2. 어떻게 pages를 파일 내에 구성할 건지
  • 3. 어떻게 records를 각 page에 구성할 건지
  • 4. 어떻게 각 record가 구성될 건지

왼쪽의 릴레이션은 오른쪽의 파일과 같은 형식으로 표현된다

 

3. Choosing File Types

• 2가지의 주요 파일 타입이 있다: Heap Files과 Sorted Files
• 데이터베이스는 각각의 테이블에 어떤 파일 타입을 사용할 건지 릴레이션의 접근 패턴의 I/O 비용에 근거하여 선택한다
• 1 I/O = 1 page read from disk || 1 page write to disk

 

4. Heap File

• heap file은 pages의 정해진 순서가 없는 또는 records on pages의 특별한 순서가 없는 파일 타입이다 
• sorted file과 비교했을 때 삽입 속도가 매우 빠르다
• 단, 순서가 없기 때문에 검색에는 매번 full scan이 필요하다. 즉, 검색의 경우 N I/Os의 linear 비용이 든다

4.1 Linked List Implementation

• 링크드 리스트 구현에서는 각각의 data page는 1. records와 2. free space tracker, 3. 다음과 이전 page에 대한 pointers(byte offsets)를 포함하고 있다
• 하나의 header page는 파일의 시작점 역할을 하며, data pages를 full pages와 free pages로 부터 분리한다

 

4.2 Page Directory Implementation

• page directory 구현 방법은 링크드 리스트를 header pages에만 사용한다는 점에서 linked list implementation과 다르다
• 각각의 header page는 파일의 data page에 얼마 만큼의 공간이 남았는지에 대한 정보를 가지고 있다. 따라서 records를 삽입할 때 linked lists보다 page directories가 더 빠르다

 

5. Sorted File

• pages가 정렬되어 있고 각 페이지의 records는 키로 정렬되어 있는 파일 타입이다
• 검색에는 logN I/Os 시간이 걸린다(binary search를 사용할 수 있기 때문). 여기서 N은 페이지의 개수이다
• 삽입은 평균적으로 logN + N I/Os가 걸린다

 

7. Record Types

• record 타입의 경우 릴레이션의 스키마에 의해 결정되며, 2가지의 종류가 있다
• 1. Fixed Length Records(FLR) 
  • 고정된 길이의 바이트를 가지고 있다 (예: integers, boolean, date, etc)
  • FLR의 동일한 스키마는 동일한 수의 바이트를 가지고 있다
• 2. Variable Length Records(VLR)
  • 고정된 길이 필드와 가변 길이 필드 (예: varchar) 모두 포함하고 있기 때문에 동일한 스키마의 VLR이라도 다른 바이트 수를 가질 수 있다. 
  • VLR은 가변 길이 필드의 끝을 가리키는 포인터를 포함하는 record header를 사용하며, 고정 길이 필드는 가변 길이 필드가 저장되기 전에 저장된다

 

8. Page Formats

8.2 Page with Variable Length Records

• 각 페이지는 page footer를 사용해 slot directory를 관리한다
• slot directory는 slot count, free space pointer, 그리고 entries를 추적한다
• slot directory의 각 entry는 [record pointer, record length] 페어로 구성되어 있다

 

 

 

 

CS186 사이트

https://cs186berkeley.net/