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

Exhibit 21-7. Hashed file.

depth is increased with every leaf of the B+ tree guaranteed to be the same
distance from the root of the tree.

A hashed file enables access to any record given the value
of its search key. In Exhibit 7, there are

Hashed File.

pages in which data records can
be stored. By performing a transformation — often called a hashing func-
tion — on the value of the search key, a page number is generated where
the page number is in the range [0,

N

- 1]. When the user inserts a record,
it is stored in the page with the generated page number. When the user
retrieves a record, the records stored in the page with the generated page
number are retrieved.

N

Hashed files are efficient when retrieving records that match the selec-
tion criteria exactly. For example, consider the SQL request:

Select * from Department where DeptName = “Accounting”

Applying the hashing function to the value for “Accounting” would gener-
ate the page number for the data page containing the record for the depart-
ment with DeptName = “Accounting,” which would be retrieved quickly.
Unfortunately, hashed files do not lend themselves to range searches, such
as Query 5.

While a table may have
multiple search keys, the primary search key is used to determine the file
structure for the table. To choose a file structure for each table in a rela-
tional database, the DBA performs the following calculations: For each
table in the relational database, examine the workload for queries and
transactions that access the table. Let:

Choosing Primary Search Keys and File Structures.

• HEAP be the sum of the weights associated with queries and transac-
tions that scan the entire table.