Indexing

Question 1

What is a search key?

Answer 1

Attribute or set of attributes used to look up records in a file.

Question 2

What is the structure of an index entry?

Answer 2

search-key | Pointer

Question 3

What factors have to be taken into account in index design?

Answer 3

• Access types
• Access time
• Insertion time
• Deletion time

Question 4

What is a primary index

Answer 4

index whose search-key specifies the order of records in the data file, usually the primary key

Question 5

What is a secondary indice?

Answer 5

Index that allows search order different from sequential order of file.

Question 6

What is a dense index?

Answer 6

Index records appears for every search-key value in the file.

Question 7

What is a sparse index?

Answer 7

Index records only stored for some of the key values. Find record with key <= K and scan sequentially from that record.

Question 8

What are the efficiency concerns when using indexing?

Answer 8

Advantages: Dense gives faster lookups, sparse takes less space and requires less maintenance.

Question 9

What’s a good compromise between sparse and dense indexing?

Answer 9

Sparse index with an index record for every disk block.

Index corresponds to least key value in block.

Question 10

How does multi-level indexing work?

Answer 10

Outer index: Sparse index of primary index

Inner index: The primary index file.