Chapter 6

File Structure and Hashing

5 hours8 marks18 past questionsBack to chapters Open filtered PYQs Previous: Ch 5 Next: Ch 7

Chapter Notes

Block-based notes with markdown, diagrams, code, and math.

Chapter 6 — File Structure and Hashing

6.1 Storage Hierarchy

RAID Levels

RAID Level	Technique	Read	Write	Fault Tolerance	Use
0	Striping only	Fast	Fast	None	Performance only
1	Mirroring	Fast	Slower	1 disk failure	Critical data
5	Striping + distributed parity	Fast	Moderate	1 disk failure	General purpose
6	Striping + dual parity	Fast	Slower	2 disk failures	High availability
10	RAID 1 + RAID 0	Very fast	Fast	1 disk per mirror	Databases

6.2 Record Organization

Fixed-Length Records

Every record occupies the same number of bytes. Access: record i starts at byte i × record_size.

Pro: simple, fast random access.
Con: wastes space if fields are often short/null.

Variable-Length Records

Fields can vary; null values take no space. Requires a slotted page structure.

6.3 Ordered Indices

An index maps search key values to records, allowing faster lookups than a full scan.

Index Type	Description
Dense index	One index entry per record in the data file
Sparse index	One entry per data block (only works on sorted data)
Primary (clustering) index	On the sort key of a sorted file
Secondary (non-clustering) index	On any non-sort key; always dense
Multi-level index	Sparse index on top of a dense index to reduce search space

Trade-off: dense index → faster search; sparse index → less space but only on sorted data.

6.4 B+ Tree Index

B+ tree is the standard index structure in all major RDBMS (PostgreSQL, MySQL InnoDB, Oracle).

B+ Tree Properties (order n)

All leaves are at the same depth (balanced).
Internal nodes: ⌈n/2⌉ to n pointers.
Leaf nodes: ⌈(n-1)/2⌉ to n-1 keys + pointers to records.
Leaf nodes are linked in a doubly-linked list → efficient range queries.
Root has at least 2 children (unless it is also a leaf).

B-tree vs B+ Tree

	B-tree	B+ tree
Data pointers	In internal + leaf nodes	Only in leaf nodes
Range queries	Slower (in-order traversal)	Fast (linked leaf list)
Space	Less redundancy	Slightly more (key repeated in leaf)
Used in practice	Rarely	Almost universally

6.5 Hashing

Static Hashing

A hash function h(K) maps a key K to a bucket number 0…B-1.
Each bucket holds one or more pages.
Overflow buckets are chained when a bucket fills.
Problem: if the table grows, performance degrades. Reorganization is expensive.

Extendable (Dynamic) Hashing

Uses a directory (array of pointers to buckets).
Global depth d: directory size = 2^d.
Local depth l per bucket: number of bits used to hash to that bucket.
On overflow: split the bucket; if l = d, double the directory.

Extendable Hashing — Insert example

Initial state: global depth = 1, 2 buckets
  Directory: [0→BucketA, 1→BucketB]
  BucketA (local depth 1): keys with h(k) ending in 0
  BucketB (local depth 1): keys with h(k) ending in 1

Insert key 15 (h(15)=1111):
  → goes to BucketB
  If BucketB overflows (local depth < global depth):
    → Split BucketB into B0 (ending 01) and B1 (ending 11)
    → Local depth of new buckets = 2
    → Update directory entries 01 → B0, 11 → B1

  If BucketB overflows AND local depth = global depth:
    → Double the directory: global depth becomes 2
    → Directory now has 4 entries: 00, 01, 10, 11
    → Then split as above

Search: compute h(k), take last d bits, follow directory pointer → O(1)

Hashing vs B+ Tree

	B+ Tree	Hash Index
Exact match	O(log n)	O(1) average
Range query	O(log n + result)	Not supported
Ordered output	Yes	No
Best for	Most queries	Point lookups only

Exam Quick-Reference

RAID 5 = striping + parity (1 disk failure tolerated); RAID 6 = 2 disk failures.
Dense index: one entry per record; Sparse: one entry per block (sorted file only).
B+ tree leaves are linked → range queries scan leaves sequentially.
Extendable hashing: global depth controls directory size; local depth controls bucket split.
Static hashing → overflow chaining; extendable → split + directory doubling.

Full Syllabus Outline

Every topic from the syllabus data is preserved here.

6.1
Disks and storage
DE
Physical storage media: magnetic disk, SSD, optical, tape. Storage hierarchy. RAID levels (0–6): striping, mirroring, parity. Selecting an appropriate RAID level.
6.2
Records organizations
DEI
File organization concepts. Fixed-length records. Variable-length records: slotted page structure. Sequential record organization. Multi-cluster (heap) record organization. Database buffer management.
6.3
Ordered indices
DEI
Primary (clustering) index vs secondary (non-clustering) index. Dense index vs sparse index. Index sequential file. Searching, inserting, and deleting in ordered indices. Multi-level sparse indices.
6.4
B+ tree index
DEI
B+ tree node structure (internal nodes and leaf nodes). Order-n definition. Search, insert, and delete operations with examples. Properties and advantages. Comparison with B-tree.
6.5
Hashing concepts — Static and dynamic hashing
DEI
Hash function basics. Hash index structure. Static hashing: bucket array, overflow chaining, search and insert. Limitations of static hashing. Extendable (dynamic) hashing: global depth, local depth, directory doubling. Bitmap indices.

Solved PYQs

A few past questions with short answers.

Chapter 68 marksasked 1x2081 Chaitra R

Explain the different levels of RAID briefly. What is indexing in database? Differentiate between dense index and sparse index.

Solution

RAID and Indexing:

RAID (Redundant Array of Independent Disks):

Level	Technique	Fault Tolerance	Performance	Storage Overhead
RAID 0	Striping only	None	Excellent R/W	None
RAID 1	Mirroring	1 disk failure	Excellent R; good W	2×
RAID 5	Striping + distributed parity	1 disk failure	Good R; moderate W	1 disk
RAID 6	Striping + 2 parity disks	2 disk failures	Good R; slower W	2 disks
RAID 10	RAID 1+0 (mirror then stripe)	1 per mirror pair	Excellent R/W	2×

RAID 10 is preferred for databases because it combines the write performance of RAID 0 striping with the fault tolerance of RAID 1 mirroring.

Index Types:

Dense Index: One index entry per data record (tuple). Can find any record by looking up its key in the index directly. More storage but faster search.

Sparse Index: One index entry per data block (only works on sorted/clustered data). Fewer entries but requires scanning within the block after finding it via the index. Less storage.

Primary Index: Built on the attribute(s) that determine the physical ordering of records in the file (the search key matches the file's sort order).

Secondary Index: Built on an attribute that is not the file's sort order. Must be dense (since records are not sorted by this attribute).

Chapter 68 marksasked 1x2081 Ashwin B

What is the purpose of using RAID? How can a variable length record be implemented? Compare dense and sparse ordered indices.

Solution

Storage Hierarchy:

Database storage is organized in a hierarchy from fastest/smallest/most expensive to slowest/largest/cheapest:

Level	Technology	Access Time	Capacity	Volatility
L1/L2/L3 Cache	SRAM	~1 ns	KB–MB	Volatile
Main Memory	DRAM	~100 ns	GB	Volatile
SSD	Flash NAND	~100 μs	TB	Non-volatile
HDD	Magnetic disk	~10 ms	TB	Non-volatile
Tape / Archive	Magnetic tape	Seconds	PB	Non-volatile

DBMS Buffer Pool: The DBMS manages a buffer pool (pool of fixed-size pages in main memory). Pages are brought from disk into the buffer pool on demand and evicted when the pool is full. The block/page (typically 4KB–16KB) is the unit of I/O transfer.

Buffer Replacement Policies:

LRU (Least Recently Used): Evict the page not accessed for the longest time. Works well for random access.
Clock Algorithm: Efficient approximation of LRU using a reference bit per page.
MRU (Most Recently Used): Evict the most recently used page — counterintuitively better for sequential scans (nested-loop joins).
Pinned Pages: Pages currently being used by a transaction cannot be evicted.

Chapter 68 marksasked 1x2082 Kartik B

Explain fixed-length and variable-length records in File Organization. Explain how a hash index works. Distinguish between static and dynamic hashing.

Solution

Fixed-Length vs Variable-Length Records:

Fixed-Length Records: All records in the file have the same size. The i-th record starts at byte offset i × record_size from the start of the file.

Advantages: random access by record number is O(1); simple deletion (mark as free or use a free list).
Disadvantages: wastes space for variable-length data (e.g., name padded to max length).

Variable-Length Records: Records have different sizes due to variable-length attributes (VARCHAR) or optional fields.

Implemented using a slotted page structure: each page has a header containing an array of (offset, length) pairs — one per record on the page. Records are packed from the end of the page toward the header.
Advantages: no wasted space for short values.
Disadvantages: more complex access; records can only be accessed by page+slot, not by absolute byte offset.

Hashing vs B+ Tree Index (Index Structure Comparison):

Property	Hash Index	B+ Tree Index
Equality search	O(1) average	O(log n)
Range search	Not supported	O(log n + result)
Ordered output	Not supported	Naturally ordered
Space overhead	Moderate	Moderate
Insertion/deletion	O(1) average	O(log n) with splits
Best use case	Exact-match queries	Mixed workloads, ORDER BY

More PYQs

Additional practice from this chapter.

Why is the B+ tree the preferred index structure for file organization in most modern relational database systems?
3 marksasked 1xModel Q
Briefly describe the mechanism that allows Extendible/Dynamic Hashing to grow without reorganizing the entire file.
4 marksasked 1xModel Q
Explain the different levels of RAID briefly. What is indexing in database? Differentiate between dense index and sparse index.
8 marksasked 1x2081 Chaitra R
What is the purpose of using RAID? How can a variable length record be implemented? Compare dense and sparse ordered indices.
8 marksasked 1x2081 Ashwin B
Explain fixed-length and variable-length records in File Organization. Explain how a hash index works. Distinguish between static and dynamic hashing.
8 marksasked 1x2082 Kartik B

File Structure and Hashing

Chapter 6 — File Structure and Hashing

6.1 Storage Hierarchy

RAID Levels

6.2 Record Organization

Fixed-Length Records

Variable-Length Records

6.3 Ordered Indices

6.4 B+ Tree Index

B+ Tree Properties (order n)

B-tree vs B+ Tree

6.5 Hashing

Static Hashing

Extendable (Dynamic) Hashing

Hashing vs B+ Tree

Exam Quick-Reference

Disks and storage

Records organizations

Ordered indices

B+ tree index

Hashing concepts — Static and dynamic hashing