Disk Space Manager
The disk space manager (DSM) (implemented as part
of the DB class) is
the component of Minibase that takes
care of the allocation and deallocation of pages within a database.
It also performs reads and writes of pages to and from disk, and
provides a logical file layer within the context of a
database management system.
A Minibase database is implemented as a single Unix file. Its
pages are simply page-sized blocks of bytes within this file. The
higher-level structures of a Minibase database, such as heap files
and B+ tree files, are actually logical files consisting of
collections of database pages. In discussing the DSM,
we will refer to page-sized blocks of bytes in the underlying
Unix file as ``pages'', and pages in higher-level structures
such as heap files as, for example, ``heap file pages'' in
order to avoid confusion.
The Page Class
The abstraction of a page is provided by the Page class. All higher
level applications use this Page class.
Higher layers impose their own structure on pages simply by casting
page pointers to their own record types. The data part of a page
is guaranteed to start at the beginning of the block.
The Database (DB) Class
The DB class provides the abstraction of a single database stored
on disk. It shields the rest of the software from the fact that
the database is implemented as a single Unix file.
It provides methods for allocating additional pages (from the
underlying Unix file) for use in the database and deallocating
pages (which may then be re-used in response to subsequent
allocation requests). (The DB class actually supports allocation
and deallocation of a consecutive run of pages,
though the higher-level code usually just asks for one page at a time.)
There is one instance of the DB class for every database used. (In
Minibase, a transaction is allowed to have at most one active
database, so there is just one instance of this class.) The
operations on this class include creating and destroying databases,
and, as noted above, allocating and deallocating pages. Further,
existing databases can be opened and closed, and there are
methods to retrieve certain characteristic properties of the
database, like the number of pages and page size.
The DB class also provides a file naming
service, which is used by higher-level code to create
logical ``files of pages''. This service is implemented using records
consisting of file names and their header page ids. There are
functions to insert, look up, and delete file entries.
The set of file entries is collectively referred to as the
The DB class keeps
track of allocated space within the database using a fixed
set of pages called the space map.
They can be thought of as containing a bit
map: one bit per database page, with ``0'' denoting that the corresponding
page is free and ``1'' denoting that it is allocated.
The DB class maintains the space map, in addition to its other
duties, updating it whenever pages are allocated or deallocated.
Limitations, or Room for Improvement
The current implementation creates fixed-size databases; the space
map is set when the database is created, and never grows. This
limitation would be fairly easy to remedy, either by setting a
maximum database size (still fixing the size of the space map, but
allowing the database to grow to fit the maximum number of pages
representable in the map), or by having the space map be a linked
list of pages and grow as needed.
Click here for the public interface for the DB
Back to the List of Components
Back to the Minibase Home Page