Browse Prior Art Database

Avoiding Binary Search when Index Cursor Affected by Update

IP.com Disclosure Number: IPCOM000110624D
Original Publication Date: 1992-Dec-01
Included in the Prior Art Database: 2005-Mar-25
Document File: 1 page(s) / 58K

Publishing Venue

IBM

Related People

Bullock, GR: AUTHOR [+2]

Abstract

Disclosed is a method for avoiding a binary search while resynching an Index Cursor affected by an update to an index. This method is applicable in a system that does not update Index Cursor Control Blocks at the time an update occurs, but instead, re-establishes an index cursor's currency upon the next fetch with that cursor.

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

Avoiding Binary Search when Index Cursor Affected by Update

       Disclosed is a method for avoiding a binary search while
resynching an Index Cursor affected by an update to an index.  This
method is applicable in a system that does not update Index Cursor
Control Blocks at the time an update occurs, but instead,
re-establishes an index cursor's currency upon the next fetch with
that cursor.

      In OS/2* Database Manager, an Index Cursor Control Block is
used to save the current key position during index scan.  The current
key is uniquely identified by the key value and Record ID (RID), and
these values are thus saved in the Cursor Control Block.  The
physical location of the current key is saved as well, to prevent
Index B-tree traversal when fetching the next key.  (A key's physical
location in OS/2 Database Manager is specified by the page number and
slot number of the key.)  B-tree traversal is something to be
avoided, not only because of the additional page fixes, but also
because of the additional binary search required at each level in the
B-tree.  (In OS/2 Database Manager, there is one page per node, and a
node does not span pages.)

      However, Index Cursor Control Blocks are not updated when some
operation, such as a key insertion or deletion, affects the current
key's physical location.  Instead, Index Manager resynchs the Index
Cursor Control Block during the next fetch request by relocating the
current key.  Index Manager can detec...