Browse Prior Art Database

Partial Expansions for File Organizations With an Index

IP.com Disclosure Number: IPCOM000061588D
Original Publication Date: 1986-Aug-01
Included in the Prior Art Database: 2005-Mar-09
Document File: 1 page(s) / 13K

Publishing Venue

IBM

Related People

Lomet, DB: AUTHOR

Abstract

A method of increasing file space in dynamically growing files teaches partial expansion which, instead of increasing the number of "buckets" as in prior techniques, increases bucket size by employing "elastic buckets." Elastic buckets may be used with any of various indexed files, including B-trees. Prior-art file organizations respond to growing files by full expansion or partial expansion. "Full expansion" typically involves file growth in which a growth event results in the doubling of space in a file. "Partial expansion" characterizes a growth regime in which more than one growth event is required for a file to double. Partial expansion has, in the past, been achieved by incrementally increasing the number of buckets in a small number of buckets.

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

Page 1 of 1

Partial Expansions for File Organizations With an Index

A method of increasing file space in dynamically growing files teaches partial expansion which, instead of increasing the number of "buckets" as in prior techniques, increases bucket size by employing "elastic buckets." Elastic buckets may be used with any of various indexed files, including B-trees. Prior-art file organizations respond to growing files by full expansion or partial expansion. "Full expansion" typically involves file growth in which a growth event results in the doubling of space in a file. "Partial expansion" characterizes a growth regime in which more than one growth event is required for a file to double. Partial expansion has, in the past, been achieved by incrementally increasing the number of buckets in a small number of buckets. For example, the small number of buckets could be increased from two to three and then three to four, thereby achieving doubling in two steps. The present method relates to a new partial expansion method in which bucket size is also permitted to grow. A page will typically contain somewhere between 512 and 4K bytes. A bucket (which will be a node in a B-tree) is defined to be one or more pages. The file will be permitted to grow both by increases in the number of buckets and, importantly, by increases in the number of pages per bucket. As an example, a B-tree includes single bucket nodes in which the smallest bucket size is two pages. When a node overflows, instead of splitting it into two nodes, the two-page node is replaced with a three-page node. The utilization drops to 67% instead of the 50% which would result if prior-art splitting were...