Browse Prior Art Database

Caching Objects in a Data Space Disclosure Number: IPCOM000113983D
Original Publication Date: 1994-Oct-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 4 page(s) / 160K

Publishing Venue


Related People



Balanced binary search tree with imbedded linked list.

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

Caching Objects in a Data Space

       Balanced binary search tree with imbedded linked list.

      Applications exist that require two retrieves of data from
auxilliary devices.  One retrieve is required to view the data, and
another to print the data.  What follows is a proposal that will
result in improving response time by eliminating the need for the
second I/O.
     Introduction - A solution for caching retrieved data in a data
space requires management of allocated and unallocated space.
 Managing allocated space requires:
 o   a directory,
 o   a technique for aging data space resident objects.
 Managing unallocated space requires:
 o   a technique to ensure all free space fragments represent the
    largest contiguous area of free space possible,
 o   a technique for ordering free space fragments by size for
    efficient allocations.
 Following is a proposal for this solution.
      Directory - The main criterion for a directory is it must be
efficient, not necessarily optimal.
      Efficiency of a directory is inversely proportional to the
amount of time required to arrive at a decision via directory access.
When talking of a directory that maps a dynamic data space, a
'decision' can be defined as the determination of whether an object
is resident in a data space (allowing immediate access) or is not
resident (requiring I/O).

      The primary contributor of directory access cost is the
overhead associated with paging.  Paging overhead can be reduced by
taking steps to minimize the size of the directory page set.  One
possible solution is the allocation of four kilobyte directory blocks
from which directory nodes are allocated, rather than allocating
storage for individual directory nodes.  One might also consider
allocating directory storage space from a fixed subpool (eliminating
paging overhead entirely).  When limiting cost consideration to node
accesses, the use of a binary search tree to organize a collection of
objects in a data space provides reasonable performance (efficiency)
without a complicated algorithm.

      A balanced binary search tree mapping 130,000 objects will
require a worst case of 17 node accesses to arrive at a decision.  In
addition, a binary search tree provides additional flexibility that
lends itself to a solution for aging objects in a data space.

      Aging data space resident objects - When dealing with a finite
amount of space and a set of potential object residents with
virtually unlimited space requirements, a point can be reached where
the data space becomes full and object replacement is necessary.
Criteria are needed to decide which object or set of objects will be

      One criterion is the amount of time objects go unreferenced.
Unreferenced age or time would not represent some absolute
quantifiable period, but would be relative to other objects'
unreferenced age or time.

      A rather simple solution...