METHOD AND SYSTEM FOR EFFICIENTLY SEARCHING FOR FREE SPACE IN A TABLE OF A RELATIONAL DATABASE HAVING A CLUSTERING INDEX

摘要

A method of searching a table in a database management system for free spacefor insertinga new record into the table. The table resides in a storage media, andincludes a series of pagescapable of storing a plurality of records. The table has a clustering indexdefined in a column of thetable. The new record has a new record attribute for storing in the column ofthe table when the newrecord is stored in the table. The method comprises searching for a targetpage in the series of pages,the target page being selected to maintain clustering when the new record isinserted thereon. Oncethe target page has been located, it is searched for sufficient free space toaccommodate the newrecord. If sufficient free space is found on the target page, then the newrecord is inserted on thetarget page. If sufficient free space is not found on the target page, then atarget neighbourhood ofpages in the series of pages is searched for sufficient free space toaccommodate the new record.The target neighbourhood of pages surrounds the target page. If sufficientfree space is found on apage in a target neighbourhood of pages, then the new record is inserted on tothis page in the targetneighbourhood of pages. If sufficient free space is not found in the targetneighbourhood of pages,then the method further comprises searching for sufficient free space toaccommodate the new recordoutside the target neighbourhood of pages. If sufficient free space is foundoutside the targetneighbourhood of pages, then the new record is inserted on a non-neighbouringpage outside thetarget neighbourhood of pages. If sufficient free space is not found outsidethe target neighbourhoodof pages, then a new page having the new record is appended to the end oftable.