Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2005-06-10
2009-12-08
Rones, Charles (Department: 2164)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
07630998
ABSTRACT:
The addition of a layer between a tree data storage structure and a persistent storage is disclosed. The additional layer, called a storage module, generates an identifier and allocates it to a node in the tree data storage structure. The storage module additionally performs a mapping function, allocating the identifier to a location in persistent storage. If the node is later deleted from the tree data storage structure, then the mapping of the identifier to the location in persistent storage is likewise deleted. In this way, if the node is deleted and, concurrently, a lookup or write operation is attempted on the deleted node, the storage module will read the identifier associated with the deleted node but will not be able to map the identifier to a location in persistent storage. Instead, an exception is generated and sent to the tree data storage module.
REFERENCES:
patent: 5243596 (1993-09-01), Port et al.
patent: 5276874 (1994-01-01), Thomson
patent: 5506983 (1996-04-01), Atkinson et al.
patent: 5508983 (1996-04-01), Nakamura et al.
patent: 6009427 (1999-12-01), Wolff
patent: 6067545 (2000-05-01), Wolff
patent: 6192051 (2001-02-01), Lipman et al.
patent: 6473849 (2002-10-01), Keller et al.
patent: 6532457 (2003-03-01), Tal et al.
patent: 2005/0114595 (2005-05-01), Karr et al.
Lehman, P.L. et al., “Efficient Locking for Concurrent Operations on B-Trees”,ACM Transactions on Database Systems, Dec. 1981, 6(4), 650-670.
MacCormick, J. et al., “Boxwood: Abstractions as the Foundation for Storage Infrastructure”,Microsoft Research Silicon Valley, 8 pages 2004.
Sagiv, Y., “Concurrent Operations onB*-Trees with Overtaking”,Journal of Computer and System Sciences. 1986, 33, 275-296.
Thekkath Chandramohan A.
Zhou Lidong
Kuddus Daniel
Microsoft Corporation
Rones Charles
Woodcock & Washburn LLP
LandOfFree
Performing a deletion of a node in a tree data storage... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Performing a deletion of a node in a tree data storage..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Performing a deletion of a node in a tree data storage... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4144867