Structure for a database

Details Structure for a database Structure for a database

1998-07-15

2001-06-19

Vu, Kim (Department: 2172)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000

Reexamination Certificate

active

06249788

ABSTRACT:

FIELD OF INVENTION
The present invention relates to a structure for the storage of data-information within a data-base.
The structure is suitable where data-information is structured in a node hierarchy that comprises a B-tree. This tree includes root-node, possibly one or more levels of intermediate nodes, and one or more leaf-nodes.
The root-node includes a root-element, respective intermediate nodes include one or more intermediate elements, and respective leaf-nodes include one or more leaf-elements.
The B-tree is built-up by linking a first intermediate element within an intermediate node to the root-element or to an intermediate element within an intermediate node placed at a higher level in the hierarchy. Remaining intermediate elements within the intermediate node are linked to the first intermediate element.
Similarly, a first leaf-element within respective leaf-nodes is linked either to the root-element or to an intermediate element of one of the intermediate nodes. Remaining leaf-elements in a leaf-node are linked to the first leaf-element.
Respective elements include address-information for the links and data-information.
The order of the elements within a node is a logical order with respect to data-information, such as an alphabetical or numerical order.
The data-information in respective elements constitutes the difference in data-information in relation to the data-information belonging to preceding elements in the hierarchy.
BACKGROUND OF THE INVENTION
It has long been known to use different data structures to store data within a data-base. These structures afford various advantages with respect to used storage space and the possibility of fast-searching, for instance.
A known structure is based on a B-tree, thereby enabling the logical distribution of elements in a table within a data-base.
An element may include an internal address in a data-base that is coupled to an external key, such as a telephone number, for instance. When inserting a new telephone number in a table, a calculation is made as to the element in which the internal address of the telephone number shall be placed, by means of a logic order.
The function of the B-tree is to distribute the addresses in the table, so that said addresses are distributed in a manner which will enable them to be easily found.
The B-tree is used essentially to create an ordered and simple structure.
Each tree commences with a root-node which points to further nodes in which a search for a desired node can be carried out on the basis of certain criteria. These nodes will often include a key or an index.
Http addresses, file names, time stamps, telephone numbers, etc., are examples of keys stored in a B-tree.
It should also be mentioned that the aforesaid nodes are nodes in a tree-structure intended to describe an hierarchy of stored keys or indexes, and not processor nodes in a distributed data-base.
It is also known in the case of logically sequential data sets to store solely the difference information between two mutually sequential data sets.
This procedure is used, for instance, in image processing where a large quantity of information is required to store and reproduce moving pictures or images, but where the difference between two mutually sequential images may be very small, and consequently only the difference between these images is stored and utilised when reproducing the images.
It is also known to store solely the difference between two interlinked elements instead of storing the entire element, in conjunction with linked lists.
This requires less storage space, but provides the same information.
It should also be mentioned that in conjunction with file names or http addresses for instance, different formats and suffixes are used which can make it difficult to describe the difference information between two adjacent nodes in a simple manner.
The following publications describe the handling of information structured in a B-tree. “Transaction Processing: Concepts and Techniques”, J. Gray, A. Reuter, Morgan Kaufman, 1993 .
“Prefix B-trees”, R. Bayer, K. Unterauer, ACM Trans. on Data-base Systems, Vol. 2, No. 1, pp. 11-26, 1977.
It should also be mentioned that it is known to store different elements in a so-called container, where the elements lie consecutively one after the other, and where a container can be treated as a unit.
SUMMARY OF THE INVENTION
Technical Problems
When considering the state of the prior art as described above, it will be seen that a technical problem resides in providing a structure for the storage of data-information in a data-base which requires far less storage space than that required with known structures, even with respect to known compression, by storing solely difference information in relation to preceding nodes.
Another technical problem resides in the provision of a compression structure that will also enable a desired element or object to be found effectively.
Another technical problem resides in the ability to provide a structure in which a data-word is able to describe the occurrent differences in an unequivocal and simple fashion.
Yet another technical problem resides in providing a structure for a data-word which handles different suffixes of the data-information to be stored in a simple fashion.
Another technical problem resides in enabling a difference between two sets of data-information to be easily represented, where said difference does not lie at the end of the data-information, to be readily represented without needing to represent those similarities that are found after this difference in data-information.
Another technical problem resides in the ability to handle changes of elements or objects in a compressed B-tree.
Yet another technical problem is one of enabling elements or objects in a compressed B-tree to be copied.
Another technical problem is one of accelerating the search of a B-tree when seeking a specific element.
Another technical problem is one of providing a structure in which compression of data-information provides the possibility of substantially speeding-up the search of a B-tree when seeking a specific element.
Still another technical problem is one of providing a structure which will enable elements to be inserted in and removed from a B-tree simply and effectively, where the data-information is compressed and includes solely difference information relating to preceding nodes.
Another technical problem is one of providing a structure whereby a node that includes a plurality of elements is available by a read-in to the cache memory.
Another technical problem is one of providing a structure in which the amount of address information required with references between different nodes and elements included therein is much less than that required traditionally.
Solution
With the intention of solving one or more of the aforesaid technical problems and with a starting point from a structure of the kind described in the introduction, it is proposed in accordance with the invention that the data-information within the root-element constitutes a start-value and that this start-value constitutes the actual data-information. It is also proposed that the differential information within remaining elements is comprised of a data-word that represents the actual difference in the data-information in relation to data-information belonging to preceding elements, regardless of where the difference is within the data-information.
Since only the actual difference is stored, regardless of whether this difference is at the end or not, a highly compressed structure is obtained.
According to one embodiment of the present invention, such a structure is created by allowing the differential-information to include a directive as to whether something shall be removed relative to the data-information belonging to preceding element and, if so, the nature of what shall be removed and from where in the data-information it shall be removed, and to allow the differential-information to include a directive as to whether something shall be added relative to the data-informatio

Affiliated with

Also associated with

Rating

Structure for a database does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Structure for a database, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Structure for a database will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2495765