1.
Fi
le Organization Basics
1.1 Database as Files
A database is stored as a collection of files.
Each file corresponds to one table (relation).
A file is a sequence of records.
A record is a sequence of fields (attributes).
1.2 Assumptions in File Organization
1. One file per table – keeps data organized and independent.
2. Fixed-length records – all records have the same size.
3. Record size < Disk block size – multiple records fit in one block.
2. Fi
xed-Length Record Organization
2.1 Record Addressing
Record i starts at byte:
Address = record_size × (i − 1)
2.2 Issues
Records may cross block boundaries.
Solution: Do not allow records to cross blocks.
2.3 Record Deletion
Techniques Method 1:
Shift Records
Move records (i+1 … N) to (i … N−1).
+ Inefficient for large files.
Method 2: Replace with Last Record
Move record N into deleted position.
⬛✓ Faster but breaks ordering.
Method 3: Free List (Best Method)
Deleted records are linked in a free list.
Advantages:
o Fast insertion
o No space wastage
o Stable record addresses
3. V
ariable-Length Records
3.1 Why Variable-Length Records Are Needed
Fields like VARCHAR, descriptions, comments vary in size.
Different records may have different numbers of fields.
Legacy systems may allow repeating fields.
3.2 Internal Record Structure
1. Fixed-length fields first
2. Variable-length fields stored using (Offset, Length)
3. Actual data stored at the end
4. Null Bitmap:
o 0 → Not NULL
o 1 → NULL
4. Sl
otted Page Structure
Used to store variable-length records efficiently inside a block.
Components
1. Block Header
2. Slot Directory (record locations)
3. Free Space
4. Records
Key Properties
Records can move inside the page.
Pointers reference slot entries, not physical addresses.
Prevents fragmentation.
5. S
toring Large Objects (LOBs)
Examples
BLOB (images, videos)
CLOB (text documents)
Storage Methods
1. Store outside DB in file system
2. Store as DB-managed files
3. Break into pieces (e.g., PostgreSǪL TOAST)
6. O
rganization of Records in Files
Comparison Overview of File Organizations
Organization Type
Storage Order Search SpeedInsert/Delete Range Ǫueries
Use Case
Heap File Unordered Slow Fast Poor OLTP systems
Sequential File Sorted by key Fast Slow Excellent Reporting systems
Hash File Hash-based Very Fast Fast Not SupportedKey-based lookup
(equality)
B+ Tree Sorted index Fast Balanced Excellent Mixed workloads
6.1 Heap File Organization
Records placed anywhere with free space.
Uses Free Space Map:
o Tracks available space per block.
o Two-level map improves efficiency.
6.2 Sequential File Organization
Records stored in sorted order by key.
Insertion:
Insert in correct position
If full → overflow block
Deletion:
Use pointer chains
Periodic reorganization required
6.3 Hash File Organization
Hash function determines block location.
Very fast equality search
Poor for range queries
6.4 B+ Tree Organization
Maintains sorted order
Efficient for range queries
Supports dynamic inserts/deletes
7. M
ultitable Clustering File Organization
Store records of multiple relations in one file.
Example: Department + Instructor
Pros
Efficient joins
Efficient access to related records
Cons
Poor performance for single-table queries
Variable-length records
8. P
artitioning
Definition
Partitioning divides a large table into smaller
partitions. Types
Horizontal (rows)
Vertical (columns)
Advantages
Reduced I/O
Better performance
Easier maintenance
Risks
Complex management
Slower full-table queries
Re-partitioning overhead
G. Data Dictionary (System Catalog)
Definition
A centralized repository storing metadata about the database.
Contents
Tables C columns
Data types C constraints
Indexes
User permissions
Statistics
Physical storage details
Storage
Stored as system tables (SYS_TABLES, SYS_COLUMNS)
Cached in memory for fast access
10. S
torage Access and Buffer Manager
Key Concepts
Block/Page: smallest disk I/O unit
Buffer: memory area holding disk blocks
Buffer Manager Responsibilities
Fetch blocks from disk
Manage buffer allocation
Decide block replacement
Workflow
1. Request tuple
2. Identify block
3. Check buffer
4. Load or return block
5. Evict if buffer is full
11. B
uffer Replacement Policies
Comparison of Buffer Replacement Policies
Policy Strategy Advantages Disadvantages Best Used When
Evict least recently Good general Overhead tracking General-purpose
LRU
used block performanc usage workloads
e
Evict most recently
Works for sequentialPoor for random
MRU Large table scans
used block scans access
Toss- One-time access
Discard after useMinimal overhead No reuse
Immediat blocks
e
Buffer Manager vs Disk Access
Aspect Disk Access Buffer Manager
Speed Very Slow Fast (RAM)
Cost High I/O cost Low
Purpose Permanent Temporary processing
storage
Common Policies
LRU: Least Recently Used
MRU: Most Recently Used
Toss-Immediate: Discard after use
Benefits of Efficient Buffer Management
Minimizes disk I/O
Improves query performance
Supports concurrency
12. C
olumn-Oriented Storage
Row-Oriented vs Column-Oriented Storage
Feature Row-Oriented Column-Oriented
Storage LayoutEntire row together Each column
separately
Best For Transactions (OLTP) Analytics (OLAP)
I/O Pattern Reads full rows Reads selected
columns
Compression Limited High
Updates Efficient Costly
Column-Oriented Storage
Concept
Store each attribute separately instead of row-wise.
Concept
Store each attribute separately instead of row-wise.
Advantages
Reduced I/O
Better compression
Faster analytics
Disadvantages
Costly updates
Tuple reconstruction overhead
Use Cases
Data warehouses
Decision support systems
File Formats
ORC
Parquet
13. M
ain-Memory Databases
Data stored directly in RAM
No buffer manager needed
Column-oriented storage preferred
Extremely fast but costly
Explain the role of the Buffer Manager in a DBMS. Describe its workflow and explain why
buffer replacement policies are necessary.
The Buffer Manager is a core DBMS component responsible for managing the
transfer of data blocks between disk storage and main memory (RAM). Since disk
I/O is the most expensive operation in a DBMS, the buffer manager aims to minimize
disk access and improve system performance.
Workflow of the Buffer Manager
1. A query requests a tuple.
2. The DBMS identifies the disk block containing that tuple.
3. The buffer manager checks whether the block is already in memory.
o If present → returns a pointer immediately.
o If not present → loads the block from disk into a buffer.
4. If the buffer is full, a replacement policy is used to select a block for eviction.
5. Modified (dirty) blocks are written back to disk before eviction.
Need for Buffer Replacement Policies
Buffer replacement policies determine which block should be removed when memory is full.
They are essential to:
Reduce disk I/O operations
Improve query execution time
Optimize memory utilization
Common policies include LRU, MRU, and Toss-Immediate, each suitable for different access
patterns.
Compare Heap File Organization, Sequential File Organization, and Hash File
Organization. Include advantages, disadvantages, and suitable use cases.
Feature Heap File Sequential File Hash File
Storage Order Unordered Sorted by key Hash-based
Search Performance Slow Fast Very fast (equality)
Insert/Delete Fast Slow Fast
Range Ǫueries Poor Excellent Not supported
Reorganization Not needed Required Not required
periodically
Use Case OLTP Reporting systems
Key-based lookup
systems
Heap files are best when insertions are frequent and ordering is not
important. Sequential files are ideal for range queries and reporting but
costly to maintain. Hash files provide the fastest equality searches but
do not support range queries.
Explain how variable-length records are stored in a DBMS. Describe the slotted page
structure and explain why it is preferred over fixed-location storage.
Model Answer
Variable-length records are used when attributes such as names, descriptions, or comments
vary in size. These records cannot be stored using fixed offsets.
Internal Storage of Variable-Length Records
Fixed-length fields are stored first.
Variable-length fields are stored using (offset, length) pairs.
Actual variable data is stored at the end of the record.
A null bitmap indicates which attributes are NULL.
Slotted Page Structure
A slotted page divides a block into:
1. Block header
2. Slot directory (record pointers)
3. Free space
4. Actual records
Why Slotted Pages Are Preferred
Records can move within the page without changing external references.
Eliminates internal fragmentation.
Supports efficient insertion and deletion.
Pointers reference slots, not physical addresses.
This makes slotted pages highly suitable for variable-length records.