CH 17 - Indexing Structures for Files and Physical Database Design

Question 1

indexing field

Answer 1

For a file with a given record structure consisting of several fields (or attributes), an index access structure is usually defined on a single field of a file, called an indexing field (or indexing attribute).1 The index typically stores each value of the index field along with a list of pointers to all disk blocks that contain records with that field value.

Question 2

17.3. Why can we have at most one primary or clustering index on a file, but several secondary indexes?

Answer 2

. Notice that a file can have at most one physical ordering field, so it can have at most one primary index or one clustering index,

Question 3

primary key field

Answer 3

The first field is of the same data type as the ordering key field—called the primary key—of the data file, and the second field is a pointer to a disk block (a block address
- Each index entry has the value of the primary key field for the first record in a block

Question 4

block anchor

Answer 4

The first record in each block of the data file is called the anchor record of the block, or simply the block anchor.2

Question 5

dense index

Answer 5

A dense index has an index entry for every search key value (and hence every record) in the data file.

Question 6

nondense (sparse) index.

Answer 6

A sparse (or nondense) index, on the other hand, has index entries for only some of the search values

Question 7

17.2. What are the differences among primary, secondary, and clustering indexes? How do these differences affect the ways in which these indexes are imple- mented? Which of the indexes are dense, and which are not?

Answer 7

• A primary index is specified on the ordering key field of an ordered file of records. A clustering index the ordering field is not a key field—that is, if numerous records in the file can have the same value for the ordering field. secondary index, can be specified on any nonordering field of a file, may be a key or not.
• Just one primary or cluster index. 0 or more secondary indexes
• secondary index access structure on a key. contains the value of the field for the record and a pointer either to the block in which the record is stored or to the record itself. Hence, such an index is dense.
• A clustering index is another example of a nondense index. Primary also.

Question 8

binary search

Answer 8

log2 b

b blocks

Question 9

linear search

Answer 9

b/2

b blocks

Question 10

clustering field

Answer 10

If file records are physically ordered on a nonkey field—which does not have a dis- tinct value for each record—that field is called the clustering field

Question 11

secondary key field

Answer 11

The first field is of the same data type as some nonordering field of the data file that is an indexing field.