edited by
596 views
2 votes
2 votes

Which of these statements is not true about a b-Tree $T$ with height $h$ and $n$ nodes, assuming that each node takes exactly $1$ $disk$ operation to read?

  1.  Finding a node in $T$ cannot require more than $O\left ( h \right )$ disk operations (in other words, $O\left ( h \right )$ time, if only disk reads and writes are counted).
  2. $h$ cannot exceed $\log t \left ( \left ( n+1 \right )/2 \right )$, where $t$ is the minimum node degree.
  3. If each node in $T$ is augmented with an integer showing the size of that node’s sub-tree, then $n$ additional nodes can be inserted into $T$ in a total of $O \left ( n \times h \right )$ CPU operations.
  4. Rotations may be required during insertion to keep $T$ balanced.
edited by

1 Answer

Best answer
7 votes
7 votes

Statement  A    " Finding a node in T cannot require more than O(h) disk operations ( in other words, O(h) time, if only disk reads and writes are counted ). "

is  True.

Reason :  Let each node has a minimum of t children . Then searching for a node takes no more time than reading down the tree in O(h) steps and reading across each node in O(t) steps for a total of O(t * h) CPU operations and O(h) disk operations, where t is a constant .

Statement B says " h cannot exceed logt ((n + 1)/2), where t is the minimum node degree.

is True .

Reason : Since each node has a minimum of t children, the height of the tree is O(logt n) and h cannot exceed log((n + 1) / 2) . 

Statement C  says " If each node in T is augmented with an integer showing the size of that node’s sub-tree, then n additional nodes can be inserted into T in a total of O(n * h) CPU operations.

is True .

Reason : Even though the tree may grow due to splits during insertion, an insertion still takes no more than O(t * h) CPU operations, so inserting n nodes takes O(n * t * h) = O(n * h) CPU operations.

Statement D  says : " Rotations may be required during insertion to keep T balanced. " 

is Not True .

Reason :   B-Trees are a generalization  form of a binary trees (which use a single key in each node to segregate children into two groups). 

In B Trees Nodes may be split during key insertion (beginning with the root, if necessary). This has the effect that younger nodes tend to appear near the top of the tree, whereas with binary trees, younger nodes appear near the bottom of the tree.

Thats why  Rotations are not used during insertion to keep that Tree balanced. 

selected by
Answer:

Related questions