Index processing method and computer systems

• US 20080114787A1
• Filed: 01/29/2007
• Published: 05/15/2008
• Est. Priority Date: 11/15/2006
• Status: Active Grant

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Kashiyama, Toshihiko, Nishizawa, Itaru
• Granted Patent: US 7,941,413 B2
• Time in Patent Office: Days
• US Class Current: 707/100
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2272 Management thereof

Abstract

Provided is an effective index processing method for a key corresponding to characteristics of a key series. The index processing method includes: holding a key tendency for representing the characteristics of the key series and a node split ratio, corresponding to the key tendency, for representing a key split ratio at the time of node split; and switching the node split ratio of an index (162) based on the key tendency. The key tendency/distribution is determined based on characteristic information of data input by a user or monitoring information acquired through monitoring of the data.

Claims

1. An index processing method for inserting a key into an index of a tree structure including keys respectively indicating data input into a computer and nodes for storing the keys, the index being used for searching for the data associated with the key, comprising the steps of:

identifying the node to which the key is to be inserted;

determining whether the number of keys stored in the identified node exceeds a predetermined key storage upper limit or not; and

upon the number of the keys exceeding the key storage upper limit, splitting the identified node into a first node and a second node,

wherein the step of splitting the node includes the step of changing a ratio for splitting the keys stored in the identified node into the keys to be stored in the first node and the keys to be stored in the second node.

2. The index processing method according to claim 1, wherein the step of changing the ratio of the split includes a key tendency determination step of determining a key tendency representing a characteristic of a value of the key to be stored in the node, and a node split ratio determining step of determining the node split ratio based on the key tendency.

3. The index processing method according to claim 2, wherein the step of changing the ratio of the split includes the steps of:

acquiring the key tendency; and

acquiring the split ratio corresponding to the key tendency.

4. The index processing method according to claim 2, wherein the step of changing the ratio of the split includes the steps of:

acquiring time information; and

acquiring the key tendency corresponding to the time information.

5. The index processing method according to claim 2, further comprising the step of monitoring data corresponding to a key to be inserted into the index, and acquiring data monitoring information, wherein the key tendency determination step calculates a predicted value of the key tendency based on the data monitoring information, and determines the predicted value as the key tendency.

6. The index processing method according to claim 5, wherein the data monitoring information retains a change of value of the data corresponding to the key to be inserted as a key series, and the key tendency determination step, upon the key series increasing as a whole, determines that the key tendency is an increase tendency, upon the key series decreasing as a whole, determines that the key tendency is a decrease tendency, and, upon the key series not being either increasing or decreasing, determines that the key tendency is a random tendency.

7. The index processing method according to claim 6, further comprising the step of storing the keys stored in the identified node in the first node and the second node based on the split ratio, wherein the node split ratio determination step, upon the key tendency being the increase tendency or the decrease tendency, sets a split ratio for differentiating the number of the keys to be stored in the first node and the number of the keys to be stored in the second node, and the split ratio, upon the key tendency being the increase tendency, sets the number of the keys to be stored in the first node larger than that upon the key tendency being the decrease tendency.

8. The index processing method according to claim 2, wherein the node split ratio determination step acquires the key tendency, a node position representing the position of the node to which the key is to be inserted in the index, and the split ratio corresponding to the key tendency and the node position, and sets the acquired split ratio as the node split ratio.

9. The index processing method according to claim 2, wherein the node split ratio determination step, upon the key tendency being the increase tendency or the decrease tendency, determines the split ratio based on the key tendency, the key storage upper limit, and a key insertion position representing a position of a newly inserted key within the node.

10. The index processing method according to claim 2, further comprising the step of monitoring the index, and acquiring a state of the index as index monitoring information, wherein:

the index monitoring information includes time information; and

a split ratio set to a node of the index and the node split ratio determination step sets a split ratio of the index corresponding to the time information of the index monitoring information.

11. The index processing method according to claim 10, wherein the node split ratio determination step includes the steps of:

narrowing down the node split ratio information based on time conditions relating to the time information;

upon a external attribute conditions relating to attribute information stored in an external recording medium being present, further narrowing down; and

upon a narrowed down result being present, setting to a node split ratio with the highest frequency.

12. An index processing method for splitting a node if a predetermined key storage upper limit is exceeded when a key is inserted in the node of an index, wherein the index includes a reading order flag indicating whether an order to assign the keys to respective addresses of a page is forward or reverse, comprising the steps of:

determining whether the reading order flag of a node of the index indicates the forward order or reverse order;

upon the reading order flag indicating the forward order, comparing the magnitude of the keys from the head of the node;

upon the reading order flag indicating the reverse order, comparing the magnitude of the keys from the tail of the node;

determining whether the node of the index is a leaf node or not;

upon the node being not a leaf node, jumping to a child node to repeat the previous steps until reaching a leaf node; and

upon the node being not a leaf node, identifying a position indicating a key insertion position in the node.

13. The index processing method according to claim 12, further comprising:

a key tendency determination step of determining a key tendency representing a characteristic of a key series to be inserted in the index,

wherein a step upon a key being inserted in the index includes the steps of;

determining whether a node split occurs in the node, a step of producing new nodes;

determining whether the key tendency of the key series to be inserted is a monotonic decrease or not a monotonic decrease but a general decrease as a whole or not;

upon the key tendency being the decrease tendency, setting the reading order flag to the reverse order;

upon the key tendency not being the decrease tendency, setting the reading order flag to the forward order;

moving keys to new nodes, and updating pointers of a parent node;

jumping to the parent node, and determining whether a node split occurs in the parent node or not; and

repeating the previous steps until a node split does not occur in the parent node.

14. An index processing method for splitting a node if a predetermined key storage upper limit is exceeded when a key being inserted in the node of an index, comprising the steps of:

monitoring data corresponding to a key to be inserted into the index, and acquiring data monitoring information;

monitoring the index, and acquiring a state of index as index monitoring information;

acquiring the number of splits in a node of the index based on the data monitoring information and the index monitoring information; and

upon the number of the splits exceeding a predetermined threshold in the index, determining that the split of the node has occurred frequently.

15. The index processing method according to claim 14, wherein the step of determining the frequent node split includes the steps of:

calculating a predicted number of splits in the node within a predetermined period based on the data monitoring information;

acquiring the split number of the node which have occurred in the index within the predetermined period based on the index monitoring information; and

determining that, upon a ratio of the number of the splits of the node which have occurred to the predicted number of the splits exceeding a predetermined value, the split of the node has frequently occurred.

16. The index processing method according to claim 14, further comprising the steps of, upon determination of the frequent split of the node, acquiring again the data monitoring information,

wherein the key tendency determination step calculates a predicted value of the key tendency based on the data monitoring information acquired again, and determines the predicted value as the key tendency.

17. A machine-readable medium embodying a program for causing a computer to execute index processing for inserting a key into an index of a tree structure including keys respectively indicating data input into the computer and nodes for storing the keys, the index being used for searching for data associated with the key, wherein the program causes the computer to execute the procedures of:

identifying the node to which the key is to be inserted;

determining whether the number of keys stored in the identified node exceeds a predetermined key storage upper limit or not; and

upon the number of the keys exceeding the key storage upper limit, splitting the identified node into a first node and a second node, and

wherein the process for splitting the node includes a key tendency determination process for determining a key tendency representing a characteristic of a value of the key to be stored in the node, and a process for determining a split ratio for splitting the keys stored in the identified node into the keys to be stored in the first node and the keys to be stored in the second node.

18. A computer system provided with a processor, a storage system, and an interface, including a data area set in the storage system for storing data input via the interface, and an index area set in the storage system for storing an index of a tree structure, including keys respectively indicating items of the data, and nodes for storing the keys, the index being used for searching for data associated with the key, the processor inserting a key corresponding to the input data into the index, comprising:

an insertion position identifying unit for identifying the node to which the key is to be inserted;

a node split determination unit for determining whether the number of keys stored in the identified node exceeds a predetermined key storage upper limit or not; and

a node splitting unit for, upon the number of the keys exceeding the key storage upper limit, splitting the node into a first node and a second node,

wherein the node splitting unit includes a key tendency determination unit for determining a key tendency representing a characteristic of a value of the key to be stored in the node, and a split ratio determination unit for determining a split ratio for splitting the keys stored in the identified node into the keys to be stored in the first node and the keys to be stored in the second node.

19. The computer system according to claim 18, further comprising a data monitoring unit for monitoring data to be stored in the data area to acquire data monitoring information, wherein the key tendency determination unit calculates a predicted value of the key tendency based on the data monitoring information, and determines the predicted value as the key tendency.

20. The computer system according to claim 18, further comprising:

an index monitoring unit for monitoring the index area, and acquiring a state of the index as index monitoring information;

a split number acquiring unit for acquiring the number of splits in a node of the index based on the data monitoring information and the index monitoring information; and

a frequent split detecting unit for, upon the number of the splits exceeding a predetermined threshold in the index, determining that the split of the node has occurred frequently.