Browse Prior Art Database

Serialization of AVL-Binary Tree Element Retrieval via Duplexed Pointers

IP.com Disclosure Number: IPCOM000107740D
Original Publication Date: 1992-Mar-01
Included in the Prior Art Database: 2005-Mar-22
Document File: 2 page(s) / 83K

Publishing Venue

IBM

Related People

Greenspan, S: AUTHOR [+3]

Abstract

Disclosed is a performance-optimized technique for retrieval of AVL- binary tree elements in a multi-tasking, multi-process environment. Using duplexed tree pointers, a synchronization count, and an active tree indicator, retrieval of elements from the AVL tree structure may occur simultaneously with additions or deletions. This technique optimizes the retrieval path length by allowing the retrieve code to run without obtaining any system locks or using the other more costly serialization techniques.

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

Serialization of AVL-Binary Tree Element Retrieval via Duplexed Pointers

       Disclosed is a performance-optimized technique for
retrieval of AVL- binary tree elements in a multi-tasking,
multi-process environment.  Using duplexed tree pointers, a
synchronization count, and an active tree indicator, retrieval of
elements from the AVL tree structure may occur simultaneously with
additions or deletions.  This technique optimizes the retrieval path
length by allowing the retrieve code to run without obtaining any
system locks or using the other more costly serialization techniques.

      AVL-binary tree structure with duplexed pointers (AVLDP).  Each
AVLDP tree has header which contains an active tree indicator, a
synchronization count, and a pair (duplexed) of first element
pointers.  The active tree indicator is a field that the retrieve
function will examine to determine which set of duplexed pointers are
to be used or considered 'active'.  It is also used by the add and
delete functions to determine which set of duplexed pointers are to
be manipulated or considered 'inactive'.  The synchronization count
is incremented when an update is made to the AVLDP tree.  NOTE:  The
active tree indicator and synchronization count are adjacent in
storage so that one atomic instruction (Compare and Swap) can be used
to update the two fields simultaneously.

      Each AVLDP  element contains a key, a user data field or
pointer to a data field, two pairs (duplexed) of right and left node
pointers, and a pair (duplexed) of balance indicators.
Updating the AVLDP tree

      Updates are made to the AVLDP in the same basic manner as
normal AVL trees.  Additions and deletions from the tree are made
such that the binary tree is balanced, e.g., the longest brand in the
tree is only one element longer than the shortest branch.  Additions
and deletions are serialized via a system lock, and are...