Estimate reclaimable space in a database using B+ tree based tables
Original Publication Date: 2004-Sep-23
Included in the Prior Art Database: 2004-Sep-23
A method for estimating the space that would be recovered from a database using B+ tree based tables.
Estimate reclaimable space in a database using B + tree based tables
Disclosed is an algorithm that will estimate the amount of space that would be recovered from a database implemented using B+ tree table structures. In a database system that implements individual tables as a B+ tree, often times space in a given page in the database is left unused. This is done to allow future insert operations to likely have enough space to succeed without having to split the page and potentially make structure changes to the B+ tree. This optimization bias for insert operations may cause subsequent query operations against that table to be less efficient. For example, if the insert optimization bias is to leave fifty percent of the space on a given database page for a table unused, 100,000 records with 1,000 records per page would require 1,000 pages to be read in order to fetch all 100,000 records. However, if the pages were allowed to be occupied at one hundred percent occupancy (completely full), the same fetch operation for the 100,000 records would only require 500 database pages to be read. So, it may be valuable to B+ tree database systems to be able to estimate the amount of space that could be recovered if database pages were filled to complete occupancy as a measure of query performance efficiency.
The following algorithm will estimate the amount of recoverable space in a B+ tree based database system:
1) For each table, scan the leaf pages examining the record occupancy on a given page. We will keep track of how many actual leaf pages we evaluate. Please note that a "leaf" page is the data page in a B+ tree table that contains the actual end-user data. The B+ tree would also consist of a root node and navigation nodes that comprise the "tree" structure of the table but for purposes of this algorithm the root and navigation pages are not used.
2) For each record in a given page, use the attributes...