Module 4

Physical Storage Media, File Organization,

RAID & Indexing
Comprehensive Notes for Exam Preparation
Module 4: Physical Storage, RAID & Indexing Page 2

Contents
1 Discuss physical storage media in database and different types of storage
media. 3

2 Compare volatile and non-volatile storage media with examples. 4

3 Discuss the difference between Magnetic Disk and Optical Disk. 5

4 Explain the hierarchy of storage systems in terms of speed, cost, and capac-
ity. 6

5 Explain the read/write mechanism of a magnetic disk with steps in DBMS. 7

6 Discuss the role and performance of magnetic disk in DBMS. 8

7 Explain how data is organized on a magnetic disk with a diagram. 10

8 Explain RAID 0. What are its benefits and drawbacks? 12

9 Compare RAID 0 and RAID 1 in terms of performance and redundancy. 14

10 How does RAID improve data reliability and performance? 15

11 Advantages of heap file organization over sequential file organization. 17

12 Differences between fixed-length and variable-length records. 19

13 Discuss different types of record organizations in a database. 21

14 Explain cluster file organization and its types. 22

15 Elaborate the concept of RAID. What are its advantages? 23

16 Explain different RAID levels with diagrams. 24

17 Compare RAID 0, RAID 1, and RAID 5 in terms of redundancy and per-

formance. 25

18 Explain the basic concept of indexing in DBMS. Discuss two basic types of
indices. 27

19 Explain the structure of a B-Tree with an example. 28

20 Explain the ordered indices in DBMS with example. 30

DBMS Notes
Module 4: Physical Storage, RAID & Indexing Page 3

1 Discuss physical storage media in database and differ-

ent types of storage media.
What is Physical Storage Media?
Every database stores its data on some physical device — RAM, hard disk, tape, etc. The
choice of device affects speed, cost, and reliability. Understanding storage media helps us
design faster databases.
The Storage Hierarchy:
Think of it as a pyramid — the top is fast but tiny and expensive; the bottom is slow but
huge and cheap.

Registers

Cache (SRAM)

Main Memory (RAM)

Capacity Speed & Cost
Flash Memory / SSD

Magnetic Disk (HDD)

Magnetic Tape

Detailed Comparison of Storage Types:

Type Speed Cost/GB Capacity Volatile? DBMS Use

Registers Fastest Highest Bytes Yes CPU operations
Cache Very fast Very high KB–MB Yes Frequent data
RAM Fast High GB Yes Buffer pool
SSD/Flash Moderate Medium GB–TB No Indexes, logs
Magnetic Disk Moderate Low TB No Main DB storage
Optical Disk Slow Low GB No Archival
Magnetic Tape Slowest Lowest PB No Backup

Key insight for DBMS: Most database data lives on magnetic disks (HDD) or SSDs
because they offer a good balance of cost, capacity, and persistence. RAM is used as a buffer-
/cache to speed up frequently accessed data.

DBMS Notes
Module 4: Physical Storage, RAID & Indexing Page 4

2 Compare volatile and non-volatile storage media with

examples.
Simple Analogy:
• Volatile = Writing on a whiteboard. Erase the board (power off) and everything is gone.
• Non-volatile = Writing in a notebook. Close the notebook (power off) and the writing
is still there.

Detailed Comparison:

Feature Volatile Storage Non-Volatile Storage

Data on power off Lost Retained
Speed Very fast (nanoseconds) Slower (microseconds to
seconds)
Cost per GB Very expensive Cheaper
Capacity Small (MB to GB) Large (GB to PB)
Technology Electronic (flip-flops, capac- Magnetic, optical, elec-
itors) tronic
Examples Registers, Cache, RAM HDD, SSD, DVD, Tape
Power needed Continuous (to keep data) Only during read/write
DBMS role Buffer pool, sorting, hash- Database files, logs, back-
ing ups

How DBMS Uses Both Types:

VOLATILE (RAM/Cache)
Buffer Pool — keeps hot pages in memory
Sort areas — temporary sort during queries
Hash tables — for join operations

Flush dirty pages

NON-VOLATILE (HDD/SSD)
Database files — actual table data
Index files — B+ tree, hash indexes
Log files — Write-Ahead Log (WAL)

Periodic backup

NON-VOLATILE (Tape)
Full database backups
Disaster recovery copies
Historical archival data

Stable Storage: DBMS creates “stable storage” by writing to multiple non-volatile

devices (e.g., RAID mirroring). Even if one disk fails, data survives. Write-Ahead Logging
(WAL) ensures recovery after crashes.

DBMS Notes
Module 4: Physical Storage, RAID & Indexing Page 5

3 Discuss the difference between Magnetic Disk and Op-

tical Disk.
Magnetic Disk (HDD): Uses spinning metal platters coated with magnetic material. A read-
/write head floats above the platter and reads/writes data by detecting or changing magnetic
patterns.
Optical Disk (CD/DVD/Blu-ray): Uses a flat, reflective disc. A laser beam reads tiny
pits (bumps) and lands (flat areas) on the disc surface.

Structure Comparison:

Magnetic Disk (HDD) Optical Disk (CD/DVD)

R/W Head

Concentric Tracks Single Spiral Track

Laser
Random Access Pits & Lands

Detailed Comparison Table:

Feature Magnetic Disk Optical Disk

Read/Write Electromagnetic head Laser beam
method
Track layout Concentric circles Single spiral
Access speed Fast (5–10 ms seek) Slow (100–200 ms)
Capacity TB range 700 MB (CD) to 128 GB
(Blu-ray)
Rewritability Always rewritable Types: ROM, R, RW
Durability Sensitive to shock Shock resistant
Portability Less portable Highly portable
Cost per GB Low ($0.03) Moderate
Lifespan 3–5 years active use 25–200 years
DBMS usage Primary data storage Archival / distribution
Data encoding Magnetic polarity (N/S) Pits and lands (0/1)

Key takeaway: Magnetic disks are the workhorse of databases (fast, rewritable, large).
Optical disks are used for distributing software or archiving old data.

DBMS Notes
Module 4: Physical Storage, RAID & Indexing Page 6

4 Explain the hierarchy of storage systems in terms of

speed, cost, and capacity.
The storage hierarchy is like a ladder — each step trades speed for capacity.
Three Key Relationships:

Rule 1: Faster storage = More expensive per GB

Rule 2: Faster storage = Smaller capacity
Rule 3: Levels 1–3 are Volatile; Levels 4–7 are Non-Volatile

Complete Hierarchy Table:

Level Storage Type Access Time Cost/GB Typical Size Volatile?

1 Registers < 1 ns $$$$ Bytes Yes
2 L1 Cache ∼1 ns $$$ 32–64 KB Yes
3 L2/L3 Cache 5–10 ns $$ 256 KB–32 MB Yes
4 Main Memory (RAM) ∼100 ns ∼$10 4–256 GB Yes
5 Flash / SSD ∼0.1 ms ∼$0.10 256 GB–4 TB No
6 Magnetic Disk (HDD) 5–10 ms ∼$0.03 1–20 TB No
7 Optical Disk ∼100 ms ∼$0.05 700 MB–128 GB No
8 Magnetic Tape Seconds ∼$0.01 Up to PB No

DBMS Mapping to the Hierarchy:

DBMS Component Storage Level Purpose

Query execution, sorting Levels 1–4 (RAM/Cache) Active processing (“hot” data)
Database files, indexes Levels 5–6 (SSD/HDD) Permanent storage (“warm” data)
Backups, archives Levels 7–8 (Tape/Optical) Recovery, compliance (“cold” data)

Why does this matter? A DBMS tries to keep frequently used data in faster storage
(buffer pool in RAM) and pushes rarely used data to slower storage. This is called the buffer
management strategy.

DBMS Notes
Module 4: Physical Storage, RAID & Indexing Page 7

5 Explain the read/write mechanism of a magnetic disk

with steps in DBMS.
Components of a Magnetic Disk:
Spindle
Track 0
R/WTrack
Head1

Platter 3 Actuator Arm

Platter 2
Platter 1

Component Description
Platter Circular disk coated with magnetic material (both
sides used)
Track Concentric circle on a platter surface
Sector Smallest unit on a track (typically 512 B or 4 KB)
Block/Page Multiple sectors grouped together (4–16 KB), unit
of DBMS I/O
Cylinder Same track position across all platters
R/W Head Electromagnetic device that reads/writes mag-
netic patterns
Actuator Arm Mechanical arm that moves the head to the correct
track
Spindle Motor Spins platters at constant speed (5400–15000
RPM)

Read Operation — Step by Step:

Step What Happens Name Time
1 Arm moves to the correct Seek Time 3–10 ms
track
2 Platter rotates until the tar- Rotational Latency 2–5 ms
get sector is under the head
3 Head reads magnetic pat- Transfer Time ∼0.04 ms (4 KB)
terns; data sent to controller
4 Controller sends data to Bus Transfer < 1 ms
RAM via bus
Access Time Formula:
Total Access Time = Seek Time + Rotational Latency + Transfer Time
Example: Seek = 5 ms, RPM = 7200, Block = 4 KB, Transfer Rate = 100 MB/s.
60 4
Avg Rotational Latency = = 4.17 ms, Transfer = = 0.04 ms
7200 × 2 100,000
Total = 5 + 4.17 + 0.04 = 9.21 ms

DBMS Notes
Module 4: Physical Storage, RAID & Indexing Page 8

6 Discuss the role and performance of magnetic disk in

DBMS.
Why Magnetic Disk is Central to DBMS:
Magnetic disk is the primary persistent storage for almost all traditional databases.
Every table, every index, and every log file sits on disk.
Roles of Magnetic Disk in DBMS:

# Role Explanation
1 Primary Data Storage All table data (rows and columns)
stored in disk blocks
2 Index Storage B+ Tree and hash index files reside on
disk
3 Log Files Write-Ahead Log (WAL) for crash re-
covery
4 Temporary Storage Sort runs and hash partitions during
query execution
5 System Catalog Metadata about tables, columns, con-
straints

Performance Metrics:

Metric What It Measures Typical HDD Value

Seek Time Time to move arm to correct track 3–10 ms
Rotational Latency Time for sector to spin under head 2–5 ms
Transfer Rate Speed of data flow 100–200 MB/s
IOPS I/O operations per second 75–200
MTBF Mean time between failures 300K–1.2M hours

Performance Optimization Techniques in DBMS:

DBMS Notes
Module 4: Physical Storage, RAID & Indexing Page 9

Technique How It Helps

Buffer Management Keep hot pages in RAM (LRU policy); avoid
repeated disk reads
Disk Scheduling SCAN/C-SCAN algorithms minimize arm
movement
Indexing B+ Tree reduces disk reads from O(N ) to
O(log N )
Sequential I/O Read contiguous blocks instead of random
blocks (100× faster)
Prefetching Read upcoming blocks before they are actu-
ally needed
Defragmentation Keep related data contiguous to reduce seek
time
RAID Parallel disk access and fault tolerance

HDD vs SSD comparison (quick):

HDD SSD
Random IOPS 75–200 10K–100K+
Sequential Read 100–200 MB/s 500–7000 MB/s
Cost per TB $20–50 $80–200

DBMS Notes
Module 4: Physical Storage, RAID & Indexing Page 10

7 Explain how data is organized on a magnetic disk with

a diagram.
Data on a magnetic disk is organized in a hierarchy: Platter → Surface → Track → Sector
→ Block.
Top View of a Platter:

Sector
One Sector

Track
Track
3 Track
2 Track
1 0

Spindle

Key Terms Explained:

Term Meaning
Platter Circular metal/glass disk; each has 2 surfaces (top
and bottom)
Surface One side of a platter; each surface has its own R/W
head
Track One concentric ring on a surface
Sector A pie-shaped slice of a track; smallest physical
unit (512 B or 4 KB)
Block / Page Group of consecutive sectors; smallest logical unit
for DBMS (4–16 KB)
Cylinder All tracks at the same radial position across all
surfaces (same arm position, no seek needed)

Cylinder Concept (side view):

Surface 0
Surface 1
Cylinder i
Surface 2
Surface 3
Track i on each surface

DBMS Notes
Module 4: Physical Storage, RAID & Indexing Page 11

Disk Address: Each block is identified by (Surface, Track, Sector) or using LBA
(Logical Block Addressing — a single sequential number).
DBMS organizes data on disk as: Database Files → Table Spaces → Data Pages
(blocks) + Index Pages + Log Files.

DBMS Notes
Module 4: Physical Storage, RAID & Indexing Page 12

8 Explain RAID 0. What are its benefits and draw-

backs?
RAID = Redundant Array of Independent Disks.
RAID 0 (Striping): Data is split into blocks and distributed across multiple disks with-
out any backup copy or parity. Pure speed, zero safety.
How RAID 0 Works:

Original Data: Block 1, 2, 3, 4, 5, 6, 7, 8, 9

Disk 0 Disk 1 Disk 2

Block 1 Block 2 Block 3

Block 4 Block 5 Block 6

Block 7 Block 8 Block 9

Blocks distributed in round-robin across disks

Benefits of RAID 0:

# Benefit
1 Highest performance — reads/writes happen in par-
allel across N disks
2 Full capacity — 100% of all disk space is usable (no
overhead)
3 Simple design — no parity calculations, easy to im-
plement
4 High throughput — N disks give approximately N ×
the bandwidth

Drawbacks of RAID 0:

# Drawback
1 ZERO fault tolerance — if any one disk fails, ALL
data is lost
2 Reliability decreases with more disks: MTBFRAID0 =
MTBFsingle /N
3 No recovery possible — cannot rebuild data from
remaining disks
4 Not suitable for databases with valuable data

Quick Stats (with N disks, each 1 TB, 100 MB/s):

DBMS Notes
Module 4: Physical Storage, RAID & Indexing Page 13

Usable space N TB (100%)

Read speed ∼ N × 100 MB/s
Write speed ∼ N × 100 MB/s
Disks that can fail 0 (none!)

DBMS Notes
Module 4: Physical Storage, RAID & Indexing Page 14

9 Compare RAID 0 and RAID 1 in terms of perfor-

mance and redundancy.
RAID 0 = Striping (speed, no safety). RAID 1 = Mirroring (safety, less capac-
ity).
Visual Comparison:

RAID 0 (Striping) RAID 1 (Mirroring)

Disk 0 Disk 1 Disk 0 Disk 1

A1 A2 A1 A1
A3 A4 A2 A2
A5 A6 A3 A3

Different data on each disk Same data on both disks

Detailed Comparison:

Feature RAID 0 RAID 1

Technique Striping Mirroring
Min. disks 2 2
Redundancy None Full copy
Usable capacity (2 2 TB (100%) 1 TB (50%)
× 1 TB)
Read speed Very high (parallel) High (read from either
copy)
Write speed Very high (parallel) Moderate (write to
both)
Disk failures toler- 0 (any failure = total 1 (mirror survives)
ated loss)
Rebuild Impossible Fast (copy from sur-
vivor)
Cost Cheapest Expensive (2× storage)
Data safety Worst Best
Best DBMS use Temporary / scratch Transaction logs, criti-
data cal data

Key takeaway: RAID 0 gives maximum speed but zero protection. RAID 1 gives maxi-
mum protection but uses double the storage. For databases, RAID 1 (or RAID 10) is preferred
for critical data.

DBMS Notes
Module 4: Physical Storage, RAID & Indexing Page 15

10 How does RAID improve data reliability and perfor-

mance?
RAID improves databases in two ways: making I/O faster (performance) and making data
safer (reliability).
How RAID Improves Performance:

# Technique How It Speeds Things Up

1 Data Striping Split data across N disks ⇒ N par-
allel reads/writes
2 Load Balancing Requests distributed evenly; no sin-
gle disk becomes a bottleneck
3 Increased N disks ≈ N × bandwidth of a single
Throughput disk

How RAID Improves Reliability:

# Technique How It Protects Data

1 Mirroring (RAID Keep an exact duplicate; if one disk
1) dies, the other has all data
2 Parity (RAID 5/6) Store XOR-based parity; recon-
struct lost data mathematically
3 Hot Spare A standby disk auto-replaces a failed
disk and begins rebuilding

Parity Reconstruction Example (RAID 5):

A = 1010 B = 1100 P = 0110

P=A⊕B
Disk 0 FAILS!

Recover: A = P ⊕ B = 0110 ⊕ 1100 = 1010 ✓

RAID Levels — Reliability vs Performance:

RAID Level Performance Gain Reliability Gain Best For

RAID 0 Highest None (worse than single disk) Temp data
RAID 1 Good reads Highest (full mirror) Logs, critical data
RAID 5 Good reads Good (1-disk tolerance) General DB storage
RAID 6 Good reads Better (2-disk tolerance) Large arrays
RAID 10 Highest High (1 per pair) High-perf DBMS

DBMS Notes
Module 4: Physical Storage, RAID & Indexing Page 16

Mathematical Justification:
• Single disk MTBF: 1,000,000 hours
• RAID 0 (2 disks): MTBF = 1,000,000/2 = 500,000 hours (worse!)
MTBF2
• RAID 1 (2 disks): MTBF = 2×MTTR (much better)

DBMS Notes
Module 4: Physical Storage, RAID & Indexing Page 17

11 Advantages of heap file organization over sequential

file organization.
Heap File: Records are stored in no particular order. New records are simply appended
at the end. Like throwing papers into a box.
Sequential File: Records are stored sorted by a key. Like filing papers alphabetically.

Visual Comparison:

Heap File Sequential File

Emp 5 Emp 1
Emp 1 Emp 2
Emp 3 Emp 3
Emp 2 Emp 4
Emp 4 Emp 5

No order Sorted by EmpID

Operation Comparison:

Operation Heap File Sequential File

Insertion O(1) — just append O(N ) — find correct position, shift records
Exact search O(N ) — linear scan O(log N ) — binary search
Range query O(N ) — full scan Fast — records already sorted
Deletion Mark as deleted May need reorganization
Reorganization Not needed Periodically required

Advantages of Heap File over Sequential:

# Advantage
1 Very fast insertions — O(1), just add to end, no sort-
ing
2 Simple implementation — no need for complex or-
dering logic
3 Excellent for bulk loading — pour data in quickly
4 No overflow chains — unlike sequential files that need
overflow blocks
5 No reorganization cost — sequential files degrade
and need periodic cleanup
6 Efficient for full-table scans — every record visited
once regardless of order
7 Good for small tables — linear scan is fast enough

DBMS Notes
Module 4: Physical Storage, RAID & Indexing Page 18

When to use which?

Use Heap Frequent inserts, rare targeted searches, small tables, bulk loads
Use Sequential Frequent range queries, ordered reports, few inserts

DBMS Notes
Module 4: Physical Storage, RAID & Indexing Page 19

12 Differences between fixed-length and variable-length

records.
Fixed-Length Record: Every record takes the exact same number of bytes, regardless
of actual data. Like every student getting a box of the same size.
Variable-Length Record: Records can have different sizes. Like envelopes — some
letters are short, some are long.
Fixed-Length Example:

Every record = 34 bytes

EmpID Name Dept

4 bytes 20 bytes 10 bytes

Finding record i is easy: go to offset i × 34.

Variable-Length — Slotted Page Structure:

Slot 1 Slot 2 Slot 3

Record 3

Record 2

FREE SPACE Record 1

Records grow from the end ←; header grows from the start →; free space is in the middle.
Comparison Table:

Feature Fixed-Length Variable-Length

Record size Same for all Varies per record
Access method Direct: record i at offset Needs pointers / slot
i × size directory
Storage efficiency Wastes space (padding Space efficient
short fields)
Implementation Simple Complex (slotted pages)
Insertion Easy (fixed slot) Must find space that fits
Deletion Reuse slot directly May cause fragmentation
Data types suited INT, CHAR(n), DATE, VARCHAR, TEXT,
FLOAT BLOB, arrays
Fragmentation None Possible (needs com-
paction)

DBMS Notes
Module 4: Physical Storage, RAID & Indexing Page 20

Key insight: Most real databases use variable-length records with slotted pages
because real data has VARCHAR, TEXT, and BLOB columns. The slotted page design makes
inserts/deletes efficient while handling varying sizes.

DBMS Notes
Module 4: Physical Storage, RAID & Indexing Page 21

13 Discuss different types of record organizations in a

database.
Record (file) organization determines how records are physically stored on disk. The
choice impacts insert, search, and delete performance.
Four Main Types:

# Type How It Works

1 Heap (Un- Records added at end in insertion order. No
ordered) sorting.
2 Sequential (Or- Records sorted by a search key. Maintained
dered) in order.
3 Hash A hash function maps the key to a bucket
number. Records go to their bucket.
4 Clustered Related records from one or more tables
stored together in the same blocks.

Visual Comparison:
Heap Sequential Hash Clustered
Rec 5 Rec 1 Bucket 0: Rec 2,4 Dept:CS + Emp:Alice

Rec 1 Rec 2 Bucket 1: Rec 1,5

Dept:Math + Emp:Bob
Rec 3 Rec 3
Bucket 2: Rec 3
Rec 2 Rec 5

Performance Comparison:

Operation Heap Sequential Hash Clustered

Insertion Fast O(1) Slow O(N ) Moderate Moderate
Exact search Slow O(N ) Moderate O(log N ) Fast O(1) Moderate
Range query Slow O(N ) Fast Slow Moderate
Deletion Moderate Slow Moderate Moderate
Full scan OK OK OK OK
Join queries Slow Moderate Moderate Fast

When to use each:

Heap Frequent inserts, full scans, bulk loading, log

tables
Sequential Frequent range queries, generating sorted re-
ports
Hash Frequent equality lookups (e.g., find by pri-
mary key)
Clustered Frequent joins between related tables

DBMS Notes
Module 4: Physical Storage, RAID & Indexing Page 22

14 Explain cluster file organization and its types.

What is Cluster File Organization?
Instead of storing each table separately, records that are frequently accessed together
are stored in the same disk blocks. This dramatically reduces disk I/O for joins and related
queries.
Analogy: Instead of keeping your textbook in the bookshelf and your notebook in a drawer,
you keep them together on your desk because you always use them at the same time.

Two Types of Clustering:

Type 1: Single-Table Clustering (Intra-file)
Records of one table are physically grouped by a clustering attribute.
Block 1:

Block(S1,
2: Alice,
(S2,CS)
Bob, Math)
(S3, Charlie,
(S4, CS)
Dave, Math)
(S5, Eve, CS)

Clustered on DeptID — all CS students in one block

Benefit: “Find all CS students” reads just 1 block instead of scanning the whole table.

Type 2: Multi-Table Clustering (Inter-file)

Records from different tables that share a common key are stored together.

Dept(D1, CS, Bldg-A)

Block 1:
Emp(E1, Alice, D1) Emp(E3, Charlie, D1)

Dept(D2, Math, Bldg-B)

Block 2:
Emp(E2, Bob, D2) Emp(E4, Dave, D2)

Department + its Employees stored in the same block

Benefit: “Join Department and Employee on DeptID” requires zero extra I/O — the
joined data is already together!

Advantages and Disadvantages:

Advantages Disadvantages
Fast join queries (data co- Slower inserts (find correct clus-
located) ter)
Better cache utilization Updates to cluster key are expen-
sive
Fewer disk I/O operations Queries on individual tables may
be slower
Excellent for range queries on Only one clustering order per file
cluster key

DBMS Notes
Module 4: Physical Storage, RAID & Indexing Page 23

15 Elaborate the concept of RAID. What are its advan-

tages?
RAID = Redundant Array of Independent Disks.
RAID combines multiple cheap disks into one logical unit that appears as a single disk
to the operating system and DBMS. It uses three key techniques:
Three Building Blocks of RAID:

1. Striping 2. Mirroring 3. Parity

Split data across Duplicate data on Store XOR checksum
multiple disks separate disks to recover lost data
(speed) (safety) (efficient safety)

Advantages of RAID:

# Advantage Explanation
1 Improved Per- Parallel I/O across multiple disks in-
formance creases read/write throughput
2 Data Redun- Mirroring or parity ensures data sur-
dancy vives disk failure
3 High Availabil- System continues operating even after
ity a disk failure
4 Fault Tolerance Lost data can be rebuilt from mirrors
or parity
5 Scalability Add more disks to increase capacity
and speed
6 Transparency Appears as a single logical disk to
DBMS
7 Cost Effective Multiple cheap disks cheaper than one
high-end disk
8 Hot Swapping Replace a failed disk without shutting
down the system

Disadvantages:

1 RAID controllers add cost and complexity

2 Write penalty in parity-based RAID (must compute and
write parity)
3 Rebuild time can be long for large disks
4 RAID is not a substitute for backups (virus, human
error, etc.)
5 Controller failure can cause total data loss

DBMS Notes
Module 4: Physical Storage, RAID & Indexing Page 24

16 Explain different RAID levels with diagrams.

RAID 0 — Striping (No Redundancy):
Disk 0 Disk 1 Disk 2
A1 A2 A3
A4 A5 A6

Min: 2 disks. Capacity: 100%. Tolerance: 0.

RAID 1 — Mirroring:
Disk 0 Disk 1
A1 A1
=
A2 A2

Min: 2 disks. Capacity: 50%. Tolerance: 1 disk.

RAID 5 — Distributed Parity (most popular for DBMS):

Disk 0 Disk 1 Disk 2 Disk 3
A1 A2 A3 Ap

B1 B2 Bp B3

C1 Cp C2 C3

Dp D1 D2 D3

Min: 3 disks. Capacity: (N −1)/N . Tolerance: 1 disk.

Parity block (red) rotates across all disks

RAID 6 — Double Distributed Parity:

Same as RAID 5 but with two different parity blocks per stripe. Tolerates 2 simultaneous
disk failures.
Min: 4 disks. Capacity: (N −2)/N . Tolerance: 2 disks.
RAID 10 (1+0) — Stripe of Mirrors:
Mirror Pair 1 Mirror Pair 2

A1 A1 A2 A2

A3 A3 A4 A4

Min: 4 disks. Capacity: 50%. Tolerance: 1 per pair.

Summary Table:
Level Technique Min Capacity Tolerance Read Write
0 Striping 2 N 0 High High
1 Mirroring 2 N/2 1 disk High Med
5 Dist. Parity 3 N −1 1 disk High Med
6 Dbl. Parity 4 N −2 2 disks High Low
10 Stripe+Mirror 4 N/2 1/pair Highest High

DBMS Notes
Module 4: Physical Storage, RAID & Indexing Page 25

17 Compare RAID 0, RAID 1, and RAID 5 in terms of

redundancy and performance.
Feature RAID 0 RAID 1 RAID 5
Technique Striping Mirroring Striping + Dis-
tributed Parity
Minimum disks 2 2 3
Redundancy None Full mirror Parity-based
Read speed Very high (paral- High (read from High (∼
lel) either) (N −1)×)
Write speed Very high Moderate (write Moderate (parity
both) overhead)
Write penalty None 2× writes 4 I/Os per write
Disk failures toler- 0 1 per pair 1
ated
Rebuild possible? No (data lost for- Yes (copy from Yes (compute
ever) mirror) from parity)
Rebuild speed — Fast Slow (heavy cal-
culation)
Data safety Worst Best Good
Cost efficiency Best (100%) Worst (50%) Good ( NN−1 )
DBMS use case Temp/scratch Transaction logs General DB stor-
data age

Example with 4 × 1 TB disks:

RAID 0 RAID 1 RAID 5

Usable space 4 TB 2 TB 3 TB
Storage efficiency 100% 50% 75%
Survives 1 disk failure? No Yes Yes
Approx. read speed 4× 2× 3×

Performance Bar Chart (Conceptual):

Read Write Safety

RAID 0 RAID 1 RAID 5 RAID 0 RAID 1 RAID 5 RAID 0 RAID 1 RAID 5

DBMS Notes
Module 4: Physical Storage, RAID & Indexing Page 26

Recommendation: For most databases, use RAID 5 (balance of speed, safety, cost) or
RAID 10 (best speed + safety, but 50% capacity).

DBMS Notes
Module 4: Physical Storage, RAID & Indexing Page 27

18 Explain the basic concept of indexing in DBMS. Dis-

cuss two basic types of indices.
What is Indexing?
An index is like the index at the back of a textbook. Instead of reading every page to find
“B-Tree,” you look it up in the index and jump directly to page 145.
Without an index: search N records ⇒ O(N ) disk reads (full table scan).
With an index: O(log N ) or even O(1) disk reads!
Index Structure:

Index File Data File

10 → 10 Alice
20 → 20 Bob
30 → 30 Charlie
40 → 40 Dave

Each index entry contains: Search Key + Pointer to data record/block.

Two Basic Types of Indices:

Type 1: Ordered Index
Index entries are stored in sorted order of the search key. Supports both equality and
range queries.
Sub-types:
• Primary Index (Clustering): Built on the sorting key of a sorted data file. Can be
sparse.
• Secondary Index (Non-clustering): Built on a non-sorting field. Must be dense.
• Usually implemented as B+ Tree.
Type 2: Hash Index
A hash function h(key) maps the search key to a bucket number. The record is stored in
that bucket.

Feature Ordered Index Hash Index

Equality search O(log N ) O(1) average
Range query Efficient Not supported
Implementation B+ Tree Hash Table
Sorted access? Yes No
Dynamic growth? B+ Tree handles well May need rehashing

DBMS Notes
Module 4: Physical Storage, RAID & Indexing Page 28

19 Explain the structure of a B-Tree with an example.

What is a B-Tree?
A B-Tree is a self-balancing search tree designed for disk-based storage. All leaves are
at the same level, which guarantees O(log N ) access for every query.
Properties of a B-Tree of order m:

Property Value
Maximum children per node m
Maximum keys per node m−1
Minimum children (non-root, internal) ⌈m/2⌉
Minimum keys (non-root) ⌈m/2⌉ − 1
Root minimum children 2 (if not a leaf)
All leaves at same level? Yes (always balanced)

Node Structure:

P0 K1 P1 K2 P2 K3 P3

< K1 K1 < . . . < K2 K2 < . . . < K3 > K3

Ki = keys (sorted), Pi = pointers to children or data records.

Example: Build a B-Tree of order 3 by inserting 10, 20, 30, 40, 50, 60, 70:
A node can hold at most m − 1 = 2 keys. When a node overflows (3 keys), it splits.

40

20 60

10 30
50 70

How it was built:

Insert Tree State

10, 20 Root: [10, 20]
30 Overflow! Split ⇒ Root: [20], Left: [10], Right: [30]
40 Right becomes [30, 40]
50 Overflow! Split ⇒ Root: [20, 40], Children: [10], [30], [50]
60 Right becomes [50, 60]
70 Overflow! Root also overflows ⇒ New root: [40] (as shown above)

B-Tree vs B+ Tree:

DBMS Notes
Module 4: Physical Storage, RAID & Indexing Page 29

Feature B-Tree B+ Tree

Data pointers at All nodes Leaves only
Leaves linked? No Yes (linked list)
Range queries Less efficient Very efficient
DBMS usage Less common Most common

DBMS Notes
Module 4: Physical Storage, RAID & Indexing Page 30

20 Explain the ordered indices in DBMS with example.

Ordered Index: An index where entries are stored in sorted order of the search key. It
allows efficient searching using binary search or tree traversal.

Three Sub-types of Ordered Indices:

1. Dense Index — one index entry for every record.

Dense Index Data File

10 → 10, Alice
20 → 20, Bob
30 → 30, Charlie
40 → 40, Dave

Finding record with key 30: search index ⇒ follow pointer ⇒ direct access.

2. Sparse Index — one index entry per block (not every record). Data must be sorted.

Sparse Index Data File (2 recs/block)

10, Alice
10 → 20, Bob

30, Charlie
30 → 40, Dave

Finding key 20: index gives 10 (largest ≤ 20) ⇒ go to that block ⇒ scan block to find 20.

3. Multilevel Index — when the index itself is too large, build an index on the index.

Outer Index Inner Index Data Blocks

10 → 10 → Block 1
100 → 50 → Block 2
100 → Block 3
150 → Block 4

Comparison Table:

Feature Dense Sparse Multilevel

Index entries One per record One per block One per index block
Index size Large Small Hierarchical
Lookup speed Fastest Slower (block scan) Moderate
Data must be sorted? No Yes Yes
Space usage More Less Structured
Best for Secondary index Primary index Very large files

Key insight: In practice, B+ Trees implement multilevel ordered indices automatically.

Each level of the B+ Tree is like one level of a multilevel index, with leaf nodes forming a dense
index linked as a list.

DBMS Notes