Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2005-03-15
2005-03-15
Alam, Shahid (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06868414
ABSTRACT:
The present invention provides a method, system, and computer program product for reliably and efficiently serializing access to data structures (i.e. updates and retrievals) without requiring searchers to use locks. The disclosed technique ensures that the contents of the data structure remain valid during access operations, yet does not require searchers to perform compute-intensive comparison operations to determine validity. Two trees are used at all times. Searches proceed against a first tree, while the second tree is used for performing updates. The steps required to carry out a particular update operation are stored as a queued transaction. When the update to the second tree completes, the trees are switched. The queued transaction is applied to the now-out-of-date tree, such that the nodes of this tree do not need to be searched or otherwise evaluated in order to perform the update, thereby optimizing the process of bringing this tree into synchronization with the tree that is now being used by the searchers. The two trees are repeatedly switched as additional update operations are performed. Atomic operations are used to ensure proper synchronization between the search and update processing on the trees.
REFERENCES:
patent: 4627019 (1986-12-01), Ng
patent: 5497487 (1996-03-01), Fortier
patent: 5852715 (1998-12-01), Raz et al.
patent: 6006216 (1999-12-01), Griffin et al.
patent: 6199069 (2001-03-01), Dettinger et al.
patent: 6353820 (2002-03-01), Edwards et al.
patent: 6360219 (2002-03-01), Bretl et al.
patent: 6377959 (2002-04-01), Carlson
patent: 6480854 (2002-11-01), Gross et al.
patent: 6535869 (2003-03-01), Housel, III
patent: 20020004799 (2002-01-01), Gorelik et al.
“Serialization of AVL-Binary Tree Element Retrieval via Duplexed Pointers”, Mar. 1992, IBM Technical Disclosure Bulletin, No. 10B, pp. 138-139.*
IBM Technical Disclosue Bulletin, “Serialization of AVL Binary Tree Element Retrieval via Duplexed Pointers”, Mar. 1992, pp. 138-139.
Khanna Sanjay
Napoli Lori Ann
Alam Shahid
Chen Chongshan
Doubet Marcia L.
Herndon Jerry W.
LandOfFree
Technique for serializing data structure updates and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Technique for serializing data structure updates and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Technique for serializing data structure updates and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3405335