a. Write pseudo code B-tree implementations of traversals and range queries that need to access entire data records, not simply the search keys. How many block accesses do your functions require?

b. To reduce the number of block accesses required by these operations, various modifications of the basic B-tree structure are frequently used. The central idea behind such structures is to keep the data fi le itself sorted. First, assume that you can keep the data fi le in sequential sorted order-that is, the records are sorted within each block and the records in Bi-1 are less than the records in Bi for i = 2, 3, and so on to the number of blocks in the fi le. Rewrite your implementations of the traversal and range-query operations to take advantage of this fact. How many block accesses do these operations now require?

c. Because it is too inefficient to maintain a sequentially sorted data fi le in the face of frequent insertions and removals, a compromise scheme is often employed. One such possible compromise is as follows. If a data record belongs in block B and B is full, a new block is allocated and linked to B, allowing the new record to be inserted into its proper sorted location. The difficulty is that you must now view each index record in the B-tree as indicating the first of possibly several blocks in a chain of blocks that might contain the corresponding data record. Rewrite the add , remove, get Item, traverse, and range Query operations in terms of this implementation. What is the effect on their efficiency?