Question: For the BTreeFile constructor, when we are creating the root
node, should it be a leaf node or an index node?
A: If there is only the root node, it should be of type leaf node.
Question: How do I "open" the BTreeFile? Should I use fopen?
A: Use MINIBASE->GetFileEntry() to get the id of the root page, and then pin
the page into the buffer. You should not use fopen(). The lower layer takes
care of opening and closing files. Look at the methods in db.h.
Question: In the destructor for BTreeFile, how do we "close" the index
file?
Answer: Just unpin all pages. Be careful to update the entry for
MINIBASE_DB when the root changes (does not have to be in the destructor, but
you have to take care of it somewhere).
Question: How can I find the child nodes of a BTIndexNode?
Answer: The pointers to the child nodes are stored in records that you
design. Each record consists of the pair (key, rid). The leftmost pointer is
stored in prevPage.
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 strategies.
Question: What is the minimum occupancy? Is it half the maximum capacity?
Answer: You can use the function "IsAtLeastHalfFull" that is defined
in BTLeafPage and BTIndexPage. You can modify this function if
necessary.
Question: Assume that the B+-tree contains the key values 4,5,7,9,13.
What should GetNext() return if I call OpenScan(6,10)? What if I call OpenScan
(10,12)?
Answer: If you call OpenScan(6,10), GetNext() should first return 7,
then return 9, 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: In BTreeFileScan::DeleteCurrent(), do we have to do a
deletion with merging and redistribution, as in BTFile::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.
Question: Since the index pages in the B+ tree don't store the recordID
along with the key, I don't see how we can add duplicate support. I was
thinking of using the (key,recordid) pair as a unique identifier for the
inserts and deletes. Are we allowed to modify the index page class to include
storage for the recordID?
Answer: No. You should change your insertion/deletion/search functions
so that they can handle duplicate keys in index pages.
Question: Can I implement duplicates by adding overflow
pointers to BTLeafPage?
Answer: No. You should not use overflow pointers. Instead, you
should be able to handle duplicate key values at both the index and leaf
pages.