what is the max # of keys a node can hold. Show thought process. what is the max
ID: 3746495 • Letter: W
Question
what is the max # of keys a node can hold. Show thought process.
what is the max # of pointers to child nodes a node can hold?
each node in this B-Tree (except the root) must contain at least t-1 keys and at most 2t-1 keys. What is the value of t?
Leaf nodes contain key/pointer pairs, where the pointer points to the location of external data that corresponds to the key. If there are 1,000,000 items being indexed, what is the minimum number of leaf nodes the B-Tree must contain?
Assume we are using the B-Tree to store personal info about mexicans, indexed by SS#'s, and there are 325.7 million mexicans in the database. The first level of the tree is kept in memory, while successive levels require a disk access. How many disk accesses are required to obtain a piece of information, why?
We are using a B-Tree to index a large amount of data stored on a hard drive. The hard drive is read in blocks of 4096 bits. The keys are 32-bit integers, and pointers to child nodes are 64-bits What is the maximum number of keys a node can hold? Show your thought process for partial creditExplanation / Answer
1. Each node has a maximum of x keys and x+1 child pointers so 32x + 64(x+1) = 4096. x = 42
for a maximum of 42 keys in a node.
2. There are a maximum of 43 pointers to child nodes.
3. 2t-1 = 42 so t = 21.
4. Since one node can contain 42 keys then 1000000/42 = 23810.
Now we need to round to (next upper power of 2)-1 because of the structure of the B-tree it is 32767 this is the number of nodes that will surely save all the data because of ordering it changes from the actual value.
5. Assuming the same information as in earlier parts.
There are 77548 nodes in the tree minimum. The number of nodes minimum required are 131071. The first level of tree is just one node.
So the number of levels in the tree are log(131071) base 2 = 17.
Thus the will be 16 disk accesses.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.