DB Interal Introduction

Data Storage and IO Models

Buffer Manger and File Organization

External Sorting

File Organization

What we will cover

1. File Organization

2. Page Organization

3. Column Stores

• The disk (low low level) is organized into files

• Files are made up of pages

• Pages contain records

File operations are on records

• insert/delete/modify record
• Read a particular record (record id)
• Scan all records

Ways to Organize:

Unordered (Heap) Files

• Simplest file structure that contains records in no particular order, as the file grows and shrinks, the disk pages are allocated and de-allocated.

• Heap File as a list is a doubly linked list

Page Organization: Page Formats

• Page is a collection of records remember

• Slotted page format is when a page is collection of slots and each slot contains a record

• We need support for searh, insert, delete records on a page

There are two possible ways of representing the records:

• Fixed-Length Records
• Variable-Length Records

Fixed-Length Records

Record id = <page id, slot#>

Packed vs. Unpacked Organization

Packed Organization are always stored in the first N slots while unpacked use a bitmap to locate records in a page.

Variable Length Records

Coloumn Stores

ADDING