4: Indexes and Trees

Question 1

What do indexes do?

Answer 1

They enhance the operational speed of queries, especially when there are very large numbers of tuples involved.

Question 2

Why can the selection of an appropriate index enhance or reduce the performance of the DB ?

Answer 2

Because relations - stored over many pages - have to be bought to the main memory, and the cost of querying and modifying is significant.

Furthermore, the index itself has to be stored and updated appropriately with the relation.

Question 3

What types of index are available ?

Answer 3

• Clustering index
• Hash index
• Multi-level index
• B-Tree
• B+Tree

Question 4

Which indexes are the most commonly used and why?

Answer 4

B+/-Trees, as they are the most cost-efficient in terms of the number of I/O operations they use, and are pretty straightforward to modify.

Question 5

What’s the key difference between B+ and B- Tree?

Answer 5

B-Tree can point to records at any level in the tree.

B+ points to records from its leaf nodes (more efficient).

Question 6

What is a ‘balanced’ tree?

Answer 6

All paths from root to leaf node are the same length and have few I/Os, and therefore have a low cost.

Question 7

How many additional index levels can speed up query processing, before B+tree is preferable?

Answer 7

Only one or two, as I/O costs may increase as extra levels are added in a multi-level environment.

Question 8

What is a clustering index?

Answer 8

The index is ordered on a non-key field.

The records in the file may be physically ordered on a non-key field that does not have distinct values (not a primary nor candidate key).

This key is called a ‘clustering field’.

Question 9

How is a clustering index ordered?

Answer 9

It’s an ordered file with 2 fields:

• A field with the same type as the clustering field on file
• A field with a pointer to the record with that clustering field.

Question 10

If your search for a record that requires the use of more than one index – identify the index-type in use ?

Answer 10

Multi-level

Question 11

The B-tree (and B+-tree) structure can be identified as having three levels:

• Root Level
• Intermediate Level
• Leaf Level.

If the record you are searching for is pointed to from an intermediate node, which type of tree is being used?

Answer 11

B-Tree

Question 12

If the relation is ordered on a non-key field (that has duplicate values allowed), which index type is usually associated with this implementation?

Answer 12

Clustering