Tables are stored as logical files consisting of pages. Each page contains a collection of records.
Storage Structure
Table
One database have many tables.
File
There are two main types of files: Heap Files and Sorted Files. For each relation, the database chooses which file type to use based on the I/O cost (read or write page once = 1 I/O) of the relation’s access pattern.
Heap File
Linked List Implementation:
Page Directory Implementation:
Each header page contains a pointer (byte offset) to the next header page, and its entries contain both a pointer to a data page and the amount of free space left within that data page.
The main advantage of Page Directories over Linked Lists is that inserting records is often faster.
Example
Consider the following example where a heap file is implemented as both a Linked List and a Page Directory. Each page is 30 bytes and a 20 byte record is being inserted into the file: Linked List:
Page Directory:
Sorted File
A sorted file is a file type where pages are ordered and records within each page are sorted by key (s).
Inserted record could potentially cause all later records to be pushed back by one.
Page
See Page
Record
See Record