Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-05-12
2004-03-02
Robinson, Greta (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06701319
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to a storing apparatus and a storing structure for constructing an address space on a secondary storage by a hard disk drive or the like and, more particularly, to a storing apparatus and a data storing structure for realizing an offset space on a secondary storage by a data storing structure of a hypercube.
2. Description of the Related Art
Hitherto, as address spaces of a computer, in addition to an address space which is realized on a main storage, an address space which is realized on a secondary storage using an external storing apparatus such as a disk drive or the like is used. In the following description, the address space on the secondary storage is called an offset space in order to distinguish it from the address space on the main storage. An address on the offset space is merely called an offset. As an example of the offset space, a file system of UNIX as a typical operating system (OS) can be mentioned. It is assumed that the offsets are sequentially allocated to 1, 2, 3, . . . from 0 on a byte unit basis in a manner similar to the general address space or UNIX file. It is required that data of a CAD, complicated data such as a molecule structure or the like, or long data such as a multimedia like an image, a document, or the like is stored in a recent database. On the other hand, it is obviously requested that relatively simple data such as conventional numerical values, character data, records, or the like and a small amount of data can be handled. Those requests can be unitedly handled by the offset space. Therefore, it is desirable to realize an offset space at a high access efficiency. The reasons why the offset space meets the requirement such that a small amount of simple data is unitedly stored simultaneously with the complicated and long data will now be described in more detail.
(Storage of Complicated Data)
In a recent database, it is required that CAD data or complicated data such as a molecule structure or the like can be also handled. The complicated data can generally have a tree—or network-shaped structure. To realize those data by a secondary storage, like a data structure on the main storage, it is desirable that addresses are distributively allocated to areas and the data structures can be linked by the addresses. In this instance, it is desirable that the addresses are as simple as possible from viewpoints of easiness of programming and a space efficiency. The offset space meets such a requirement.
(Storage of Long Data)
In a recent database, it is required to store long data of an image, a document, or the like. Those data are often stored as files. The offset space conceptually includes a file as mentioned above and can store long data. Specifically speaking, when there is long data of (n) bytes, by storing the long data into offsets 0 to n−1 of the offset space, the long data can be stored. The offset space meets the above requirement.
(Storage of Simple Data)
Since complicated data can be stored in the offset space, conventional character train, numerical values, and records can be also obviously stored therein. In case of simple data, however, an amount of data is also generally small. In the case where data can be fully inserted in one page, in the database, it is obviously stored into one page. In such a case, therefore, it is desirable that the offset space can be also realized on a page unit basis. Hitherto, a database has a problem about how to solve an overflow. The offset space can also provide a possible solution for such a problem.
(Page is Made Unconscious)
A database is divided into areas called pages of a fixed length of, for example, 4 kB and stores data therein. “Page” is a unit of an input/output between the secondary storage and the main storage. A unit of an input/output in the OS is also generally such a page. As shown in
FIG. 1
, a page
100
is usually divided into a header portion
102
and a data portion
104
. In case of storing user data, information on the system side is necessary independent on the data. For example, information such as size of user data and amount of remaining space areas is necessary. That information is called management information. User data and, in a special case, management information are stored in the data portion
104
. The management information is stored in the header portion
102
.
FIG. 2
shows a state of storage of data in the database. In this example, a record R
1
and a record R
2
have been stored in 0-page
100
-
0
. Subsequently, when the user intends to insert a record R
3
, if it cannot be fully inserted into the 0-page
100
-
0
, a new 1-page
100
-
1
is captured and the record R
3
is stored in the 1-page
100
-
1
. In case of constructing a system of the database, usually, programming is performed while the user is conscious of the pages. For example, it is now considered that the record R
1
in
FIG. 2
is updated. If a length of record R
1
increases and the record R
1
cannot be fully inserted in the 0-page
100
-
0
, as one of countermeasures, there is a measure such that a 2-page
100
-
2
is newly assured and some portion in the record R
1
after the updating or the whole record R
1
is transferred as shown in FIG.
3
.
FIG. 3
shows a case where the record R
1
becomes two partial records R
11
and R
12
after the updating, the record R
11
has been stored in a 0-page
104
-
0
, and the record R
12
has been stored in a 2-page
104
-
2
. A state where a bundle of data cannot be fully inserted into one page as mentioned above is called “overflow”. The overflow is shown as an example in which the user is conscious of the page. In case of using the offset space, generally, data can be handled without allowing the user to be aware of the overflow and page. However, since there is a problem about continuity of areas, although it depends on a realizing method, a situation such that the data has to be copied or the like occurs.
FIG. 4
shows a state where the overflowed records in
FIG. 3
are stored in an offset space of offsets 0 to 7999.
Hitherto, there is a file system in the OS such as UNIX or the like as a typical example of the offset space. The file system of UNIX has the following features.
(1) Offset space
The file of UNIX is considered as an offset space. The offsets of 0, 1, 2, . . . are allocated to respective bytes of the data of the UNIX file from the head.
(2) Management page is separately managed
In UNIX, the user data and management information are managed by different pages. A page to store the management information is called a management page.
(3) Management page has a tree structure
The management page is realized as an unbalanced tree structure.
(4) There is no function for area management
A function for area management is provided in the address space on the main storage. Specifically speaking, functions of malloc ( ) and free ( ) are supported in UNIX. When the user wants to assure an area whose dimensions are “size”, by calling this function as
address=malloc(area);
the system side assures a continuous area existing on the main storage and returns the address as an “address”. By setting
free(address)
this area is released. So long as the area corresponding to “address” is not opened, this area is not again transferred by malloc ( ). However, the area managing function of the main storing space does not exist in the file as an offset space of UNIX. UNIX has a process for writing the contents of a continuous area of (n) bytes (such an area is called a “user buffer”) on the main storage designated by the user from some offset into an area of (n) bytes and a process for, contrarily, reading out the contents of (n) bytes from some offset into a user buffer of (n) bytes designated by the user. In the database or the like, however, the area management is performed with regard to an area of the record or the like.
(5) Copy into buffer
Although pages on the secondary storage are copied into the buffer which is managed by the system, they are further copied there
Fujitsu Limited
Robinson Greta
Staas & Halsey , LLP
LandOfFree
Storing apparatus and data storing 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 Storing apparatus and data storing structure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Storing apparatus and data storing structure will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3277510