JPS63318628A - Horizontally dividing system for data base - Google Patents

Abstract

PURPOSE:To contrive the equalization of the number of tuples stored in a disk device automatically, by dividing a page into two, when tapple storing pages are full, storing the tuple in one of them, and sending one page to the disk device having the smallest number of pages. CONSTITUTION:It is assumed that a tuple in which key values of an integer value are between 1-100 is stored in a page 3c in a disk device 2e. In case of storing the tuple having a key value of the key values between 1-100, in this page 3c, since the page in full, it is divided into two. Subsequently, the tuple having a key value between 1-50 is stored in the original page 3c, and the tuple having a key value between 51-100 is stored in the other page 3d. A disk 2f is constituted of the tuple of a relation to which its tuple selected in order to store a page 3d belongs, and its number of pages is the smallest. After the page has been divided, a clustered index is reorganized, an operation for determining the disk device to be stored, and the page is repeated, and unless the page is full, the tuple is stored in the determined page.

Description

[Detailed Description of the Invention] r Industrial Application Field] This invention is a book related to a database storage method in a relational database management system.

(Prior Art) In a relay serial database management system, a database is a collection of tables as shown in FIG.

Each table is called a relation (5), each item in the nine tables is called an atto IJ butte (6), and one record that actually contains data in each attribute is called a double (7).

Next, a plurality of data processing devices i 1 as shown in FIG.
In a relay serial database management system that operates on a system in which disk devices 8al to 8d are connected to a plurality of disk devices 12g) to 2j via a network (9), one By dividing and storing data in multiple disk devices (2g) to (2J), multiple data processing devices t8aJ to 18d) J
't, relation data stored in the disk devices 12g) to 12j) can be accessed in parallel. At this time, divide the relation horizontally into double units.1. This process is called horizontal partitioning.

In this horizontal partitioning, if the storage partition does not have a clustered index, when each double is inserted, it is stored in the disk device that holds the least amount of doubles at that time. Then, the relation can be stored in such a way that the amount of doubles that each disk device has for that relation is approximately equal.

If the relations are divided equally in this way, a plurality of data processing devices (8a) to (8d) will be divided into each disk device (8a) to (8d).
From 2g) to (2j), 11 can read data in equal time, so even if one data processing device has already finished reading the data, another data processing device has not finished reading the data yet. This eliminates this problem, and the processing speed can be improved.

Problems to be Solved by the Invention] The conventional horizontal partitioning method is configured as described above, but since this is a partitioning method for relations that do not have a clustered index, By using a clustered index, which cannot be partitioned.

There is a problem in that it is not possible to implement processing that allows high-speed access to doubles within a relation.

This invention was made to solve the above-mentioned problems, and aims to provide a horizontal database partitioning method that can evenly partition relations with clustered indexes.

(Means for Solving the Problems) The database horizontal partitioning method according to the present invention is B-
This is a trap when storing a relation with a clustered index consisting of a tree on multiple disk devices, and when a physical page in the disk device becomes a cup due to the double of that relation, the page is divided into two. One of the pages divided into 9 parts,
The database can be evenly divided horizontally by storing the pages that hold doubles for each relation in the disk device that has the least number of pages.

[Effect]

In the horizontal database partitioning method of this invention, when a double of a relation with a clustered index is stored in a disk device, the page storing the double is full.

By dividing a page into two, storing the double in one of them, and then sending one page to the disk device with the least number of pages, the number of doubles automatically stored in the disk device is approximately equal. Maintain a certain division state.

C Embodiment of the Invention] Hereinafter, an embodiment of the invention will be described with reference to the drawings. @1
In the figure, (1) is a clustered index. Clustered index is * Computer
Copyrighted by 5science Press Inc.
ple of Database Systems'
It is explained in Section 2.4 of ``Principles of Database Systems'' (Japanese translation, copyright of the Japan Combiator Association, translated by Toshiyasu Kunii). In an index composed of a B-tree, each double of a relation with a clustered index is physically stored based on the value of a) +7 pietes, where the clustered index is specified. are also sorted.

Each double is in a page (3a) to (3e) which is a physical storage unit of the disk drive K 12a) to (2d).

They are stored in the order they were noted. In Figure 1, l-
t7 shows an example of storage when a clustered index is attached to an integer value in the range of 1000. Page (2a) (3
In a), a double with a key value between 73 and 186 is
It is stored on the disk installation @ t2bl page (Ko City). In this way, if a double key value is specified, the disk device and page are determined by the pointer (41) of the clustered index.

When storing doubles of a relation with a clustered index on a disk device.

As shown in the flowchart in Figure 5, the disk device and page to be stored are determined by referring to the clustered index by the double key value υ+101), and the
After storing the double in the page, it is investigated whether the page overflows (102).If the double is stored in the page, the contents of the page are divided into two if the page overflows. One of the divided pages is transferred to the disk device with the smallest number of doubles +103). ! Figure 2 shows this situation, and the page (3c
) stores a double with an integer key value between 1 and 1000, and if you try to store a double with a value between 1 and 100 on this page (3c), the page is full, so , 2 parts and 1 original page 13c) K Fi
This shows that doubles with key values between 1 and 50 are now stored in the other page (3d), and doubles with key values between 51 and 100 are now stored. The disk device (2f) is selected to store the page (3d) and has the least number of pages composed of doubles of the relation to which the double belongs. After dividing the page, reorganize the clustered index104
), the operations from step +1011 are repeated. In step (1021), if it is detected that the page does not overflow, the double is stored in the page determined in step (101).

In the above embodiment, a system configuration was described in which the disk devices (2g) to (2j) and the data processing devices 18a) to (8d) are connected by a network (9) as shown in FIG. , this network (
The shape WA of 9) may be, for example, a ring type or a single bus type, and in general, if it is similar to these, it will have the same effect as the above embodiment.

(Effects of the Invention) As described above, according to the present invention, relations can be horizontally divided evenly even when a clustered index is provided, so that multiple data processing devices can process multiple disks. In a system that allows devices to be accessed simultaneously, in addition to high-speed processing using cluster indexes, each data processing device can read data in the same amount of time during all-record search processing, reducing the overall time to a minimum. This has the effect of being able to read data with .

[Brief explanation of the drawing]

FIG. 1 is an explanatory diagram showing an example of how a relation with a clustered index is divided according to an embodiment of the present invention, FIG. 2 is an explanatory diagram showing an example of page division according to an embodiment of the present invention, and FIG. FIG. 4 is an explanatory diagram showing an example of a relation in a relational database, FIG. 4 is an explanatory diagram showing an example of a system configuration necessary to implement this invention, and FIG. 5 is a flowchart of a program according to an embodiment of this invention. FIG. , (1+1i cluster index, (2aJ to (2f) are disk devices, 13a) to (3e) are pages, (4) is an index pointer, (5) is a relation, (6
) Company Attribute, (7] is double, (8al~
(8d) is a data processing device, and (9) is a network. Note that the same reference numerals in Figure 9 indicate the same or corresponding parts.

Claims (1)

[Claims] In a relational database management system in which one relation in a database is horizontally divided into double units and stored on multiple disk devices, when a relation with a clustered index is stored on multiple disk devices, the disk When a physical page in the device becomes full with doubles for that relation, the page is split into two, and one of the pages is used as the page that holds the double for that relation. A database horizontal partitioning method characterized in that the amount of doubles stored in each disk device is made almost equal by storing data in the smallest disk device.