Pré-visualização3 páginas

bytes/record divided by 2400 bytes/block = 10000 blocks. Time for exhaustive read = s + r + b.btt = 16 + 8.3 + (10000) * 0.8 = 8024.3 msec Let X be the # of records searched randomly that takes more time than exhaustive read time. Hence, X (s + r + btt) > 8024.3 X (16+8.3+0.8) > 8024.3 X > 8024.3/25.1 Thus, X > 319.69 i.e. If at least 320 random reads are to be made, it is better to search the file exhaustively. 13.40 Suppose that a static hash file initially has 600 buckets in the primary area and that records are inserted that create an overflow area of 600 buckets. If we reorganize the hash file, we can assume that the overflow is eliminated. If the cost of reorganizing the file is the cost of the bucket transfers (reading and writing al of the buckets) and the only periodic file operation is the fetch operation, then how many times would we have to perform a fetch (successfully) to make the reorganization cost-effective? That is, the reorganization cost and subsequent search cost are less than the search cost before reorganization. Assume s=16, rd=8.3 ms, btt=1 ms. Primary Area = 600 buckets Secondary Area (Overflow) = 600 buckets Total reorganization cost = Buckets Read & Buckets Written for (600 & 600) + 1200 = 2400 buckets = 2400 (1 ms) = 2400 ms Let X = number of random fetches from the file. Average Search time per fetch = time to access (1 + 1/2) buckets where 50% of time we need to access the overflow bucket. Access time for one bucket access = (S + r + btt) = 16 + 8.3 + 0-8 = 25.1 ms Time with reorganization for the X fetches = 2400 + X (25.1) ms Time without reorganization for X fetches = X (25.1) (1 + 1/2) ms = 1.5 * X * (25.1) ms. Hence, 2400 + X (25.1) < (25.1) * (1.5X) 2374.9/ 12.55 < X Hence, 189.23 < X If we make at least 190 fetches, the reorganization is worthwhile. 13.41 Suppose we want to create a linear hash file with a file load factor of 0.7 and a blocking factor of 20 records per bucket, which is to contain 112000 records initially. (a) How many buckets should we allocate in primary areas? (b) What should be the number of bits used for bucket addresses? Answer: (a) No. of buckets in primary area. = 112000/(20*0.7) = 8000. (b) K: the number of bits used for bucket addresses 2K < = 8000 < = 2 k+1 2 12 = 4096 2 13 = 8192 K = 12 Boundary Value = 8000 - 2 12 = 8000 - 4096 = 3904 - �PAGE � Copyright © 2007 Pearson Education, Inc. Publishing as Pearson Addison-Wesley.