Storage & File Structures: Files, Blocks, Indexing

TAKEAWAYS:

• Physical vs. logical storage: Databases use files and blocks to bridge the gap between how data is stored on disk and how it is accessed logically.
• File organizations: Sequential, indexed (B-trees, B+ trees), and hashed files each optimize for different query patterns (range queries, exact-match lookups, or fast inserts).
• Overflow handling: Techniques like linked overflow and dynamic hashing ensure files remain efficient even as data grows.
• Performance trade-offs: Indexes speed up searches but slow down inserts/deletes; file structures must balance these costs.
• Real-world impact: From Khalti’s transaction logs to Daraz’s product catalogs, file structures determine how fast your app responds.

---

1. Physical Storage Basics: Files and Blocks

Databases do not store data in memory forever—they must persist it on disk. To manage this, they use files (contiguous disk regions) and blocks (fixed-size chunks, typically 4–16 KB). Here’s how they work:

1.1 Files in Databases

A file is a named collection of records stored contiguously on disk. Files can be:

• Data files: Store actual records (e.g., customers.dat, orders.dat).
• Index files: Store pointers or keys for fast lookup (e.g., customer_index.btree).
• Log files: Record transactions for recovery (e.g., transaction_log).

Why blocks? Disks read/write in fixed-size chunks (blocks). If a record spans multiple blocks, the database must:

1. Split the record into fragments.
2. Link fragments using pointers (e.g., in overflow areas).

1.2 Block Organization

A block holds multiple records, but not all records fit perfectly. Databases use:

• Fixed-length records: All records in a block are the same size (e.g., SSN + Name + Age).
• Variable-length records: Records vary in size (e.g., ProductID + Description + Price). The database uses slots to track where each record starts.

---

2. File Organizations: How Records Are Arranged

The way records are stored in a file determines how fast queries run. Three primary organizations:

2.1 Sequential (Heap) Files

• How it works: Records are stored in the order they arrive (no sorting). Think of a stack of papers—you can only access the top one quickly.
• Access methods:
  • Sequential scan: Read every record until you find the target (slow for large files).
  • Indexed access: Use a separate index (e.g., B-tree) to find the block containing the record.
• Use case: Batch processing (e.g., generating monthly reports for NTC’s billing system).
• Disadvantage: Terrible for point queries (e.g., "Find customer ID 12345").

2.2 Indexed Files (Ordered Files)

• How it works: Records are sorted by a key (e.g., customer_id). The database maintains an index (e.g., B-tree) to point to blocks.
• Types:
  • Primary index: Sorts records on the primary key (e.g., account_number).
  • Secondary index: Sorts records on a non-key attribute (e.g., customer_name).
• Advantage: Fast lookups (O(log n) with B-trees).
• Disadvantage: Inserts/deletes require reordering (expensive).
• Real-world example: Khalti’s transaction logs use indexed files to quickly verify if a transaction exists by transaction_id.

2.3 Hashed Files

• How it works: Records are stored based on a hash function (e.g., hash(customer_id) % 1000). The hash maps to a bucket (block).
• Advantage: O(1) average-time lookups (instant for exact matches).
• Disadvantage:
  • Collisions: Multiple records hash to the same bucket → overflow.
  • No range queries: Cannot efficiently find "customers with IDs between 1000 and 2000."
• Overflow handling:
  • Linked overflow: Overflow records are chained in a linked list.
  • Dynamic hashing: Resize the hash table as data grows (e.g., extendible hashing).
• Real-world example: Daraz’s product catalog uses hashed files to quickly locate products by product_id (e.g., "Find the laptop with ID LP-2023-001").

---

3. Overflow Handling: Keeping Files Efficient

When a block fills up, new records must go elsewhere. Two common strategies:

3.1 Linked Overflow

• How it works: If a block is full, the new record is stored in an overflow block, and the original block’s last record points to it.
• Pros: Simple to implement.
• Cons: Sequential scans become slow (must follow pointers).
• Example: In a bank’s loan records, if the primary block for loan_id fills up, new loans are linked in overflow blocks.

3.2 Dynamic Hashing (Extendible Hashing)

• How it works: The hash table grows by doubling its size when load factor exceeds a threshold (e.g., 70%).
• Example: NEPSE’s stock transaction records use dynamic hashing to handle sudden spikes in trading volume.

---

**4. Comparison Table: File Organizations

---

5. Real-World Applications

Example 1: Khalti’s Transaction Processing

• Problem: Khalti needs to verify transactions in milliseconds.
• Solution:
  • Indexed files store transactions sorted by transaction_id.
  • B-tree indexes allow O(log n) lookups for fraud checks.
  • Sequential files log all transactions for auditing.

Example 2: Daraz’s Product Catalog

• Problem: Millions of products must be retrieved instantly.
• Solution:
  • Hashed files map product_id to blocks for O(1) access.
  • Linked overflow handles collisions (e.g., if two products hash to the same bucket).

Example 3: NTC’s Customer Billing

• Problem: Monthly bills must be generated efficiently.
• Solution:
  • Sequential files store customer records in arrival order.
  • Secondary indexes on customer_name speed up name-based searches.

---

6. Worked Example: File Organization for a Bank’s Loan System

Scenario: A bank stores loan records with fields: (loan_id, customer_id, amount, interest_rate, status).

Requirements:

1. Fast lookup by loan_id.
2. Efficient range queries on amount (e.g., "Loans between ₹500K and ₹1M").
3. Handle 10,000 daily new loans.

Solution:

• Primary storage: Indexed file sorted by loan_id (B-tree index).
• Secondary index: Indexed file sorted by amount for range queries.
• Overflow: Linked overflow for blocks that fill up.

Trace:

1. Insert a new loan:
   • Hash loan_id to find the block.
   • If full, use linked overflow.
   • Update the amount index.
2. Query: "Find loans > ₹500K":
   • Use the amount index to locate the range of blocks.

---

7. Exam Tip

What examiners test:

1. Definitions: Know the difference between sequential, indexed, and hashed files.
2. Trade-offs: Can you explain why a bank uses indexed files but Daraz uses hashed files?
3. Overflow handling: Describe linked overflow or dynamic hashing in detail.
4. SQL to file mapping: Given a query like SELECT * FROM accounts WHERE balance > 100000, which file organization would you use and why?
5. Diagrams: Always draw block diagrams or B-trees when asked about indexing.

Common pitfalls:

• Confusing primary vs. secondary indexes.
• Forgetting that hashed files cannot do range queries.
• Not explaining overflow handling in your answer.

Sample exam question: "Explain how a bank’s loan records would be organized in a file system to support fast lookups by loan_id and range queries on amount. Include a diagram of the file structure and discuss overflow handling."

Model answer structure:

1. Choose file organization: Indexed file for loan_id (primary index), indexed file for amount (secondary index).
2. Draw diagrams: B-tree for loan_id, another for amount.
3. Overflow: Linked overflow for full blocks.
4. Query example: Show how a range query on amount works using the secondary index.

---