M=4
,
containing all the letters of the alphabet,
unique? Explain.
M=3
is given below.
Insert a record with key N
,
making sure to show the evolution of the tree as the B-tree insertion
algorithm proceeds.
M=3
is given below. Delete the
record with key N
, making sure to show the evolution of
the tree as the B-tree deletion algorithm proceeds.
M
) of a B-tree:
M=3
allows nodes to have as many as
three children. Why is a B-tree of order M=2
not
necessarily a binary search tree?
M=3
, consisting of
three levels of completely full index nodes,
how many disk accesses would it take to perform the
following tasks? Fill in the table and show your calculations, below.
task | B-tree | B+ tree | ||
---|---|---|---|---|
at most | at least | at most | at least | |
locate an arbitrary record | ||||
locate sequentially next record |
M=3
by inserting the
following keys into an initially empty tree:
A, B, C, D, E, F, G, H
.
Show the tree at each stage.
b) Can a tree of lower height, also of M=3
and containing
the same keys as in part (a) be constructed? If so, show such a tree,
and if not, explain why not.
c) If we now added a record with key I to the tree of part (a), would your answer to part (b) change? Justify your answer numerically.
d) Delete the record with key B
from the tree of part (a).
Show the tree at each stage.