Browse Prior Art Database

Splitting a Page in an Index with Variable Length Records

IP.com Disclosure Number: IPCOM000112493D
Original Publication Date: 1994-May-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 2 page(s) / 42K

Publishing Venue

IBM

Related People

Bezviner, DE: AUTHOR [+2]

Abstract

In an index in which a record has references to all the objects that match that record's key, the records can have very different lengths. For example, a record whose key is matched by one object may be 20 bytes long, whereas a record whose key is matched by 50 objects might be 220 bytes long (assuming each reference is 4 bytes, such as a pointer reference would be).

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 72% of the total text.

Splitting a Page in an Index with Variable Length Records

      In an index in which a record has references to all the objects
that match that record's key, the records can have very different
lengths.  For example, a record whose key is matched by one object
may be 20 bytes long, whereas a record whose key is matched by 50
objects might be 220 bytes long (assuming each reference is 4 bytes,
such as a pointer reference would be).

      When a page in such an index is split, some records are placed
in the new page and some remain in the old page.  A fifty-fifty space
split is a common way to determine where to split the page, with the
exception of never unnecessarily splitting a record (splitting a
record requires considerably more overhead than merely splitting on a
record boundary).  This works well when the records are approximately
the same length, or when each record can only take a small percentage
of the total space on the page.  However, when a single record can
take a large percentage of the space on the page, it is possible to
end up having to do a page split for every new record, as is the case
when the new records all fall into sequence immediately before or
after the large record (depending on the index's implementation).
The result is a large performance penalty.  If the operation must be
logged, the performance penalty is especially large, as both I/O and
storage consumption are both further increased.

The described solution is to add an extra s...