Question: For the BTreeFile constructor, when we are creating the root
node, should it be a leaf node or an index node?
Answer: If there is only the root node, it should be of type leaf node.
Question: How do I "open" the BTreeFile?
Answer: Use MINIBASE_DB->GetFileEntry() to get the id of the header page, and then
pin the page into the buffer. Look at the useful methods in db.h.
Question: In BTreeFile constructor, we need to allocate a new page when we cannot find the file with the input filename. We are using the NewPage method in the BufMgr to allocate it. It returns a Page pointer, but the B+ tree header variable is of type BTreeHeaderPage. Do we just need to cast header to (Page*)?
Answer: Yes, you should cast between BTreeHeaderPage* and Page*. Please
look at the provided constructor BTreeFile::BTreeFile (Status& returnStatus) for
an example.
In general, BufMgr and the underlying DB only understands Page*. So anytime you
allocate a new page of type BTreeHeaderPage, BTLeafPage, BTIndexPage, HeapPage
and so on, you should cast between it and Page*.
Question: In the destructor for BTreeFile, how do we "close" the index
file?
Answer: In a correct implementation of B+
tree, only the header page will stay pinned at this point. Therefore you only
need to unpin the header page here.
Question: For insertions, do I have to implement both splits and
redistribution?
Answer: No. You have to implement splits, but not redistribution.
Question: For deletions, do I have to implement both merging and
redistribution.
Answer: Yes. You have to implement both merging and redistribution.
For implementing redistribution in this assignment, it is sufficient for you to
pick one of the two siblings and try to redistribute. For example, you can
always pick the left sibling to perform redistribution; if that fails, try
merging; if that fails still, do nothing.
Question: We know each B+ tree leaf page record is a pair of key and rid (referred to as dataRid below). BTreeFile::Delete takes as input a key and an rid. Does this rid refer to a dataRid, or the rid of a B+ tree leaf record itself?
Answer: The input rid of BTreeFile::Delete refers to a dataRid. The idea is that the rids of leaf/index records in B+ tree are only artifacts to the index structure, and are also subject to change (think of the rids of records in a sorted heap page -- they are not stable and can change when records are inserted/deleted). So these dataRids should never be exposed to user. Also, users will only care about the dataRids stored in the B+ tree leaf nodes anyway, and BTreeFileScan is supposed to provide such as iterator interface to give back these dataRids (paired with the key values) one by one.
Question: Assume that the B+-tree contains the string key values
04,05,07,09,13. What should GetNext() return if I call OpenScan(06,10)? What if
I call OpenScan (10,12)?
Answer: If you call OpenScan(06,10), GetNext() should first return 07,
then return 09, then return DONE. If you call OpenScan(10,12), then the first
call to GetNext should return DONE. You have to return a DONE object, even if
there are no keys in the specified range.
Question: What should we initialize in OpenScan?
Answer: You should initialize some member variables to keep track of the
current state (including the high key and the low key), so that you can actually
perform the scan using GetNext().
Question: We know each B+ tree leaf page record is a pair of key and
rid (referred to as dataRid below). GetNext() returns an rid. Does it
refer to the rid of a leaf record in the B+ tree, or a dataRid?
Answer: It refers to a data rid. Again, users will only care about the
dataRids stored in the B+ tree leaf nodes, and BTreeFileScan is supposed to
provide such as iterator interface to give back these dataRids (paired with the
key values) one by one.
Question: In BTreeFileScan::DeleteCurrent(), do we have to do a
deletion (with merging), as in BTreeFile::Delete?
Answer: Yes.
Question: What should I return when BTreeFileScan::DeleteCurrent() is
called on the last record in the specified range?
Answer: You should return OK. If DeleteCurrent is called a second time at
same position, without a call to GetNext() in between, return FAIL.
Question: Are we allowed to modify SortedPage and HeapPage?
Answer: No.