File Structures, Hashing and Indexing

Introduction
In database systems, persistent data is stored on secondary storage (magnetic disks or SSDs)
because primary memory is limited and volatile. The performance of a DBMS is largely
governed by the efficiency of disk access operations, since disk I/O is the most expensive
operation compared to CPU processing.

A file is a collection of related records stored on disk. A record is a collection of fields

describing an entity, and a field represents an attribute.

The design of file structures aims to:

 Minimize disk seek time, rotational latency, and transfer time

 Optimize block utilization
 Support efficient search, insertion, deletion, and update operations

The efficiency of a database depends on:

 File organization
 Access methods
 Buffer management
 Indexing techniques

Disk Storage Fundamentals

A disk consists of:

 Platters coated with magnetic material

 Tracks (concentric circles)
 Sectors (subdivisions of tracks)
 Cylinders (set of tracks aligned vertically across platters)

Disk Access Time Components

1. Seek Time
Time required to move the disk arm to the desired track
2. Rotational Latency
Time for the desired sector to rotate under the read/write head
3. Transfer Time
Time to read/write data

Total Access Time = Seek Time + Rotational Latency + Transfer Time

Because seek time is dominant, file structures aim to reduce disk head movement.
File Organization Techniques
File organization defines how records are physically stored on disk.

1. Heap File Organization

Records are placed in no specific order.

Characteristics:

 Records inserted wherever space is available

 Uses free space list to track empty blocks

Advantages:

 Fast insertion
 Simple structure

Disadvantages:

 Linear search required → O(n)

 Poor performance for large datasets

Use Case:

 Temporary data storage

2. Sequential File Organization

Records are stored in sorted order based on a key.

Characteristics:

 Maintains order physically

 Suitable for batch processing

Advantages:

 Efficient for range queries

 Sequential access is fast

Disadvantages:

 Insertions require shifting records

 Deletions create gaps

Use Case:

 Payroll systems, report generation

3. Hashed File Organization
Records are placed using a hash function.

Characteristics:

 Direct access using key

 No ordering of records

Advantages:

 O(1) average search time

 Efficient equality queries

Disadvantages:

 Poor for range queries

 Collision handling required

4. Indexed File Organization

An auxiliary structure (index) is used to locate records.

Characteristics:

 Logical ordering via index

 Physical storage may remain unordered

Advantages:

 Fast search
 Supports range queries

Disadvantages:

 Extra storage
 Maintenance overhead

Placing File Records on Disk

Blocking

Disk transfers occur in units called blocks (pages).

Blocking Factor (bfr)

bfr = Block Size / Record Size

If:
Block Size = 1024 bytes
Record Size = 128 bytes

bfr = 8 records per block

Spanned vs Unspanned Records

 Unspanned: Record cannot cross block boundary

 Spanned: Record can occupy multiple blocks

Spanned records improve space utilization but complicate retrieval.

Hashing Techniques
Hashing transforms a search key into a physical address.

Hash Function

h(K) = K mod M

Where:

 K = key
 M = number of buckets

Bucket

A bucket is a storage location that can hold multiple records.

Collision Resolution
1. Separate Chaining

Each bucket contains a linked list of records.

Advantage:

 Simple implementation

Disadvantage:

 Extra pointer overhead

2. Open Addressing

Find alternate locations.

Methods:

 Linear probing
 Quadratic probing
 Double hashing

Static Hashing
 Fixed number of buckets
 Does not adapt to growth

Problem:

 Overflow chains increase

Dynamic Hashing
Extendible Hashing

 Uses directory of pointers

 Buckets split dynamically

Concepts:

 Global depth
 Local depth

Linear Hashing

 Buckets split gradually

 No directory required

Advantages:

 Better space utilization

 Reduced overflow

Indexing
Indexing improves search efficiency by reducing disk access.

Index Structure

An index entry contains:

 Search key
 Pointer to record
Types of Indexes
Primary Index

 Based on ordering key

 Sparse index

Secondary Index

 Based on non-ordering field

 Dense index

Dense Index

 Entry for every record

Search complexity:

 O(log n) with tree

Sparse Index

 Entry for some records

Search process:

 Find nearest key → scan

Multilevel Indexing
Indexes can be built on top of indexes.

Benefits:

 Reduces search time

 Improves scalability

B-Tree Index
Balanced tree structure.

Properties:

 All nodes have multiple children

 Height is small
Operations:

 Search: O(log n)
 Insert/Delete: Balanced

B+ Tree Index
Improved version of B-Tree.

Characteristics:

 Data stored only in leaf nodes

 Leaf nodes linked

Advantages:

 Efficient range queries

 Better disk utilization

Hashing vs Indexing (Theoretical Comparison)

Feature Hashing Indexing
Access Type Direct Sequential + Direct
Query Type Equality Equality + Range
Structure Hash table Tree structure
Performance O(1) avg O(log n)

RAID Technology
RAID stands for: Redundant Array of Independent Disks

Originally, RAID was called Redundant Array of Inexpensive Disks, but the term
“Independent” is now preferred because it reflects the use of multiple disks working together as a
single system.

Theoretical Explanation
RAID is a technology that combines multiple physical disk drives into a single logical unit to
achieve:

 Higher performance through parallel disk access

 Fault tolerance through redundancy
 Improved data reliability and availability
RAID achieves this using three main techniques:

 Striping → Splitting data across multiple disks for parallel access

 Mirroring → Copying identical data to multiple disks
 Parity → Storing extra information to recover lost data

Why RAID is Needed

Single disk systems have limitations:

 Slow access due to mechanical delays

 High risk of data loss if disk fails

RAID overcomes these by:

 Distributing workload across disks

 Providing backup through redundancy

Conceptual Working
Instead of storing data on one disk:

Data → Split into blocks → Stored across multiple disks

Example (RAID 0 concept):

Disk 1 → Block A
Disk 2 → Block B
Disk 3 → Block C

All blocks can be accessed simultaneously → parallelism

RAID Levels (Theoretical View)

RAID 0

 Striping only
 No redundancy

Performance:

 High

Reliability:

 Low
RAID 1

 Mirroring

Performance:

 Read fast

Reliability:

 Very high

RAID 3

 Byte-level striping + parity

RAID 4

 Block-level striping + single parity disk

Problem:

 Parity disk bottleneck

RAID 5

 Distributed parity

Advantages:

 Balanced performance
 Fault tolerance

RAID 6

 Double parity

Advantage:

 Survives two disk failures

Parallel Disk Access

RAID enables:

 Parallel reads/writes
 Reduced response time
 Increased throughput
Advanced Considerations
Buffer Management

 Frequently accessed blocks stored in memory

 Reduces disk I/O

Clustering

 Related records stored together

 Improves locality

File Fragmentation

 Occurs when records are scattered

 Reduces performance

Indexing Structures for Files

Introduction
Indexing is a technique used in database systems to improve the speed of data retrieval by
reducing the number of disk accesses required to locate records.

An index is an auxiliary data structure that contains:

 A search key value

 A pointer (address) to the corresponding record or block on disk

Instead of scanning the entire file, the DBMS uses the index to directly locate required data,
thereby significantly improving performance.

Indexes are especially useful for:

 Large databases
 Frequently searched attributes
 Query optimization

Types of Single-Level Ordered Indexes

Single-level indexes are the simplest form of indexing, where only one index structure is
maintained on the data file.

1. Primary Index

A Primary Index is defined on a file that is physically ordered based on a primary key.
Characteristics:

 File must be sorted on the primary key

 Usually implemented as a sparse index
 One index entry per block

Structure

Key Value Block Pointer

Advantages:

 Efficient search using binary search

 Requires less storage

Disadvantages:

 Insertions and deletions are costly

 Requires maintaining sorted order

2. Clustering Index

A Clustering Index is defined on a file ordered by a non-key attribute.

Characteristics:

 Multiple records can have same value

 One entry per distinct value

Example

DeptID Block Pointer

Advantages:

 Efficient retrieval of groups of records

 Useful for grouping data

Disadvantages:

 More complex maintenance

3. Secondary Index

A Secondary Index is defined on an attribute that is not used for physical ordering.
Characteristics:

 File is not sorted

 Requires dense index
 May have multiple entries for same key

Structure

Key Value Record Pointer

Advantages:

 Supports fast access on non-key attributes

 Useful for multiple search conditions

Disadvantages:

 Requires more storage

 Higher maintenance cost

Dense vs Sparse Index

Dense Index:

 One index entry for each record

 Faster access

Sparse Index:

 One entry per block or group

 Less storage required

Limitations of Single-Level Indexing

 Large index size for big files
 Increased search time when index grows
 Requires multiple disk accesses

To overcome these limitations, multilevel indexing is used.

Dynamic Multilevel Indexes

Multilevel indexing organizes indexes in hierarchical levels, reducing search complexity.

Instead of searching a large index, we search:

 Top-level index → points to lower-level index → points to data

This reduces search time to logarithmic complexity.

B-Tree Index Structure
A B-Tree is a balanced tree structure used for indexing.

Properties of B-Tree

 All nodes have multiple children

 Keys within a node are sorted
 Tree remains balanced
 Each node contains:
o Keys
o Pointers to child nodes

Structure

Internal nodes store keys and pointers

Leaf nodes also store data

Operations

Search:

 Start from root → traverse down

Insert:

 Insert in leaf
 Split node if full

Delete:

 Merge or redistribute nodes

Advantages

 Balanced tree ensures O(log n) search time

 Efficient insertion and deletion

Disadvantages

 More complex than simple indexing

 Data stored in internal nodes reduces efficiency

B+ Tree Index Structure

A B+ Tree is an improved version of B-Tree.
Key Characteristics

 Data stored only in leaf nodes

 Internal nodes store only keys
 Leaf nodes are linked sequentially

Structure

Root → Internal Nodes → Leaf Nodes (linked list)

Advantages

 Efficient range queries

 Better disk utilization
 Sequential access is fast

Comparison: B-Tree vs B+ Tree

Feature B-Tree B+ Tree

Data Storage All nodes Leaf nodes only

Search Path May end early Always goes to leaf

Range Queries Less efficient Highly efficient

Sequential Access Not efficient Efficient

B+ Tree is widely used in real-world database systems.

Indexes on Multiple Keys

In many cases, queries involve multiple attributes. For such cases, special indexing techniques
are used.

1. Composite (Concatenated) Index

An index on multiple attributes combined together.

Example

Index on (DeptID, CourseID)

DeptID CourseID Pointer

Used when queries involve both attributes together.

2. Advantages

 Improves performance for multi-condition queries

 Reduces need for multiple indexes

3. Limitations

 Order of attributes matters

 Not efficient if only one attribute is used

Other Multi-Key Indexing Techniques

1. Secondary Index on Multiple Attributes

Separate indexes maintained for each attribute.

2. Bitmap Index

 Uses bit vectors

 Efficient for low-cardinality attributes

Example

Gender → 1010 pattern

3. Hash-Based Multi-Key Index

 Combines multiple keys into hash value

Query Processing, Optimization and

Database Tuning
Introduction
Query processing is the mechanism by which a DBMS converts a high-level SQL query into an
efficient execution plan. Since databases operate on disk-resident data, the dominant cost is
disk I/O, making optimization essential.

A query can be executed in many different ways, but the DBMS aims to choose the plan with
minimum execution cost. This involves:

 Translating SQL into relational algebra

 Applying optimization techniques
 Selecting efficient algorithms
Internal Query Representation
After parsing, SQL is transformed into:

 Relational Algebra Expression

 Query Tree (Logical Plan)

Example

SQL:

SELECT Name
FROM STUDENT
WHERE Age > 20;

Relational Algebra:
π Name (σ Age > 20 (STUDENT))

Explanation

 Selection (σ) filters tuples

 Projection (π) selects attributes

Query Tree Representation

Root → Projection
Child → Selection
Leaf → STUDENT

This tree becomes the basis for optimization.

Heuristic Query Optimization (Rule-Based)

Heuristic optimization uses transformation rules to improve performance without computing
exact cost.

Core Idea

Reduce size of intermediate results as early as possible.

1. Selection Pushdown

σ Age > 20 (STUDENT ⋈ DEPARTMENT)

→ (σ Age > 20 (STUDENT)) ⋈ DEPARTMENT

Reason:

 Filters tuples before join

 Reduces join cost significantly
2. Projection Pushdown

π Name (STUDENT ⋈ DEPARTMENT)

→ π Name (π Name,DeptID (STUDENT) ⋈ DEPARTMENT)

Reason:

 Reduces number of attributes

 Saves memory and I/O

3. Join Reordering

(R ⋈ S) ⋈ T = R ⋈ (S ⋈ T)

Optimizer chooses order based on:

 Relation size
 Selectivity

4. Replace Cartesian Product + Selection with Join

σ condition (R × S) → R ⋈ S

Cost-Based Query Optimization

Cost-based optimization evaluates multiple execution plans and selects the best one based on
estimated cost.

Cost Components

 Disk I/O cost (most important)

 CPU cost
 Memory usage

Selectivity Factor

Selectivity = fraction of tuples satisfying a condition

Example
1000 tuples → 100 satisfy → selectivity = 0.1

Lower selectivity → better filtering

Cardinality Estimation
Used to estimate result size.

For join:

|R ⋈ S| ≈ (|R| × |S|) / max(V(R,A), V(S,A))

Where:

 |R| = number of tuples

 V(R,A) = distinct values of attribute A

Algorithms for External Sorting

External sorting is required when data exceeds main memory.

External Merge Sort

Phase 1: Run Generation

 Divide file into chunks

 Sort each chunk
 Write sorted runs

Phase 2: Merge Phase

 Merge runs using multi-way merge

Example

File = 1000 records

Memory = 100 records

→ 10 sorted runs
→ Merge runs in passes

Cost

Number of passes = log₍M−1₎ (N / M)

Algorithms for SELECT Operation

1. Linear Search
  Scan entire file

Cost:
b block accesses

2. Binary Search

 Works on sorted file

Cost:
log₂ b

3. Index-Based Selection

 Use index to directly locate record

Example:
Primary index → direct access

4. Hash-Based Selection

 Use hash function

Best for:
Equality conditions

Algorithms for JOIN Operations

JOIN is the most expensive operation in query processing.

1. Nested Loop Join

For each tuple in R:

 Scan S

Cost:
|R| × |S|

2. Block Nested Loop Join

 Process blocks instead of tuples

Reduces disk I/O

3. Indexed Nested Loop Join

 Use index on inner relation

Efficient when:
Index exists

4. Sort-Merge Join

Steps:

1. Sort both relations

2. Merge matching tuples

Efficient for large datasets

5. Hash Join

Two phases:

Partition Phase:

 Divide relations using hash

Probe Phase:

 Match partitions

Cost:
≈ 3 × (bR + bS)

Algorithms for PROJECT Operation

Projection removes unwanted attributes.

Steps

1. Extract required attributes

2. Remove duplicates

Duplicate Removal

Sorting Method

 Sort tuples
 Remove adjacent duplicates

Hashing Method

 Store unique values in hash table

Algorithms for Set Operations

Union (∪)

Combine tuples
Remove duplicates

Intersection (∩)

Find common tuples

Difference (−)

Find tuples in R not in S

Query Execution Plan (QEP)

A QEP defines:

 Order of operations
 Algorithms used
 Access methods

Example:

 Use index scan instead of full scan

 Use hash join instead of nested loop

Database Tuning (Advanced Theory)

Database tuning improves performance by optimizing system design.

1. Index Tuning

 Create indexes on frequently used attributes

 Avoid redundant indexes

2. Query Rewriting

Bad:
SELECT *

Good:
SELECT required columns

3. Buffer Management

 Cache frequently used blocks

 Reduce disk I/O

4. File Organization
  Use clustering
 Store related records together

5. Hardware Tuning

 Use SSD
 Increase RAM
 Apply RAID

Example of Optimization
Original:

π Name (σ Age > 20 (STUDENT ⋈ DEPARTMENT))

Optimized:

π Name ((σ Age > 20 (STUDENT)) ⋈ DEPARTMENT)

Benefit

 Reduces tuples before join

 Improves performance

Final Understanding
 Query processing = translation + execution
 Optimization = choosing best plan
 Algorithms = execution efficiency
 Tuning = real-world performance improvement

Advanced Query Processing Concepts

Introduction
Advanced query processing focuses on efficient execution of complex operations such as
aggregate functions, outer joins, pipelining, and optimization techniques. These operations are
critical in real-world database systems where queries involve large datasets and multiple
operations.

The DBMS must ensure:

 Minimal disk I/O

 Reduced intermediate results
 Efficient use of memory
Implementing Aggregate Operations
Aggregate operations compute a single value from a set of tuples.

Common Aggregate Functions

 COUNT()
 SUM()
 AVG()
 MAX()
 MIN()

Basic Implementation Approach

Aggregate operations can be implemented using two main techniques:

1. Sorting-Based Aggregation

Steps:

1. Sort tuples based on grouping attributes

2. Scan sorted data
3. Compute aggregates for each group

Example

STUDENT

Course Marks
MCA 80
MCA 90
BCA 70

Query

SELECT Course, AVG(Marks) FROM STUDENT GROUP BY Course

Processing:

 Sort by Course
 Compute average per group

2. Hash-Based Aggregation
Steps:

1. Apply hash function on grouping attribute

2. Store groups in hash table
3. Compute aggregate values

Advantages:

 Faster than sorting for large data

 No need to sort

Memory Consideration

 If data fits in memory → single-pass algorithm

 Otherwise → multi-pass (external aggregation)

Implementing OUTER JOINs

Outer joins extend join operations by including non-matching tuples.

Types of Outer Join

1. LEFT OUTER JOIN

2. RIGHT OUTER JOIN
3. FULL OUTER JOIN

LEFT OUTER JOIN

Returns:

 All tuples from left relation

 Matching tuples from right relation
 Non-matching → NULL

Example

STUDENT

RollNo Name
101 Amit
102 Ravi

ENROLL

RollNo Course
101 MCA
Result

RollNo Name Course

101 Amit MCA
102 Ravi NULL

Implementation Methods

Outer joins are implemented using:

 Nested Loop Join (with NULL padding)

 Sort-Merge Join (modified to include unmatched tuples)
 Hash Join (extended with unmatched handling)

Combining Operations Using Pipelining

Concept of Pipelining

Pipelining allows output of one operation to be used directly as input to another, without
storing intermediate results on disk.

Types of Pipelining

1. Materialization (Non-Pipelined)

 Intermediate results are stored on disk

 Slower due to disk I/O

2. Pipelining (On-the-fly Processing)

 Results passed directly between operations

 No intermediate storage

Example

Query

SELECT Name FROM STUDENT WHERE Age > 20

Without pipelining:

 Store selection result → apply projection

With pipelining:

 Pass tuples directly from selection to projection

Advantages
  Reduces disk I/O
 Improves performance
 Reduces memory usage

Limitation

 Not all operations support pipelining

 Sorting requires materialization

Using Heuristics in Query Optimization

Heuristic optimization uses rules to transform queries into more efficient forms.

Key Heuristic Rules

1. Apply Selection Early

σ condition (R ⋈ S)
→ (σ condition (R)) ⋈ S

2. Apply Projection Early

π attributes (R ⋈ S)
→ π attributes (π attributes(R) ⋈ π attributes(S))

3. Replace Cartesian Product with Join

→R⋈S
σ condition (R × S)

4. Reorder Join Operations

 Join smaller relations first

 Reduce intermediate results

Goal of Heuristics

 Minimize size of intermediate relations

 Reduce computational cost

Using Selectivity and Cost Estimates in Query Optimization

Cost-based optimization uses statistical information to choose the best execution plan.

Selectivity
Selectivity measures how restrictive a condition is.

Formula

Selectivity = (Number of tuples satisfying condition) / (Total tuples)

Example

Total tuples = 1000

Condition matches = 100

Selectivity = 0.1

Lower selectivity → better filtering

Cost Estimation
Cost is mainly determined by:

 Disk I/O operations

 CPU processing
 Memory usage

Example (Selection Cost)

Linear search:
Cost = number of blocks (b)

Index search:
Cost = log₂ b

Join Cost Estimation

Nested Loop Join:

Cost ≈ |R| × |S|

Hash Join:
Cost ≈ 3 × (bR + bS)

Choosing Optimal Plan

The optimizer:

1. Generates multiple execution plans

2. Estimates cost for each
3. Selects lowest-cost plan

Example
Query

SELECT * FROM STUDENT WHERE Age > 20

Plan 1:
Full table scan

Plan 2:
Use index on Age

If selectivity is low → index is better

Combined Optimization Strategy

Modern DBMS uses:

 Heuristic optimization (initial pruning)

 Cost-based optimization (final selection)

Physical Database Design and Database

Tuning in Relational Systems
Introduction
After completing conceptual design (ER model) and logical design (relational schema &
normalization), the next step is Physical Database Design.

Physical design deals with:

 How data is actually stored on disk

 Which access paths (indexes) are used
 How performance can be optimized

It focuses on:

 Minimizing disk I/O

 Improving query execution time
 Efficient use of storage and memory

Physical Database Design in Relational

Databases
Definition
Physical database design is the process of selecting:
  File organizations
 Index structures
 Storage parameters

to achieve efficient data access and update performance.

Objectives of Physical Design

 Reduce data access time
 Optimize query performance
 Minimize storage overhead
 Improve throughput and response time

Steps in Physical Database Design

1. Analyze Database Requirements

 Identify frequently used queries

 Determine transaction types
 Analyze workload characteristics

Example:

 Frequent SELECT → need indexing

 Frequent INSERT → avoid too many indexes

2. Choose File Organization

Different file organizations affect performance.

Heap File

 Unordered
 Fast insertion
 Slow search

Sequential File

 Ordered
 Efficient for range queries

Hashed File

 Direct access
 Best for equality queries

3. Index Selection

Indexes are critical for performance.

Types of Indexes

 Primary Index
 Secondary Index
 Clustering Index
 Composite Index

Index Selection Criteria

 Attributes used in WHERE clause

 Attributes used in JOIN conditions
 High selectivity attributes

Trade-Off

More indexes:

 Faster retrieval
 Slower updates

4. Clustering of Data

Clustering means storing related records together.

Example:

 Store STUDENT and ENROLL data close

Benefits:

 Reduces disk I/O

 Improves join performance

5. Partitioning

Divide large tables into smaller parts.

Types

 Horizontal Partitioning (rows)

 Vertical Partitioning (columns)

Advantages:

 Parallel processing
 Faster access

6. Denormalization (Advanced Concept)

Denormalization introduces redundancy to improve performance.

Example:
Combine STUDENT and DEPARTMENT

Benefit:

 Reduces joins

Cost:

 Increased redundancy

7. Storage Parameters

 Block size
 Record size
 Buffer size

These affect:

 Number of disk accesses

 Performance

Physical Design Example

Query:

SELECT Name FROM STUDENT WHERE DeptID = 10

Optimization:

 Create index on DeptID

Result:

 Faster retrieval

Overview of Database Tuning in Relational

Systems
Definition
Database tuning is the process of improving performance of a database system by adjusting:

 Queries
 Indexes
 Storage structures
 Hardware
Objectives of Database Tuning
 Reduce query execution time
 Improve throughput
 Optimize resource utilization
 Ensure scalability

Levels of Database Tuning

1. Query-Level Tuning

Focus on improving SQL queries.

Techniques

 Avoid SELECT *
 Use proper WHERE conditions
 Reduce unnecessary joins

Example

Bad:
SELECT * FROM STUDENT

Good:
SELECT Name FROM STUDENT

2. Index Tuning

 Create indexes on frequently used attributes

 Remove unused indexes

3. Schema Tuning

 Normalize to remove redundancy

 Denormalize for performance

4. Memory Tuning

 Increase buffer cache

 Reduce disk I/O

5. File and Storage Tuning

 Use clustering
 Choose proper file organization

6. Hardware Tuning
  Use SSD instead of HDD
 Increase RAM
 Use RAID

Performance Bottlenecks
 Disk I/O
 Poor indexing
 Inefficient queries
 Memory limitations

Example of Database Tuning

Query:

SELECT * FROM STUDENT WHERE Age > 20

Problem:

 Full table scan

Solution:

 Create index on Age

Result:

 Faster query execution

Trade-Offs in Tuning
Technique Advantage Disadvantage

Indexing Fast search Slow updates

Denormalization Faster queries Redundancy

Partitioning Parallelism Complexity

Monitoring and Evaluation

DBMS uses:

 Query execution plans

 Performance statistics
 Cost estimation