Algorithm 17.1 outlines the procedure for searching a nondense multilevel primary index to retrieve a file record.

Question:

Algorithm 17.1 outlines the procedure for searching a nondense multilevel primary index to retrieve a file record. Adapt the algorithm for each of the following cases:

a. A multilevel secondary index on a nonkey nonordering field of a file.

Assume that option 3 of Section 17.1.3 is used, where an extra level of indirection stores pointers to the individual records with the corresponding index field value.

b. A multilevel secondary index on a nonordering key field of a file.

c. A multilevel clustering index on a nonkey ordering field of a file.

Algorithm 17.1. Searching a Nondense Multilevel Primary Index with t Levels

(*We assume the index entry to be a block anchor that is the first key per block*)
p ← address of top-level block of index;
for j ← t step − 1 to 1 do
begin
read the index block (at jth index level) whose address is p;
search block p for entry i such that Kj (i) ≤ K < Kj(i + 1)
(* if Kj(i) is the last entry in the block, it is sufficient to satisfy Kj(i) ≤ K *);
p ← Pj(i ) (* picks appropriate pointer at jth index level *)
end;
read the data file block whose address is p;
search block p for record with key = K;

Fantastic news! We've located the answer you've been seeking!

Step by Step Answer:

Related Book For  answer-question

Fundamentals Of Database Systems

ISBN: 9780133970777

7th Edition

Authors: Ramez Elmasri, Shamkant Navathe

Question Posted: