Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-06-30
2002-06-25
Coby, Frantz (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06411957
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a system and method of organizing nodes within a tree structure, and in particular to a system and method of organizing within a tree structure a plurality of nodes representing physical entities.
2. Description of the Prior Art
It is known to organize and manage a group of physical entities by representing those physical entities as a plurality of nodes within a tree structure, e.g. a binary tree structure. By creating such a tree structure to represent the physical entities, it is then possible to perform searches within the tree structure to find a particular physical entity, or a physical entity that meets some predetermined criteria. For example, the physical entities represented by the nodes of the tree structure may be blocks of memory and a search may be performed to find a particular block of memory, or a block of memory of a size greater than or equal to some predetermined threshold.
Each node within the tree structure will have a number of fields associated therewith. Typically, one field will be identified as a “key” and this key may be used to organize the nodes within the tree structure, so that the exact location of a particular node is dependent on that key. For example, considering the example where the physical entities may be blocks of memory, the key may be chosen to be the start address of each memory block, and the nodes within the tree may then be organized based on that address key, so that the nodes are sorted on increasing address.
It will be appreciated that by organizing the tree in such a way, it is then easy to perform searches based on the chosen key. However, it is often the case that a search may need to be performed based not only on a single parameter. However, since trees such as binary trees can generally only be sorted on a single key, the value of any other parameter required for searching will typically have to be provided within an auxiliary field associated with each node. The auxiliary field associated with a particular node may specify the value of a parameter which is not specific to that node itself, but also takes into account the value of that parameter as associated with all of its child nodes. For example, returning again to the example where the physical entities are blocks of memory, it may be desirable to perform a “first-fit” search, which aims to find the block of memory with the smallest address that has a size larger than or equal to a specified size. In such cases, each node would typically have an auxiliary field containing the maximum block size of itself and all of its children, and the nodes would be sorted within the tree by address key.
However, whilst this approach enables such searching to be performed, there is a significant amount of overhead in maintaining the auxiliary fields associated with each node. For example, to ensure predictable searching times, it is desirable for the trees to be balanced, i.e. for the tree to have a fixed maximum depth, and this requires that whenever a node is inserted or deleted, a rebalancing process is performed. Rebalancing is in itself a complicated procedure; for example even the relatively relaxed Red-Black trees require elaborate balancing steps (see “An Introduction to Algorithms” by Thomas Cormen, Charles Leiserson and Ronald Rivest, MIT Press, 1990, for a description of Red-Black trees). However, this process is further complicated when auxiliary fields are associated with each node, because in such cases the auxiliary fields will need to be recalculated for every node affected by the insertion or deletion. Further, it should be noted that since rebalancing progresses from the leaves towards the root, the tree must either be doubly linked, or a separate list with the path taken from the root must be made during the downward traversal.
It is an object of the present invention to provide an improved system and method for organizing a plurality of nodes within a tree structure.
SUMMARY OF THE INVENTION
Viewed from a first aspect, the present invention provides a method of organizing within a tree structure a plurality of nodes representing physical entities, the tree structure defining a number of node locations, each node location being reached via a predetermined path from a root node of the tree structure, the method comprising the steps of: (i) associating first and second keys with each node to be included in the tree structure, the value of at least the first key being unique for each node; (ii) arranging the nodes within the tree structure by sorting the nodes with respect to both the first key and the second key, the sorting with respect to the first key being such that each node may be positioned within the tree structure at any node location along the path from the root node to the node location specified by the first key; whereby a search can be performed for a node within the tree structure based on specified criteria for both the first and second keys.
In accordance with the present invention, each node has both first and second keys associated therewith, the value of at least the first key being unique for each node. Then, the nodes within the tree structure are sorted with respect to both the first key and the second key. In a typical prior art tree structure, such as a binary tree structure, this would not be possible, as the sorting with respect to the first key would preclude a further sorting with respect to any defined second key. However, in accordance with the present invention, the tree structure is defined such that the sorting with respect to the first key is such that each node may be positioned within the tree structure at any node location along the path from the root node to the node location specified by the first key. Hence, the exact placing of nodes based on the first key is less restricted than in the known prior art search trees, and this provides the flexibility to further sort the tree with respect to the second key. As a result, it is possible for a search to be performed for a node within the tree structure based on specified criteria for both the first and second keys.
It will be appreciated by those skilled in the art that the above defined tree structure may be used to represent a number of different types of physical entities. However, in preferred embodiments, the physical entities are free blocks of memory within a memory region, and the first key for each node is an address key identifying an address associated with the block of memory represented by that node.
Preferably, the address key identifies a start address for the block of memory.
In preferred embodiments, each node location has an address range associated with it such that a node positioned at that node location must represent a block of memory whose start address is within that address range, the root node location having the entire address range of the memory region associated with it. It will be appreciated that this approach enables any of the free blocks of memory to be allocated as the root node, since all of the free blocks of memory will fall within the address range associated with the root node location.
In preferred embodiments, the tree structure is a binary tree structure, and a number of the nodes are parent nodes, each parent node having at most two child nodes associated therewith, a first child node being positioned at a node location whose address range covers a first half of the parent node location's address range, and a second child node being positioned at a node location whose address range covers a second half of the parent node location's address range. Hence, considering the root node, which can represent any of the free blocks of memory, the only requirement for the two child nodes is that the first child node is in the bottom half of the address range of the memory region, whilst the second child node is in the upper half of the address range of the memory region. It should be noted that the choice of the two child nodes is hence independent of
ARM Limited
Coby Frantz
Nixon & Vanderhye P.C.
LandOfFree
System and method of organizing nodes within a tree structure does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method of organizing nodes within a tree structure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method of organizing nodes within a tree structure will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2981895