Browse Prior Art Database

Search Argument Checking

IP.com Disclosure Number: IPCOM000086510D
Original Publication Date: 1976-Sep-01
Included in the Prior Art Database: 2005-Mar-03
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Wolff, CH: AUTHOR [+2]

Abstract

The use of radix partition trees for efficient retrieval of named data is described in U. S. patent 3,916,387. The terminology used herein is the same as in the referenced patent.

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

Page 1 of 1

Search Argument Checking

The use of radix partition trees for efficient retrieval of named data is described in U. S. patent 3,916,387. The terminology used herein is the same as in the referenced patent.

The radix partition tree (RPT) has the property that the names or keys are not stored at the inner vertex entries, but are stored at the ends of the binary-tree paths going to the data. If the RPT is used to index a set of keys in a block stored as a page on a disk, then each key represented in the RPT nominally requires from six to eight bytes of space in the page. This does not include the space to store the keys. If the keys are also stored in the same page as the RPT, then the total space requirement per key includes the space to store the keys, as well as the six to eight bytes.

For example, suppose that an index block, as in the virtual sequential access method (VSAM) program is represented by an RPT. Then the number of successor blocks is limited by the total number of keys that can be represented in a block, since each key represents a connection to another index block. If the keys were all eight bytes long, and the RPT overhead is eight bytes per key, then a 4096-byte page can only be 256 keys, hence there cannot be more than 256 successor blocks.

However, if the key at the end of a path in a block is not stored at the end of the path, in the same block, but rather in the front of the block the path goes to, then the storage overhead is only 8 bytes per...