 |
Database Management Systemsby Raghu Ramakrishnan and Johannes Gehrke
|
|
|
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, whenever necessary 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 ClassThe 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) ClassThe 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.
File DirectoryThe 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 file directory.
Space ManagementThe 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 ImprovementThe 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 class
Back to the List of Components |