B+ Trees
Introduction
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.
Design Decisions
A few assumptions are made with respect to inserts and deletes in
B+ Trees.
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
|