Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-06-29
2001-02-06
Black, Thomas G. (Department: 2771)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C711S217000, C711S218000
Reexamination Certificate
active
06185569
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the field of linked data structures, and in particular to a system for verifying the integrity of administrative data for a variety of linked data structure types including, but not limited to, linked lists, indexed trees, and secondary index trees.
Problem
Linked data structures are logical arrangements of data that facilitate efficient and organized data storage, data manipulation, and data retrieval. The basic component of a linked data structure is known as an element or node. Individual nodes in a linked data structure are linked together by special fields called pointers that identify or “point to” neighboring nodes in a linked structure of nodes. A pointer is also sometimes referred to as reference.
One reason it is important that the pointers in each node of a linked data structure are accurate is because logically neighboring nodes of a linked data structure are not necessarily stored in adjacent physical locations on a memory device. Absent a guarantee of physical proximity from one node to the next on a memory device, it is difficult to know which node is actually the next logical node in a linked data structure if an invalid pointer exists. Thus, a pointer that does not correctly point to a next logical node within the linked data structure renders the entire linked data structure unreliable and unusable.
For these and other reasons, the general problem addressed by the invention disclosed herein is that of how to verify quickly and efficiently the integrity of a linked data structure.
The following text accompanying
FIGS. 1-2
are representative examples of typical linked data structures and their general characteristics. The examples are presented for background purposes generally and to clarify terms used in this document specifically. Note that other types of linked data structures exist that are considered within the scope of this document yet have characteristics beyond those illustrated in
FIGS. 1-2
. Examples of other types of linked data structures include, but are not limited to, tagged structures, secondary index structures, and binary tree structures. Note also that the text accompanying
FIGS. 1-2
is intended only to convey basic ideas and terms, and is not intended as a complete discussion of the flexibility and construction of any one or all linked data structures known in the art. The representative linked data structure types illustrated in the text accompanying
FIGS. 1-12
include, but are not limited to, linked lists and index trees. Although linked data structure types are not limited to linked lists and index trees, these two linked data structure types are commonly understood structures existing in the art and are presented as a basis for discussion purposes and not as any limitation on the scope or field of use of the disclosed invention.
FIG. 1
illustrates a typical doubly linked list
100
in block diagram form. Doubly linked list
100
and linked lists generally are also known as a heap type structure. Doubly linked list
100
includes nodes
110
-
113
each stored in a discrete location of a memory device. Generally speaking, each of the respective nodes
110
-
113
include at least one pointer including a Forward Pointer (FP)
120
-
123
from any first node to a neighboring second node, and a corresponding Backward Pointer (BP)
130
-
133
from the second node back to the first node. The purpose of the pointers is to establish a logical chain from one node to the next and back again, so that the list of nodes
110
-
113
can be traversed in either a forward direction or backward direction.
For example, if the backward pointer
130
of node
110
points to node
113
and the forward pointer
123
of node
113
points to node
110
, then the doubly linked list
100
is a continuous loop of chained nodes. However, if the backward pointer
130
of node
110
and the forward pointer
123
of node
113
are both NULL pointers, then the doubly linked list
100
has a special characteristic where there exists only one first node and one last node among a bounded linear chain of nodes
110
-
113
. As illustrated in
FIG. 1
, node
110
is the first node of the linked list and node
113
is the last node of the linked list.
FIG. 2
illustrates a typical index tree in block diagram form. Index trees are also known as clustered index structures, trees, or in the present case a B-tree
200
. Note that a B-tree and a binary tree are distinguishable in the art, and that the present discussion relates to B-trees.
B-tree
200
includes nodes
210
-
216
each stored in a discrete location of a memory device. Each of the nodes
210
-
213
are referred to in degrees of consanguinity, at least to the extent of parent, child, and siblings that each descend from a common ancestor called a root or root node. In the present example, the root node is node
210
. Nodes
211
-
213
are siblings of each other as well as children of node
210
. Further, nodes
214
-
216
are siblings of each other as well as children of parent node
212
, and so on.
Each generation of the B-tree
200
is referred to as a level. Levels are numbered from the youngest generation, level 0, through the oldest generation, level n. There are three levels in B-tree
200
, namely level 2 containing root node
210
, level 1 containing nodes
211
-
213
, and the level 0 containing nodes
214
-
216
. Note also that nodes that have no children, such as level 0 nodes
214
-
216
, are also referred to as leaf nodes because a leaf is as far down the branches of a tree as can be traversed.
A variety of pointers exist among the respective nodes
210
-
216
depending on the location of each node in the linked structure. The variety of pointers in the present example include left child pointers
220
-
223
, right child pointers
230
-
233
, inner child pointers
240
-
243
, and doubly linked list style pointers such as forward pointers
250
-
255
and corresponding backward pointers
260
-
265
among the various levels within the linked structure. Note that although the present B-tree
200
example illustrates only three children for any one node, a B-tree can be constructed to have any number of children. Note also that each leaf node
214
-
216
can also contain any number of data fields other than the illustrated data fields
290
-
298
, and one or more data fields
290
-
298
may exist that do not contain any data at all.
B-tree
200
is referred to as an index tree structure because each of the nodes
210
-
216
includes administrative data in an index field. An index field is also known as a key or key field. The purpose of an index field is to facilitate the search for a specific item of substantive data in a leaf node. In the present B-tree
200
example, the administrative data in nodes
210
-
216
are located in index fields
270
-
277
and
280
-
288
, and the substantive data in leaf nodes
214
-
216
are located in data fields
290
-
298
.
For example, consider a B-tree having a discrete piece of substantive data located in respective leaf nodes, and each leaf node is uniquely identified by a letter of the alphabet known as a key or index key. If the substantive data indexed by the letter L is desired, a traverse of B-tree
200
would begin from root node
210
. Index field
270
would be examined and found less than letter L, then index field
271
would be examined and found less than letter L, then index field
272
would be examined and found greater than letter L. Thus the child pointer
240
of node
210
to node
212
, indicated by index field
271
as the last index field less than the index letter L, would be followed to node
212
. Similarly left child pointer
222
of node
212
would be followed to node
214
, and again index field L is located along with its accompanying substantive data in data field
292
. Because the entire traverse of the B-tree
200
example required visits to only two nodes, an indexed search is a significantly more efficient way to locate data in a linked data structure than a linear search for the s
Agarwal Sameet H.
East Jeffrey A.
Graefe Goetz
Lindell Steven J.
Lingelbach Albert L.
Black Thomas G.
Microsoft Corporation
Trinh William
Woodcock Washburn Kurtz Mackiewicz & Norris LLP
LandOfFree
Linked data structure integrity verification system which... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Linked data structure integrity verification system which..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linked data structure integrity verification system which... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2581908