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;