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 K_j (i) ≤ K < K_j(i + 1)
(* if K_j(i) is the last entry in the block, it is sufficient to satisfy K_j(i) ≤ K *);
p ← P_j(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;