Physical Database Design - High-Performance Web Databases: Design, Development, and Deployment - page 345

Exhibit 21-10. Hashing search keys. ( continued )

Rather than using a function to calculate the data page
address, a tree index can be used to map a value of a search key to a data
page. The tree index does not require a linking table if the search key is the
primary search key used to order the file. However, a linking table is
required if the file is a heap or hashed file, or if the secondary search key is
different from the primary search key used to sort the file.

Tree Index.

The choice between using a hashed or tree index
is determined by the number of matching requests as compared to the
number of range requests. For example, consider Queries 4 and 5 from the
workload in Exhibit 3:

Hashed or Tree Index.

• Query 4: Select * from Department where Budget = 500,000
• Query 5: Select * from Department where 100,000 < Budget and Budget
< 500,000