Physical Database Organization

Overview

Having established the principles of logical database design through the relational model, we now descend to the physical level of implementation. This chapter addresses the critical question of how data is physically stored on and retrieved from secondary storage devices such as disks. The abstract tables and relations we have worked with must ultimately be mapped to blocks of data, and the efficiency of this mapping is paramount to the performance of any database management system. The choices made at this level directly determine the speed at which the system can respond to queries and execute transactions.

We shall explore the two fundamental concepts that govern this physical layer: File Organization and Indexing. File organization dictates the strategy by which records are arranged within data files, directly influencing the time complexity of retrieval, insertion, and modification operations. Indexing, in turn, provides auxiliary access paths—akin to an index in a book—to dramatically accelerate the search for specific records without scanning the entire dataset. A thorough understanding of these mechanisms is indispensable, as questions in the GATE examination frequently require a quantitative analysis of the performance trade-offs inherent in different physical design choices.

---

Chapter Contents

| # | Topic | What You'll Learn |
|---|-------|-------------------|
| 1 | File Organization | Techniques for arranging records in files. |
| 2 | Indexing | Data structures for accelerating data access. |

---

Learning Objectives

---

---

We now turn our attention to File Organization...

Part 1: File Organization

Introduction

In the context of database management systems, the physical storage of data on a secondary storage device, such as a disk, is a matter of critical importance. The efficiency with which data can be retrieved, updated, and managed is fundamentally dependent on how records are arranged within files. File organization refers to the logical arrangement of records in a file and the corresponding methods used to access them. A well-chosen file organization strategy can significantly reduce the number of disk accesses required for database operations, thereby enhancing overall system performance.

We shall explore the primary methods of file organization, analyzing their respective advantages and disadvantages in terms of operational costs. Understanding these foundational structures is essential, as they form the basis for more complex data access mechanisms, such as indexing. The choice of a particular organization method is a design decision that involves trade-offs between the speed of data retrieval, the efficiency of insertions and deletions, and the utilization of storage space.

---

Key Concepts

The performance of any file organization method is typically measured in terms of the number of block accesses (or I/O operations) required to perform a task. Let us first define the fundamental parameters used in these calculations.

Common Parameters:

• $B$ : Block size (in bytes)


• $R$ : Record size (in bytes)


• $N$ : Total number of records in the file


• $P$ : Size of a block pointer (in bytes)

From these, we derive two critical metrics:

1. Heap (Unordered) File Organization

In a heap file organization, records are placed in the file in the order they are inserted. A new record is simply appended to the last block of the file. If the last block is full, a new block is allocated. This is the simplest and most basic method of file organization.

Performance Characteristics:

• Insertion: Very efficient. We locate the last block and add the record. This typically requires 1 I/O to read the last block and 1 I/O to write it back. Cost: $O(1)$ .


• Search: Very inefficient. To find a specific record, one might have to scan the entire file from the beginning, as there is no ordering. In the worst case, we must search all blocks. Cost (average): $\frac{b}{2}$ block accesses. Cost (worst-case): $b$ block accesses.


• Deletion: Inefficient. Deletion first requires a search for the record. After finding the record in a block, the block must be modified and written back. Cost is dominated by the search.

2. Sequential File Organization

In a sequential file organization, records are physically stored in a sorted order based on the value of a unique search key. This ordering allows for highly efficient processing of records in sequence and enables the use of binary search for record retrieval.

Performance Characteristics:

• Insertion: Inefficient. To maintain the sorted order, inserting a new record may require shifting all subsequent records, which can be a costly operation involving many block reads and writes.


• Search: Highly efficient. Since the records are sorted, we can use a binary search algorithm on the blocks to locate the record. Cost: $O(\log_2 b)$ block accesses.


• Deletion: Inefficient. Similar to insertion, deleting a record may require reorganizing the file to fill the empty space and maintain contiguity.

Worked Example:

Problem:
Consider a file with $N = 30,000$ records. Each record is $R = 100$ bytes long. The file is stored on a disk with a block size of $B = 1024$ bytes. If the file is organized as a sorted sequential file, calculate the approximate number of block accesses required to search for a record using binary search.

Solution:

Step 1: Calculate the blocking factor ($bfr$) .

Step 2: Calculate the total number of blocks ($b$) required for the file.

Step 3: Calculate the number of block accesses for a binary search.

The number of accesses is given by the formula for binary search on $b$ blocks.

Step 4: Evaluate the logarithm.

We know that $2^{11} = 2048$ and $2^{12} = 4096$ . Since $2048 < 3000 < 4096$ , the value of $\log_2 3000$ is between 11 and 12.

Answer: \boxed{12 \text{ block accesses}}

---

---

#
## 3. Hashed File Organization

In hashed file organization, a hash function is applied to a specific key field of a record. The output of this hash function, known as the hash value, determines the block address where the record should be stored. This allows for extremely fast direct access to records. The blocks are often referred to as buckets.

Performance Characteristics:

• Insertion, Search, Deletion: Ideally, these operations are very fast. We compute the hash of the key, which directly gives the block address. This requires only one block access. Cost: $O(1)$.


• Collisions: The primary challenge is collisions, which occur when the hash function generates the same block address for two different keys. Collisions are handled by techniques like chaining or open addressing, which may increase the number of block accesses beyond one.


• Range Queries: Hashed organization is inefficient for retrieving a range of records (e.g., "find all employees with salary between 40000 and 50000"), as the hash function scatters related records across different blocks.

---

Problem-Solving Strategies

---

---

Common Mistakes

---

Practice Questions

:::question type="NAT" question="A file contains 25,000 records, where each record is 200 bytes in size. The data is stored in a disk with a block size of 4096 bytes. The file is sorted on a primary key. What is the number of block accesses required to find a record using binary search?" answer="11" hint="First, calculate the blocking factor. Then, find the total number of blocks. Finally, apply the formula for binary search on the blocks." solution="
Step 1: Calculate the blocking factor ($bfr$).

Step 2: Calculate the total number of blocks ($b$).

Step 3: Calculate the binary search cost.

We know $2^{10} = 1024$ and $2^{11} = 2048$. Since $1024 < 1250 < 2048$, $\log_2 1250$ is between 10 and 11.

Result:
The number of block accesses is 11.
Answer: \boxed{11}
"
:::

:::question type="MCQ" question="Which of the following file organization methods is most efficient for processing records in a sorted order?" options=["Heap File Organization","Sequential File Organization","Hashed File Organization","B+ Tree File Organization"] answer="Sequential File Organization" hint="Consider which organization inherently stores data based on a sorted key." solution="
Sequential File Organization stores records physically sorted based on a search key. This makes it trivial to read records in that sorted order by simply scanning the file from the beginning. Heap files are unordered. Hashed files scatter records based on a hash function, destroying any natural order. While B+ Trees support ordered traversal, the fundamental method designed specifically for this purpose is Sequential File Organization.
"
:::

:::question type="MSQ" question="Select all the statements that are TRUE regarding Heap File Organization." options=["Insertion of a new record is typically very efficient.","It is well-suited for range queries.","Searching for a specific record may require scanning the entire file in the worst case.","Records are stored in a sorted order based on a primary key."] answer="Insertion of a new record is typically very efficient.,Searching for a specific record may require scanning the entire file in the worst case." hint="Evaluate the performance characteristics of adding, searching, and ordering records in a heap file." solution="

• Option A (Correct): In a heap file, new records are simply appended to the end, making insertion a very fast operation, typically requiring only a couple of I/Os.


• Option B (Incorrect): Since records are unordered, a range query (e.g., find all employees with age between 30 and 40) would require a full scan of the file, which is highly inefficient.


• Option C (Correct): As there is no order, locating a specific record without an index requires a linear scan. In the worst-case scenario, the record is the last one in the file or not present, necessitating a scan of all blocks.


• Option D (Incorrect): This describes Sequential File Organization. Heap files are by definition unordered.

"
:::

:::question type="NAT" question="A database file uses a hashed file organization. It contains 500 buckets (blocks), and there are no overflow blocks. Assuming an ideal hash function with no collisions, how many block accesses are required to delete a specific record?" answer="1" hint="Consider the fundamental principle of hashed organization for direct access." solution="
Step 1: In a hashed file organization, a hash function is applied to the record's key.

Step 2: The function directly computes the address of the bucket (block) where the record is stored.

Step 3: To delete the record, the system must first fetch it. This requires reading the corresponding bucket from the disk. Under ideal conditions (no collisions), this takes one block access.

Step 4: After modifying the block in memory (marking the record as deleted), the block must be written back to the disk. However, the question asks for block accesses to find and delete. The dominant cost is finding the block, which is 1 access. The write-back is the second part of the operation. In GATE, "accesses required" typically refers to the read cost for retrieval. Even if we consider the read-then-write cycle, the initial search access is 1. For direct access operations, the cost is considered $O(1)$.

Result:
Under ideal conditions, only 1 block access is required.
Answer: \boxed{1}
"
:::

---

Summary

---

What's Next?

---

---

---

Part 2: Indexing

Introduction

In the management of large-scale relational databases, the efficiency of data retrieval is a paramount concern. Data is physically stored on secondary storage devices, such as hard disks, where access times are orders of magnitude slower than in main memory. A naive approach to locating a specific record would involve a linear scan of the entire table, an operation whose cost is proportional to the size of the data file. For tables containing millions or billions of records, such an approach is computationally infeasible for interactive applications.

To surmount this performance bottleneck, we employ a data structure known as an index. An index serves as an auxiliary structure that provides an efficient access path to data records, obviating the need for exhaustive table scans. Conceptually, it is analogous to the index found at the back of a textbook; instead of reading the entire book to find a topic, one consults the index to be directed to the relevant page number. Similarly, a database index allows the system to locate the disk block containing the desired record(s) with a minimal number of I/O operations. The strategic use of indexes is one of the most fundamental techniques in database performance tuning.

---

---

Key Concepts

1. Index Structure and Terminology

An index file is typically much smaller than the data file it indexes because it contains only the search key values and pointers. Let us establish the core components of an index.

• Search Key: This is the attribute or set of attributes of a relation that is used to look up records. The index is built upon the values of this search key.
• Data Pointer: A reference to the physical location of a record on disk. This pointer allows the database system to fetch the complete record after it has been located via the index.
• Index Entry: An index entry, or index record, is a pair `(k, p)` where `k` is a search key value and `p` is a pointer to one or more data records with that search key value.

The general structure involves an ordered index file containing these entries, which points to the unordered data file on disk.

Index File

101 | ptr

105 | ptr

210 | ptr

215 | ptr

300 | ptr

Data File (Disk Blocks)

[300, 'Alice', ...]

[101, 'Bob', ...]

[210, 'Charlie', ...]

[...other records...]

[105, 'David', ...]

[215, 'Eve', ...]

2. Clustered vs. Unclustered Indexes

The relationship between the index and the physical ordering of data on disk gives rise to a critical distinction.

Consider a relation sorted by its primary key, `ID`. An index on `ID` would be a clustered index. An additional index on a `Department` attribute would be an unclustered index, as the physical data is not sorted by department. Retrieving data via an unclustered index may require an extra disk I/O to fetch the data row after the pointer is found.

3. Indexing Data Structures: B+ Tree vs. Hash Index

The internal structure of an index dictates its performance characteristics and suitability for different types of queries. For the GATE examination, a firm understanding of B+ Trees and Hash Indexes is essential.

B+ Tree Index

The B+ Tree is a self-balancing tree data structure that maintains sorted data and allows for efficient insertion, deletion, and search operations. It is the most common and versatile index structure used in relational database systems.

Characteristics:
* Balanced Structure: All paths from the root to any leaf node have the same length. This guarantees that the worst-case lookup performance is logarithmic.
* Data Pointers at Leaves: All data pointers are stored exclusively at the leaf nodes.
* Sequential Linking: The leaf nodes are linked together in a doubly-linked list, which allows for efficient sequential processing and range queries.

Performance:
* Search, Insert, Delete: $O(\log_b N)$, where $N$ is the number of records and $b$ is the branching factor (fanout) of the tree.

Use Cases:
* Range Queries: Highly efficient for queries involving inequalities, such as `WHERE price > 1000` or `WHERE date BETWEEN '2023-01-01' AND '2023-03-31'`. The linked-list structure of the leaf nodes allows the system to find the start of the range and then simply traverse the leaves.
* Equality Queries: Also very efficient for point queries, such as `WHERE student_id = 54321`.
* Join Operations: B+ tree indexes on primary and foreign keys are fundamental for accelerating join performance.
* Ordered Retrieval: Queries with an `ORDER BY` clause can be satisfied directly by traversing the leaf nodes of the index, avoiding a costly sort operation.

Hash Index

A Hash Index organizes data based on the output of a hash function applied to the search key. The hash function maps search keys to a fixed-size array of "buckets."

Characteristics:
* Hash Function: Maps a search key to a bucket address.
* Buckets: Each bucket contains pointers to the data records whose search key hashes to that bucket.
* No Order Preservation: The hash function scrambles the input, so there is no inherent ordering of keys within the index.

Performance:
* Search, Insert, Delete: $O(1)$ on average, assuming a good hash function and minimal collisions. In the worst case (many collisions), performance can degrade.

Use Cases:
* Equality Queries: Extremely fast for point queries, such as `WHERE email = 'user@example.com'`. This is the primary strength of a hash index.

Limitations:
* Range Queries: A hash index is unsuitable for range queries. To find all records where `price > 1000`, the system would have to hash every possible price value greater than 1000, which is not feasible. There is no way to find a "starting point" and traverse.
* Ordered Retrieval: Cannot be used to speed up `ORDER BY` clauses.

The choice between these two structures is a classic trade-off based on the expected query patterns.

Worked Example:

Problem:
A database for an e-commerce platform has a `Products` table with attributes `ProductID` (PK), `ProductName`, `Category`, and `Price`. The two most frequent queries are:

`SELECT * FROM Products WHERE ProductID = 12345;`

`SELECT ProductName, Price FROM Products WHERE Price > 5000 ORDER BY Price;`

Propose an optimal indexing strategy for the `ProductID` and `Price` attributes.

Solution:

Step 1: Analyze Query 1.
This query is an equality search on the primary key `ProductID`.
`WHERE ProductID = 12345`

Both a Hash Index and a B+ Tree are highly effective for equality lookups. Since it is a primary key, most systems would default to a B+ Tree, which also provides ordering benefits. A Hash Index would provide marginally faster lookups but with less versatility.

Step 2: Analyze Query 2.
This query involves a range predicate and an ordering requirement.
`WHERE Price > 5000` (Range)
`ORDER BY Price` (Ordering)

A Hash Index cannot handle the range predicate `Price > 5000` efficiently. Furthermore, it cannot provide sorted output for the `ORDER BY` clause.

A B+ Tree is perfectly suited for this query. It can efficiently locate the first product with a price greater than 5000 and then traverse the linked leaf nodes to retrieve all subsequent products in sorted order, directly satisfying the `ORDER BY` requirement without a separate sort step.

Answer:

• For `ProductID`, a B+ Tree index is the standard and most versatile choice, although a Hash Index would also be very fast for the specific equality lookup.


• For `Price`, a B+ Tree index is mandatory to efficiently handle the range query and the `ORDER BY` clause.

---

Problem-Solving Strategies

When faced with a GATE question asking you to choose an indexing scheme to speed up a given SQL query, we recommend a systematic approach.

---

---

Common Mistakes

A correct understanding of indexing is crucial, but several common misconceptions can lead to incorrect answers in an exam setting.

---

Practice Questions

:::question type="MCQ" question="A library database has a `Books` table with attributes `ISBN` (primary key), `Title`, `Author`, and `PublicationYear`. A data analyst frequently runs the following query: `SELECT Title, Author FROM Books WHERE PublicationYear BETWEEN 2010 AND 2020;`. To optimize this specific query, what is the most appropriate index to create?" options=["A hash index on `PublicationYear`","A B+ tree index on `Title`","A B+ tree index on `PublicationYear`","A clustered index on `Author`"] answer="A B+ tree index on `PublicationYear`" hint="The query involves a range search on the `PublicationYear` attribute. Consider which index type is designed to handle range predicates efficiently." solution="Step 1: Analyze the query's `WHERE` clause. The condition is `PublicationYear BETWEEN 2010 AND 2020`.

Step 2: Classify the predicate. This is a range query, as it selects a continuous range of values.

Step 3: Evaluate the suitability of index types. A hash index is not suitable for range queries because it does not preserve the order of the keys. A B+ tree, however, is specifically designed for efficient range traversal due to its sorted structure and linked leaf nodes.

Step 4: Determine the correct attribute for the index. The query filters on `PublicationYear`, so the index must be created on this attribute to be effective. An index on `Title` or `Author` would not help with this `WHERE` clause.

Result: A B+ tree index on `PublicationYear` is the most appropriate choice. Answer: \boxed{A B+ tree index on `PublicationYear`} "
:::

:::question type="NAT" question="A table with 1,000,000 records is stored on disk. Without an index, a query to find a single record requires scanning, on average, half the data blocks. If the table occupies 10,000 disk blocks, this requires 5,000 block accesses. With a B+ tree index of height 3, a search requires traversing from the root to a leaf. How many disk block accesses are required to find the data pointer for a record using this B+ tree index (assuming each node is in a different block)?" answer="3" hint="The height of a B-tree or B+ tree corresponds to the number of disk accesses required to locate a leaf node, assuming the root is not cached in memory." solution="Step 1: Understand the B+ tree search process. A search starts at the root node and traverses down the tree to a leaf node.

Step 2: Relate tree height to disk accesses. The height of the tree is the number of levels. To reach a leaf node from the root in a tree of height $h$, we must access $h$ nodes.

Step 3: Apply the given information. The problem states the B+ tree has a height of 3. Assuming each node is stored in a separate disk block and no nodes are cached in memory, we must perform one disk access for the root, one for an intermediate node, and one for the leaf node.

Result: The number of disk block accesses required is equal to the height of the tree, which is 3. Answer: \boxed{3}"
:::

:::question type="MSQ" question="Consider the following SQL query on `Employee(ID, Name, Dept, Salary)` and `Department(DeptID, DeptName)` tables:
```sql
SELECT E.Name, D.DeptName
FROM Employee E JOIN Department D ON E.Dept = D.DeptID
WHERE E.Salary > 75000 AND D.DeptName = 'Research';
```
To maximize the performance of this query, on which of the following columns would a B+ tree index be beneficial? (Select ALL that apply)" options=["Employee.Salary","Employee.Dept","Department.DeptID","Department.DeptName"] answer="Employee.Salary,Employee.Dept,Department.DeptID,Department.DeptName" hint="Examine every predicate in the `WHERE` clause and every column used in the `JOIN` condition. Each of these is a candidate for indexing." solution="Analysis of each column:

• `Employee.Salary`: This column is used in a range predicate (`E.Salary > 75000`). A B+ tree index here is highly beneficial to quickly filter employees by salary without a full table scan. This option is correct.

• `Employee.Dept`: This column is used in the `JOIN` condition (`E.Dept = D.DeptID`). It is a foreign key. Indexing this column will significantly speed up the process of finding matching employees for a given department. This option is correct.

• `Department.DeptID`: This column is the primary key of the `Department` table and is used in the `JOIN` condition. Indexing a primary key is standard practice and essential for efficient joins. This option is correct.

• `Department.DeptName`: This column is used in an equality predicate (`D.DeptName = 'Research'`). A B+ tree index will allow the database to quickly find the `DeptID` for the 'Research' department, which can then be used in the join. This option is correct.

Conclusion: Indexes on all four columns would contribute to optimizing the query. The filters on `Salary` and `DeptName` reduce the initial data sets, and the indexes on `Dept` and `DeptID` accelerate the join between these reduced sets. Answer: \boxed{Employee.Salary,Employee.Dept,Department.DeptID,Department.DeptName}" :::

:::question type="MCQ" question="Which of the following operations is LEAST likely to be accelerated by a hash index on a column `X`?" options=["SELECT FROM T WHERE X = 100;","DELETE FROM T WHERE X = 200;","UPDATE T SET Y = 5 WHERE X = 300;","SELECT FROM T ORDER BY X;"] answer="SELECT * FROM T ORDER BY X;" hint="Recall the fundamental properties of a hash function. Does it preserve the order of the input keys?" solution="Step 1: Analyze the property of a hash index. A hash index uses a hash function to map keys to bucket locations. This process is designed for fast equality lookups but does not maintain any sort order of the keys.

Step 2: Evaluate each option.

• `SELECT ... WHERE X = 100;`: This is an equality search, the primary use case where a hash index provides excellent performance.


• `DELETE ... WHERE X = 200;`: To delete a row, the system must first find it. This involves an equality search on `X`, which is accelerated by the hash index.


• `UPDATE ... WHERE X = 300;`: Similar to `DELETE`, the system must first locate the row to be updated using the equality condition on `X`. The hash index speeds this up.


• `SELECT ... ORDER BY X;`: This query requires retrieving the data in the order of column `X`. Since the hash index does not store keys in any specific order, it cannot be used to satisfy the `ORDER BY` clause. The database would have to retrieve all the data and then perform a separate, costly sort operation.

Result: The `ORDER BY` operation is the one that receives no benefit from a hash index. Answer: \boxed{SELECT * FROM T ORDER BY X;}"
:::

---

Summary

---

What's Next?

---

Chapter Summary

---

Chapter Review Questions

:::question type="MCQ" question="A B+ tree is used to index a file. The tree conforms to the following specifications: Block size is 2048 bytes, search key size is 12 bytes, block pointer is 8 bytes, and record pointer is 10 bytes. What is the maximum number of records that can be indexed by a B+ tree of height 3?" options=["976,028", "997,516", "1,092,337", "954,800"] answer="976,028" hint="First, calculate the order (fanout) of an internal node and the capacity of a leaf node. The total capacity is the maximum number of leaf nodes multiplied by the records per leaf." solution="
Step 1: Calculate the order $p$ of an internal node.
An internal node stores $p$ block pointers and $p-1$ keys.

The maximum order (fanout) of an internal node is $p = 103$.

Step 2: Calculate the capacity $p_{leaf}$ of a leaf node.
A leaf node stores $p_{leaf}$ pairs of (key, record pointer) and one pointer to the next leaf.

The maximum number of records per leaf node is $p_{leaf} = 92$.

Step 3: Calculate the total capacity of the tree.
A B+ tree of height 3 has a root, one level of internal nodes, and one level of leaf nodes.

• The root can point to a maximum of $p$ children.


• Each of these children (internal nodes) can point to a maximum of $p$ leaf nodes.

Therefore, the maximum number of leaf nodes is $p \times p = p^2$.

The total number of indexable records is the number of leaf nodes multiplied by the capacity of each leaf node.

Thus, the maximum number of records that can be indexed is 976,028. Answer: \boxed{976,028}"
:::

:::question type="NAT" question="A data file contains 200,000 records. A B+ tree secondary index is built on a non-key field. The file system uses a block size of 4096 bytes. The index has the following parameters: search key size is 15 bytes, record pointer is 9 bytes, and block pointer is 6 bytes. It is known that any given search key value appears in 20 different records. Assuming the data records are not clustered by the search key, calculate the total number of block accesses required in the worst case to retrieve all records for a specific search key value." answer="24" hint="The total block accesses will be the sum of accesses to traverse the index tree to the leaf node, plus any additional leaf node accesses, plus the accesses to retrieve the data records from the file." solution="
This problem requires us to calculate the I/O cost for a query using a secondary B+ tree index. The total cost is the sum of traversing the index and fetching the data records.

Step 1: Calculate the order $p$ of an internal node.

The order of an internal node is $p = 195$.

Step 2: Calculate the capacity $p_{leaf}$ of a leaf node.
Since this is a secondary index, it must be dense. Each leaf node entry consists of a key and a record pointer.

The capacity of a leaf node is $p_{leaf} = 170$ index entries.

Step 3: Calculate the height $h$ of the B+ tree.
The number of leaf nodes required is $\lceil \frac{\text{Total Records}}{p_{leaf}} \rceil$.

The height $h$ is the smallest integer such that $p^{h-1} \ge \text{Number of Leaf Nodes}$.

• If $h=1$: The tree has only one node (a leaf). Max capacity is 170. Not enough.


• If $h=2$: Max leaf nodes = $p = 195$. Not enough.


• If $h=3$: Max leaf nodes = $p^2 = 195^2 = 38,025$. This is sufficient.

So, the height of the tree is $h=3$.

Step 4: Calculate the total block accesses.
The query is to retrieve all 20 records matching a specific key.

• Index Traversal Cost: To find the first matching entry, we must traverse the tree from the root to the leaf. This requires $h$ block accesses. Cost = 3.


• Leaf Node Access Cost: The 20 matching index entries will fit within a single leaf node (since $p_{leaf} = 170$). So, only 1 block access is needed for the leaf node itself after traversal. Cost = 1.


• Data Record Fetch Cost: The index is on a non-key, unclustered attribute. Therefore, the 20 matching records could reside in 20 different data blocks. In the worst case, this requires 20 separate block accesses to the data file. Cost = 20.

Total Block Accesses = Index Traversal Cost + Leaf Node Access Cost + Data Record Fetch Cost = $3 + 1 + 20 = 24$. Answer: \boxed{24}"
:::

:::question type="MSQ" question="Which of the following statements about physical database organization are correct?" options=["A clustering index on a non-key attribute must be a dense index.", "In a B+ Tree, deleting a record may cause a merge operation that propagates all the way to the root, reducing the tree's height.", "For a data file sorted on an attribute `A`, a sparse primary index on `A` offers lower storage overhead than a dense secondary index on another attribute `B`.", "In extendible hashing, a bucket split operation always doubles the size of the global directory."] answer="B,C" hint="Evaluate each statement based on the precise definitions of index types, B+ Tree maintenance operations, and dynamic hashing schemes." solution="
Let us analyze each statement:

• A. A clustering index on a non-key attribute must be a dense index.

This is incorrect. A clustering index, by definition, is built on the ordering attribute of a data file. Since the file is sorted on this attribute, we only need to store one index entry per data block, pointing to the first record in that block. Therefore, a clustering index is sparse.

• B. In a B+ Tree, deleting a record may cause a merge operation that propagates all the way to the root, reducing the tree's height.

This is correct. When a record is deleted, the corresponding node may underflow (i.e., have fewer than the minimum required entries). This underflow is handled by borrowing from a sibling or merging with a sibling. If a merge occurs, it removes a node, which is equivalent to deleting an entry from the parent node. This deletion can cause the parent to underflow, and this process can propagate up the tree. If the root's children are merged, the root itself may be deleted, thereby reducing the overall height of the tree by one.

• C. For a data file sorted on an attribute `A`, a sparse primary index on `A` offers lower storage overhead than a dense secondary index on another attribute `B`.

This is correct. A sparse primary index on `A` stores one entry (key + pointer) for each data block. A dense secondary index on `B` must store one entry for each data record. Since the number of records is typically much larger than the number of blocks they occupy (i.e., the blocking factor is greater than 1), the dense index will have significantly more entries and thus a higher storage overhead.

• D. In extendible hashing, a bucket split operation always doubles the size of the global directory.

This is incorrect. The global directory only doubles in size when a bucket splits whose local depth has become equal to the global depth. If a bucket splits whose local depth is less than the global depth, the directory size does not change; instead, pointers in the directory are simply adjusted to point to the new bucket.

Therefore, the correct statements are B and C. Answer: \boxed{B,C}"
:::

:::question type="MCQ" question="Consider a relation stored as a sequential (sorted) file on its primary key. Which of the following operations is the most computationally expensive in terms of average-case I/O cost?" options=["Retrieving a specific record based on its primary key.", "Performing a range query (e.g., finding all records between two primary key values).", "Inserting a new record into the file.", "Deleting an existing record from the file."] answer="C" hint="Think about how the sorted order of the file must be maintained for each operation and what that implies for reading and writing data blocks." solution="
Let us analyze the I/O cost of each operation for a sequential file sorted on its primary key. Let the file have $B$ blocks.

• A. Retrieving a specific record based on its primary key.

Since the file is sorted, we can use binary search on the blocks to locate the correct block containing the record. The I/O cost for this is $O(\log_2 B)$. This is very efficient.

• B. Performing a range query.

This involves first finding the starting record of the range, which takes $O(\log_2 B)$ using binary search. Then, we sequentially scan and retrieve all subsequent blocks that contain records within the range. This is also very efficient, as all relevant records are physically contiguous.

• C. Inserting a new record into the file.

To insert a new record, we must first find the correct position to maintain the sort order. This takes $O(\log_2 B)$ I/O. However, once the position is found, we must shift all subsequent records to make space for the new one. In the average case, this requires reading and re-writing half of the file's blocks. The I/O cost is therefore proportional to $B$, making it an $O(B)$ operation.

• D. Deleting an existing record from the file.

Similar to insertion, deletion requires finding the record ($O(\log_2 B)$) and then either marking it for deletion (logically) or physically removing it and compacting the file by shifting subsequent records. Physical deletion is an $O(B)$ operation, just like insertion. However, logical deletion is often preferred, which is much cheaper but introduces its own complexities. In the context of maintaining a purely sequential file, both insertion and physical deletion are $O(B)$. Insertion is often considered slightly more complex as it always requires shifting, whereas deletion can sometimes be handled with markers. Between the two, insertion's need to create space makes it fundamentally expensive.

Comparing the complexities, $O(B)$ is significantly more expensive than $O(\log_2 B)$. Both insertion and physical deletion have this high cost, but they represent the most expensive class of operations. The question asks for the most expensive, and insertion is a canonical example of this high cost. Answer: \boxed{C}"
:::

---

What's Next?