We compare the speed of searching a B-tree with a standard binary search tree (BST). If...

   

Transcribed Image Text:

We compare the speed of searching a B-tree with a standard binary search tree (BST). If there are n keys, let TBfree (n) and TBST(n) denote their worst case search times. We write TBST(n) = lgn, measured in some idealized time unit. NOTE: each time unit is less than e machine cycles for some moderate constant c> 1 (most likely, c < 40). A B-tree with n leaves has height at most loggn for some constant B2 2. Each internal node is stored in a disc block, and assume that the time to read or write a disc block is 1000 time units. In the search algorithm, assume that we read and write one disc block per level. Moreover, assume that it takes lg B time units to find the correct child in the next level of the search. (a) Write an expression for TBtree(n). (b) What is TBtree (nº) when n = 10° is 1 billion, and B = 500? Use the "Computer Science approximation of "Ig", e.g., Ig 1000 = 10, and lg 10º = 30. (c) Comparing TBST (n) and TBtree (n), my student Sharp exclaimed: we should NEVER use B-trees! If Mr.Sharp right, then it is a paradox to say that B-trees are very important! Explain this paradox. We compare the speed of searching a B-tree with a standard binary search tree (BST). If there are n keys, let TBfree (n) and TBST(n) denote their worst case search times. We write TBST(n) = lgn, measured in some idealized time unit. NOTE: each time unit is less than e machine cycles for some moderate constant c> 1 (most likely, c < 40). A B-tree with n leaves has height at most loggn for some constant B2 2. Each internal node is stored in a disc block, and assume that the time to read or write a disc block is 1000 time units. In the search algorithm, assume that we read and write one disc block per level. Moreover, assume that it takes lg B time units to find the correct child in the next level of the search. (a) Write an expression for TBtree(n). (b) What is TBtree (nº) when n = 10° is 1 billion, and B = 500? Use the "Computer Science approximation of "lg", e.g., Ig 1000 = 10, and lg 10⁰ = 30. (c) Comparing TBST (n) and TBtree (n), my student Sharp exclaimed: we should NEVER use B-trees! If Mr.Sharp right, then it is a paradox to say that B-trees are very important! Explain this paradox. We compare the speed of searching a B-tree with a standard binary search tree (BST). If there are n keys, let TBfree (n) and TBST(n) denote their worst case search times. We write TBST(n) = lgn, measured in some idealized time unit. NOTE: each time unit is less than e machine cycles for some moderate constant c> 1 (most likely, c < 40). A B-tree with n leaves has height at most loggn for some constant B2 2. Each internal node is stored in a disc block, and assume that the time to read or write a disc block is 1000 time units. In the search algorithm, assume that we read and write one disc block per level. Moreover, assume that it takes lg B time units to find the correct child in the next level of the search. (a) Write an expression for TBtree(n). (b) What is TBtree (nº) when n = 10° is 1 billion, and B = 500? Use the "Computer Science approximation of "Ig", e.g., Ig 1000 = 10, and lg 10º = 30. (c) Comparing TBST (n) and TBtree (n), my student Sharp exclaimed: we should NEVER use B-trees! If Mr.Sharp right, then it is a paradox to say that B-trees are very important! Explain this paradox. We compare the speed of searching a B-tree with a standard binary search tree (BST). If there are n keys, let TBfree (n) and TBST(n) denote their worst case search times. We write TBST(n) = lgn, measured in some idealized time unit. NOTE: each time unit is less than e machine cycles for some moderate constant c> 1 (most likely, c < 40). A B-tree with n leaves has height at most loggn for some constant B2 2. Each internal node is stored in a disc block, and assume that the time to read or write a disc block is 1000 time units. In the search algorithm, assume that we read and write one disc block per level. Moreover, assume that it takes lg B time units to find the correct child in the next level of the search. (a) Write an expression for TBtree(n). (b) What is TBtree (nº) when n = 10° is 1 billion, and B = 500? Use the "Computer Science approximation of "lg", e.g., Ig 1000 = 10, and lg 10⁰ = 30. (c) Comparing TBST (n) and TBtree (n), my student Sharp exclaimed: we should NEVER use B-trees! If Mr.Sharp right, then it is a paradox to say that B-trees are very important! Explain this paradox.

Answer rating: 100% (QA)

On the basis of the result one can say that we should never use the Btree But what will that person ... View the full answer