The total cost of retrieving records in sorted order using an unclustered B+ tree is (P-Average number of records per data page N-Data pages F-Ratio of the size of a data entry to the size of a data record)
(F + P) * N
Understanding Retrieval Cost with Unclustered B+ Trees
The question asks for the total cost of retrieving records in sorted order when using an unclustered B+ tree. This scenario involves accessing data records based on the order provided by the index entries in the B+ tree leaves.
Let's define the given parameters:
- P: Average number of records per data page.
- N: Total number of data pages storing the actual records.
- F: Ratio of the size of a data entry (in the index) to the size of a data record. \( \text{Size(Data Entry)} / \text{Size(Data Record)} = F \)
Retrieving records in sorted order using an unclustered B+ tree involves two main steps regarding disk I/O:
- Reading the data entries from the leaf pages of the B+ tree in sorted order.
- Retrieving the actual data records from the data pages using the pointers obtained from the data entries.
Cost of Reading Index Leaf Pages
The B+ tree leaf level contains data entries for all records. We need to scan these leaf pages sequentially to get the pointers to the records in sorted order.
Let's determine the number of leaf pages:
- Total number of data records = \( N \times P \) (assuming data pages are filled to capacity on average).
- Each data record has a corresponding data entry in the index. So, total number of data entries = \( N \times P \).
- The number of records that fit into a data page is P. This means \( \text{Page Size} / \text{Size(Data Record)} = P \).
- The number of data entries that fit into an index page is \( \text{Page Size} / \text{Size(Data Entry)} \).
- Since \( \text{Size(Data Entry)} = F \times \text{Size(Data Record)} \), the number of entries per index page is \( \text{Page Size} / (F \times \text{Size(Data Record)}) = (\text{Page Size} / \text{Size(Data Record)}) / F = P/F \).
- The total number of leaf pages in the index is (Total number of entries) / (Entries per page) = \( \frac{N \times P}{P/F} = N \times F \).
Reading these \( N \times F \) leaf pages sequentially typically costs approximately \( N \times F \) disk I/Os.
Cost of Reading Data Records
After reading the data entries from the index leaves, we have the pointers to the \( N \times P \) data records in the required sorted order. Since the index is unclustered, the physical location of these records on disk does not follow the index order. Retrieving them according to the sorted order of the index entries usually results in random disk I/Os.
There are a total of \( N \times P \) records to retrieve. In the worst case for an unclustered index, fetching each record might require a separate random disk I/O. However, considering we are retrieving *all* records that are spread across \( N \) data pages, a more typical measure for accessing all data records via an unclustered index is related to the total number of records or the number of data pages involved.
Let's look at the structure of the correct option \( (F + P) \times N = (F \times N) + (P \times N) \). We've identified that \(F \times N\) corresponds to the index leaf read cost.
The term \(P \times N\) is the total number of records. In the context of disk I/O cost, accessing \(P \times N\) distinct records via random I/Os would indeed cost \(P \times N\) I/Os in the worst case (where each record is on a different page or accessed in an order that requires reading a new page each time).
So, the cost of reading data records is approximately \( N \times P \) I/Os.
Total Cost Calculation
The total cost is the sum of the cost of reading the index leaf pages and the cost of reading the data records:
Total Cost = Cost (Index Leaves) + Cost (Data Records)
Total Cost = \( (N \times F) + (N \times P) \)
Total Cost = \( (F + P) \times N \)
This matches option 2.
| Component | Calculation | Cost (I/Os) |
|---|---|---|
| Number of Data Records | \( N \times P \) | - |
| Number of Entries per Index Page | \( P/F \) | - |
| Number of Index Leaf Pages | \( (N \times P) / (P/F) \) | \( N \times F \) |
| Cost to Read Index Leaves (Sequential) | \( N \times F \) pages | \( N \times F \) |
| Cost to Read Data Records (Random via Unclustered Index) | \( N \times P \) records | \( N \times P \) |
| Total Cost | Sum of component costs | \( (N \times F) + (N \times P) = (F + P) \times N \) |
Therefore, the total cost of retrieving records in sorted order using an unclustered B+ tree, considering the cost of scanning index leaves and fetching individual data records, is \( (F + P) \times N \).
Revision Table: Unclustered B+ Tree Retrieval Cost
| Term | Definition | Role in Cost Calculation |
|---|---|---|
| P | Avg. records per data page | Used with N to find total records (\(N \times P\)) and in number of entries/page (\(P/F\)). Contributes to data record retrieval cost \(N \times P\). |
| N | Total data pages | Indicates scale of data. Multiplier for both index leaf cost (\(F \times N\)) and data record cost (\(P \times N\)). |
| F | Size(Entry)/Size(Record) | Relates data size to index entry size. Determines number of index leaf pages (\(N \times F\)). Contributes to index leaf read cost \(F \times N\). |
| \(N \times F\) | Number of index leaf pages | Cost of sequentially reading all index leaf pages. |
| \(N \times P\) | Total number of data records | Worst-case cost of randomly accessing all data records via the index. |
| \((F+P) \times N\) | Total Cost | Sum of index leaf read cost and data record read cost. |
Additional Information: Clustered vs. Unclustered Index Cost
It's helpful to compare this to a clustered B+ tree for sorted retrieval. In a clustered index, the data records themselves are stored in the sorted order of the index key. The leaf level of a clustered B+ tree often contains the actual data records, or pointers to contiguous blocks of data records.
- Clustered Index Cost for Sorted Retrieval: You would traverse the tree to the first leaf (logarithmic cost) and then scan the leaf pages sequentially. Since the leaf pages contain the data records in sorted order and are physically contiguous or close, reading all records only requires reading the data pages containing them. The number of such data pages is simply N. The cost is roughly the cost of traversing the tree + N I/Os for sequential scan of data pages. This is significantly cheaper than the unclustered case for retrieving large portions of the data in sorted order.
- Unclustered Index Cost for Sorted Retrieval: As calculated, this involves scanning index leaves (\(N \times F\)) and then fetching data records (\(N \times P\)), leading to a total cost of \( (F+P) \times N \). This cost is higher because accessing data records via pointers often incurs random I/Os.
This difference highlights why a clustered index is often preferred when range queries or sorted retrieval based on the index key are frequent operations accessing a significant portion of the data.
Important Questions from Indexing
Primary index in sequential order file organisation is also known as ______.
A B-tree used as an index for a large database table has four levels including the root node. If a new key is inserted in this index, then maximum number of nodes that could be newly created in the process is
- In a relational database, a B+ Tree Index is to be constructed for a relation on a key field. In a B+ Tree, a Node Pointer points to a sub-tree and a Data Record Pointer points to a block of database records.
Let, Node size = 4096 bytes, Node Pointer size = 10 bytes, Search Key Field size = 11 bytes and Data Record Pointer size = 12 bytes.
The maximum number of Node Pointers that can be present in a non-leaf node of the B+ Tree is ________ . (Answer in integer) Consider a B+ Tree where the maximum number of key values in each leaf node is 2 and the maximum number of pointers in each non-leaf node is 3. Let the content of the B+ Tree be as shown in the figure.
Which of the following options denotes the key value(s) stored in the root node after inserting a key value 3 in the given B+ Tree?
An OTT company is maintaining a large disk-based relational database of different movies with the following schema:
Movie(ID, CustomerRating)
Genre(ID, Name)
Movie_Genre(MovieID, GenreID)
Consider the following SQL query on the relation database above:
SELECT *
FROM Movie, Genre, Movie_Genre
WHERE
Movie.CustomerRating > 3.4 AND
Genre.Name = “Comedy” AND
Movie_Genre.MovieID = Movie.ID AND
Movie_Genre.GenreID = Genre.ID;
This SQL query can be sped up using which of the following indexing options?
