Browse Prior Art Database

Rapid Detection of Index Key Insertion Patterns

IP.com Disclosure Number: IPCOM000114472D
Original Publication Date: 1994-Dec-01
Included in the Prior Art Database: 2005-Mar-28
Document File: 4 page(s) / 98K

Publishing Venue

IBM

Related People

Dean, RD: AUTHOR [+3]

Abstract

A method of detecting index key insertion patterns which is unaffected by a few stray keys which violate the pattern is disclosed. Pattern granularity is limited to ascending, descending, and random but the detection mechanism requires very little permanent work space and is extremely efficient from a computational perspective.

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

Rapid Detection of Index Key Insertion Patterns

      A method of detecting index key insertion patterns which is
unaffected by a few stray keys which violate the pattern is
disclosed.  Pattern granularity is limited to ascending, descending,
and random but the detection mechanism requires very little permanent
work space and is extremely efficient from a computational
perspective.

      Consider a binary tree.  Each node of such a tree provides the
ability to navigate in either the low or high collating direction.
An insert key operation will cause the creation of a new node in
either the low or high direction relative to an existing node in
order to provide space to house the new key.  This number of insert
operations that occur in the low direction will be tabulated and used
to determine the key insertion pattern in an index.

      Two count fields and a current-pattern status field will be
maintained in the index object header as follows:
  LowInsertOperations      The number of insert operations that
                            occurred on the low side of an existing
                            node in the tree.
  TotalInsertOperations    The total number of insert operations that
                            have occurred.
  CurrentPattern           The current key insertion pattern that
                            prevails in the index.  This field will
be
                            a value that indicates either a random,
                            ascending, or descending key pattern.

The following constant fields are also defined:
  PatternReevaluationThreshold  The total number of insert operations
                                 at which a reevaluation of the
                                 CurrentPattern is performed.
  HighSequentialThreshold       The greatest number of insert
                                 operations which, if they occurred
on
                                 the low side of a node, would
indicate
                                 an ascending insertion pattern.  In
                                 other words, HighSequential
Threshold
                                 is the greatest number of insert
                                 operations which deviate from the
                                 general ascending insertion pattern
                                 such that the result is still an
                                 ascending insertion pat...