Browse Prior Art Database

An Efficient Way To Clean B-tree Index Pages

IP.com Disclosure Number: IPCOM000202448D
Publication Date: 2010-Dec-15
Document File: 2 page(s) / 13K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method for using a compressed bitmap to simplify the process of cleaning index pages when there is a large number of pages with deleted items.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 01 of 2

An Efficient Way To Clean B-tree Index Pages

When an item is deleted in a B-tree index, it is not always removed immediately. The index pages containing committed deleted items are cleaned at a later time. The index pages containing committed deleted items need to be collected and managed for cleaning.

A database server with hundreds of large indexes may have many index

pages to be cleaned; therefore, it is important to manage the pages to be cleaned in an efficient manner.

One known way to manage the large set of dirty pages is to use a small bitmap for each index and represent a range of pages for each bit. If a bit is set, all the pages represented by that bit's range will be candidates for cleaning. This method has an obvious drawback: if only a few pages in the range are candidates for cleaning, then all the other pages in the range represented by that bit need to be examined for cleaning. This causes unneeded input and output (I/O) and processing. The size of the bitmap increases as the range of pages per bit decreases. For example, using one bit to represent one page will avoid the unneeded I/O problem but that will make the bitmap very large.

The disclosed solution is a method for using a compressed bitmap to simplify the cleaning process. For each index, the entire set of pages that needs to be cleaned is represented using a compressed bitmap.

A compressed bitmap is described as

follows: if the n-th bit of the expanded version of the compressed bitmap is set, it means the n-th page needs cleaning.

A compressed bitmap uses less memory and provides

for efficient processing. This provides an efficient method to manage large number of pages with deleted items.

In an exemplary embodiment of the invention, an item may be deleted from a B-tre...