Index Question

[K S]

Hi, tutors

I have 2 Questions about Index:

Q1

Why if a key is given it would be faster half of time ? why we just need to check half of pages? I see no difference whether the selection is key or not because we regard a record as a smallest unit.

Q2

 

Why hashed files cost more 0.25 than unsorted files (or heap files) ?   how to figure out this additional 0.25 cost, which process consume it ?

[Yu Hao]

Hi,

In my view, when given only one specified key, on average, it will be half of the time. For example, given N blocks that we will check one by one (a linear search), if a key in the first block the time cost is 1, and if the key the last block it will be N. On average, the cost is N/2. But if there are multiple keys, on average we might check all the blocks, thus it is B(D+RC).

1.25 is from:

  80% page occupancy => File size = 1.25 data size

Cheers,

Yu