Access Methods


An access method (or index) facilitates retrieval of a desired record from a relation. In Minibase, all records in a relation are stored in a Heap File. An index consists of a collection of records of the form <key value,rid>, where `key value' is a value for the search key of the index, and `rid' is the id of a record in the relation being indexed. Any number of indexes can be defined on a relation.

Only B+ Tree indexes are currently supported.

Minibase only supports unclustered indexes. (In fact, dense, unclustered indexes storing key/rid-of-data-record pairs; Alternative 2, in terms of the text.) Implementing clustered indexes would require major changes. (The optimizer, however, can correctly handle clustered vs. unclustered indexes. Of course, this is only useful while running the optimizer in stand-alone mode against synthetic catalogs.)

Design Decisions

All access methods are based on a common C++ base class. A particular access method can be understood in terms of its file structure (which determines how the pages in the index file are organized), page structures (typical page format), and the functionality of scans (e.g., whether range scans are supported).

Back to the List of Components
Back to the Minibase Home Page