B+ Trees are one of the access methods that are available in Minibase. For a detailed discussion of B+ Trees and the search, insert and delete algorithms, see the text.
On inserts,when a page becomes full it is split in such a way as to keep the resulting pages about half full, subject to the condition that all duplicates remain on the same page. (Two key/rid pairs are `duplicates' if they have the same key value.) In Minibase, we assume that there will never be more than a page full of index entries with the same key value.
Index entries are deleted without any attempt to merge pages that become less than half-full. Pages are de-allocated when they become empty. (Thus, only a simplified form of the B+ tree deletion algorithm is implemented.)
The BTreeFile class is derived from IndexFile, and scans are objects of the BTreeFileScan class. Pages are BTreePage objects. Lower levels (e.g. the Disk Space Manager) treat pages as Page objects; casting is used to obtain BTreePage objects.
Click here for the public interface.
Back to the List of Components
Back to the Minibase Home Page