Browse Prior Art Database

Extending Bindary Search for Entries with an Ordered Set of Object References

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

Publishing Venue

IBM

Related People

Bezviner, DE: AUTHOR [+2]

Abstract

A binary search usually returns an index entry and an answer of either "found" or "not found", or one of three values:

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

Extending Bindary Search for Entries with an Ordered Set of Object
References

      A binary search usually returns an index entry and an answer of
either "found" or "not found", or one of three values:

1.  Greater than

2.  Equal to (Match)

3.  Less than

      When the entries in the index being searched contain two parts,
a key and an ordered set of object references associated with the
key, a new object reference may be inserted in one of five places:

1.  As a new entry prior to an existing entry

2.  As a new entry after an existing entry

3.  As the first object reference in an existing entry

4.  As an intermediate object reference in an existing entry

5.  As the last object reference in an existing entry

      With the typical two- or three-valued response, there is no way
to uniquely determine how to add a new object reference without doing
another comparison.  For example, a value of "greater than" could
mean that the search key was not found and that it should be added as
a new entry, or it could mean that the search key matches an existing
entry's key and that the object reference in the search key has an
order value higher than any of the object references in the existing
entry with a matching key.  Since key comparisons are one of the
most, if not the most expensive parts of a search, this extra
comparison should be avoided if at all possible.

      The solution described herein is to have the binary search
return an answer consisting o...