Assume a table has 100,000 rows and each row occupies 100 bytes. Disk pages are 4000 bytes and the worst case time to access a page is 20ms. Estimate the worst case time of doing an equality search on a candidate key under the following conditions
(a) An (unsorted) heap file with no index.
(b) An unclustered B+ tree in which each entry occupies 20 bytes.
(c) A clustered B+ tree.
(a) An (unsorted) heap file with no index.
Solution:
size of file = (105 ? 102)/(4 ? 103) = 2500 pages worst case time = 2500 ? 20ms = 50 sec
(b) An unclustered B+ tree in which each entry occupies 20 bytes.
Solution:
max. number of entries in a page = (4?103)/20 = 200
min. number of entries in a page = 100 (worst case)
tree must have 105 entries, hence a 3 level tree is required
3 I/O operations to search tree + 1 I/O operation to fetch row = 4 I/O ops 4 ? 20ms per I/O operation = 80 ms
(c) A clustered B+ tree.
Solution:
100 separator entries per page (worst case) 4000/100 = 40 rows per page max at leaf level 20 rows per page at leaf level (worst case)
leaf level has 100,000/20 = 5000 pages (worst case)
total number I/O operations = 2 (to search separator levels) + 1 (to get index page) cost = 60 ms
You might also like to view...
The printer that is automatically selected if you do not choose a specific printer is the ________ printer
Fill in the blank(s) with correct word
Linux uses files to represent ________.
a) named sets of data b) hardware devices c) shared memory regions d) all of the above
Choose the sentence that demonstrates correct punctuation.?
A. ?"September 11, 2001," a book written by a firefighter, is on the bestsellers list. B. ?September 11, 2001, a book written by a firefighter, is on the bestsellers list. C. ?September 11, 2001, a book written by a firefighter, is on the bestsellers list.
The ___________________ is a fixed, predetermined number that defines the function or session type.
Fill in the blank(s) with the appropriate word(s).