CN100468402C - A data storage and query method - Google Patents

Abstract

Disclosed is a data storage method, which classifies the data at least once, obtains classified data and classification directories of all levels of the classified data, stores the classified data in the memory space of a computer; adopts a binary structure directory tree Storing the classification directories at all levels of the classification data, storing each node on the directory tree with a fixed-size memory space, and using a recursive algorithm to respectively establish one-to-one corresponding nodes with the classification directories at all levels of the classification data; A mapping table is generated in the memory, and the mapping relationship between the node identifier of the node and the pointer pointing to the memory space where the node is located is saved in the pre-generated mapping table when each node is established. The invention also discloses a data query method. The above method can effectively save memory space, increase the utilization efficiency of memory resources, and simplify the storage of classified data and the operations of moving, adding and deleting classified directories.

Description

A data storage and query method

technical field

The invention relates to data management technology, in particular to a data storage and query method.

Background technique

With the explosive growth of current data information and the continuous expansion of computer applications, computers have become an indispensable data management tool in people's lives. No matter data collection, processing, storage, retrieval, etc., operations are inseparable from computers. Therefore, How to store data effectively and quickly and how to quickly retrieve the required data has become the main problem to be solved in current data management.

At present, classification data can usually be stored in a tree structure, and the tree structure storing these classification directories is also called a directory tree. The method for using a directory tree to store classified data includes: first establishing a root node, which contains at least one first-level child node, and the number of said first-level child nodes is based on the first-level classification directory obtained after the classification data is classified once Depending on the number of , each sub-node corresponds to a first-level classification directory, and information such as the name or logo of the first-level classification directory is recorded. Wherein, each first-level child node can further include at least one second-level child node, and correspondingly, each second-level child node will correspond to the second-level data obtained after classification of the data contained in the first-level classification directory corresponding to its parent node. The first-level classification directory records information such as the name of the second-level classification directory. Going on in this way, several n-level child nodes are obtained (n described here is a natural number), and the n-level classification catalogs corresponding to these n-level child nodes will not be able to be further classified. At this time, these n-level Sub-nodes are called leaf nodes. In addition to recording the name or logo of the corresponding n-level classification directory, these leaf nodes need to further store the classification data contained in the corresponding n-level classification directory.

Figure 1 shows a commodity catalog stored using the above catalog tree. It can be seen from Fig. 1 that after one classification of various commodity data, several first-level classification directories are obtained, such as computer, jewelry, mobile phone, etc., which will correspond to each first-level child node of the directory tree shown in Fig. 1; The commodities contained in each first-level classification catalog can be further classified into several second-level classification catalogs. For example, the computer catalog can be further divided into categories such as notebooks, desktop computers, and office equipment. Corresponding to each secondary child node of the directory tree shown in FIG. 1 . For catalogs that cannot be further classified, such as IBM or DELL, etc., they will correspond to the leaf nodes of the catalog tree shown in Figure 1. In addition to storing the name or logo of the corresponding catalog on the above leaf nodes, the It further stores various commodity information contained in its corresponding classification catalog, such as various commodity information of IBM notebook computers or various commodity information of DELL notebook computers.

The above tree structure can clearly indicate the classification relationship between the classification directories at all levels, so as to realize the effective management of the classification data. However, since the above-mentioned directory tree actually adopts the data structure of a multi-fork tree, the number of sub-nodes contained in each node in the multi-fork tree will correspond to the number of sub-directories divided by the directory corresponding to the node. Therefore, each The number of sub-nodes contained in a node is uncertain, or unpredictable, which will cause the size of the storage space required by each node on the directory tree to be uncertain, resulting in the allocation of storage space during the data storage process too complicated. Especially when the above storage method is applied to the management of massive data, such as catalog management in e-commerce, and library information management, etc., due to the huge amount of information contained in massive data, each node If the number of sub-nodes is too large, the information stored in each node will be too large, which will not only further increase the complexity of the storage space allocation operation, but also cause a waste of storage space resources.

In addition, when the classification relationship of the classification data stored by the multi-fork tree structure directory tree changes, for example, when adding, moving or deleting a certain classification directory, it is also necessary to consider the allocation and recovery of the storage space of the parent node of the classification directory, etc. The problem makes the addition, deletion and movement of categories very complicated.

Contents of the invention

In order to solve the problems existing in the prior art, the present invention provides a data storage method, which can effectively save memory space, and simultaneously simplify the storage of classified data and the operations of moving, adding and deleting classified directories.

The invention also provides a data query method, which can quickly retrieve the classification directory to be queried, and obtain the classification data contained in the classification directory.

A data storage method, which classifies the data at least once, obtains the classified data and classification directories of the classified data at all levels, and stores the classified data in the memory space of the computer; adopts a binary structure directory tree to store all the classified data Classification catalogs at all levels of the classification data, each node on the catalog tree is stored in a fixed-size memory space, and each node at least includes a node identifier, a child node pointer, and a brother node pointer of the classification catalog corresponding to the node And data pointer; A, set up the root node of described catalog tree, make the sibling node pointer of this root node be empty, data pointer be empty, and set up a new node, make the child node pointer of described root node point to the established A new node of the new node corresponding to a first-level classification directory of the classification data; B, using a recursive algorithm to respectively establish a node corresponding to each level of classification directory of the classification data, corresponding to each node, if the If the classification directory corresponding to the node contains the next-level classification directory, then make the child node pointer of the node point to a node corresponding to the lower-level classification directory of the corresponding classification directory of this node, and make the node data pointer empty, otherwise , make the child node pointer of the node empty, and make the node data pointer point to the memory space used to save the classification data contained in the classification directory corresponding to this node; if the directory tree already contains the corresponding If all the nodes of the category directory are at the same level as the category directory, the sibling node pointer of the node is empty; otherwise, the sibling node pointer of the node points to a directory of the same level corresponding to the category directory corresponding to this node and is not included in the Nodes in the directory tree; generate a mapping table in memory in advance, and save the mapping between the node ID of the node and the pointer to the memory space where the node is located in the pre-generated mapping table when each node is established relation.

The described step B utilizes the recursive algorithm to set up all the nodes corresponding to all classification catalogs of the classification data in the catalog tree including the following steps:

C. Let the newly created node be the current node, and judge whether the classification directory corresponding to the current node has a next-level classification directory. If so, set the data pointer of the current node to be empty, and then create a new node. The child node pointer of the node points to the new node established in this step, and the new node is set to correspond to a subcategory of the category directory corresponding to the current node, and then returns to step C; otherwise, the child node of the current node is set The pointer is empty, and the data pointer of the current node points to the memory space used to save the classification data contained in the classification directory corresponding to the current node, and then step D is executed;

D: judge whether the classification directory corresponding to the current node has a classification directory of the same level that has not been added to the directory tree, if so, then establish a new node, and make the sibling node pointer of the current node point to the new node established in this step , and set the new node to correspond to a category directory at the same level that is not added to the directory tree corresponding to the category directory corresponding to the current node, and then return to step C; otherwise, return to the previous category directory of the category directory corresponding to the current node Corresponding node, and judge whether this node is the root node, if yes, then end, otherwise, make this node the current node, and return to this step D.

The method of the present invention further includes adding classification data to a certain classification directory, specifically:

A1: find the node corresponding to the classification directory in the directory tree according to the classification directory to be added;

A2: the first pointer element of the pointer array pointed to by the node data pointer is set as the current pointer element;

A3: Determine whether the memory space pointed to by the current pointer element is empty, if so, apply for a fixed-size memory space from the memory, and make the pointer element point to the newly applied memory space, and then execute A4; otherwise, judge the current pointer Whether the memory space pointed to by the element is full, if yes, set the current pointer element as the next pointer element of the pointer array, and then return to this step; otherwise, execute step A4;

A4: Add the classification data information to be added in the memory space pointed to by the current pointer element.

Based on the data storage method of the present invention, the present invention also provides a data query method, wherein the classified data obtained after the data is classified at least once are stored in the memory space of the computer; Each level of classification directory of classification data obtained after the data has been separated at least once, each node on the directory tree occupies a fixed size of memory space, and at least includes a node identifier of the classification directory corresponding to the node, a child node pointer, Brother node pointers and data pointers; generate a mapping table in memory in advance, and save the relationship between the node ID of the node and the pointer pointing to the memory space where the node is located in the pre-generated mapping table while establishing each node Mapping relationship; including:

a. Find the node corresponding to the classification directory to be queried in the directory tree according to the mapping table;

b. Determine whether the child node pointer of the node is empty, if so, add the node into a container, and then perform step d; otherwise, perform step c;

c. Read all the leaf nodes contained in the entire left branch of the node through a recursive algorithm, and add all the leaf nodes read into a container in turn, and then execute step d;

d. Read the leaf nodes sequentially from the container, obtain all classified data stored in the memory space according to the memory space pointed to by the read leaf node data pointer, and return them to the user.

When the present invention establishes each node, the node identification of each node is made the classification identification of the classification directory corresponding to the node;

Finding the node corresponding to the classification directory to be queried in the directory tree according to the mapping table in step a includes:

a1. According to the classification identification of the classification directory to be queried, find a pointer to the memory space where the corresponding node is located in the mapping table;

a2. Directly locate the node corresponding to the classification directory to be queried and browsed through the pointer.

It can be seen from this that using a binary directory tree to replace the existing multi-fork directory tree to store classification information can obtain the following beneficial effects:

First of all, since the size of each node of the binary directory tree is fixed and occupies a small space, using a binary directory tree to store classified information can greatly save memory resources, so that the memory can store more classified data and improve memory storage efficiency.

In addition, due to the simple operation algorithm of the generation of the binary tree and the movement, addition, and deletion of nodes, the overhead is small, and in the process of a node being moved, added, or deleted, there is no need to consider the allocation and recycling of its parent node storage space. , making it easy to manage classified data using a binary directory tree.

Description of drawings

FIG. 1 is a schematic diagram of a commodity catalog stored in an existing multi-fork tree structure catalog tree;

Fig. 2 is the structural representation of each node in the catalog tree that the preferred embodiment of the present invention adopts;

Fig. 3 is the flow chart of the classification data storage method based on directory tree described in the preferred embodiment of the present invention;

Fig. 4 is a schematic diagram of a commodity catalog stored in a catalog tree according to a preferred embodiment of the present invention;

Fig. 5 is the flow chart of the method for querying and browsing the classification data contained in a certain classification directory in the binary directory tree described in the preferred embodiment of the present invention;

Fig. 6 is a flowchart of a method for adding classified data in a certain classification directory of the binary directory tree according to the preferred embodiment of the present invention.

Detailed ways

In order to make the object, technical solution and advantages of the present invention clearer, the present invention will be further described in detail below with reference to the accompanying drawings and examples.

Considering that the binary tree is a data structure widely used for data search, its generation and node search algorithms are relatively mature, and the convergence speed is fast, so the core idea of the present invention is to use the binary tree structure to store classified data.

A preferred embodiment of the present invention provides the structure of each node in the binary tree structure directory tree (binary directory tree for short) that is used to store classification data, as shown in Figure 2, each node contains the information used to identify the node The node identifier (ID) corresponding to the classification directory, a child node pointer pointing to the next-level child node of the node, a sibling node pointer pointing to another node in the same-level node of the node, and a pointer pointing to the memory space used to save the classification data data pointer.

The method described in a preferred embodiment of the present invention uses above-mentioned binary directory tree to store classification data as shown in Figure 3, mainly comprises the following steps:

A: Establish a root node, that is, open up a space in the memory to store the node ID of the root node, its child node pointer, sibling node pointer and data pointer, set the node ID of the root node to 0, and make its sibling node pointer empty (NULL), the data pointer is also NULL.

B: set up a new node, make the child node pointer of described root node point to the new node that this step is set up, and make the node ID of described new node be the classification mark of a first-level classification list.

The classification identifier described here is a predetermined identifier that can uniquely identify each classification catalog of the classification data. For example, in this embodiment, the classification identifier of the first-level classification computer in the commodity catalog described above is 1, The classification logo of jewelry is 2, the classification logo of mobile phone is 3; the classification logo of notebook in the second-level classification directory is 11, and the classification logo of desktop computer is 12; the classification logo of IBM in the third-level classification directory is 111, and the classification logo of DELL is 112 and so on. In this way, by setting the ID of the current node as the classification identifier of a certain classification directory, the current node can be associated with a classification directory. It should be noted that, in the present invention, the identification of each category can be in any form, as long as each category can be uniquely identified, and is not limited to the form given in the above-mentioned preferred embodiment. In this step, setting the node ID of the new node as a classification identifier of a first-level classification directory is essentially to associate the new node with a first-level classification directory.

The method of establishing a new node described in this step is the same as that of establishing a root node described in step A, that is, open up a space in memory to store the node ID, child node pointer, sibling node pointer and data pointer of the node.

In subsequent steps, a binary directory tree for storing the classified data will be created through a recursive algorithm, specifically including:

C: Let the new node be the current node, judge whether the classification directory corresponding to the current node has a next-level classification directory, and if so, execute step D; otherwise, execute step E.

D: set the data pointer of the current node to be NULL, then set up a new node, make the child node pointer of the current node point to the new node established in this step, and set the node ID of the new node to be the corresponding classification directory of the current node The classification identifier of a classification directory in the next-level classification directory, that is, the new node corresponds to a lower-level classification directory of the classification directory corresponding to the current node, and then return to step C.

In this step, if the current node corresponds to an n-level classification directory, the node ID of the new node will be the classification identification of an n+1-level classification directory contained in the n-level classification directory, such as the current node Corresponding to the notebook of the second-level classification directory, the node ID of the new node may be the classification identification 111 of the third-level classification directory IBM or the classification identification 112 of the third-level classification directory DELL.

E: set the child node pointer of the current node as NULL, and point the data pointer of the current node to the memory space for saving the classification data contained in the corresponding classification directory of the current node, and then perform step F.

The memory space used for storing the classification data contained in the classification directory corresponding to the current node described in this step can be a memory space of any size and can be dynamically expanded.

In another preferred embodiment of the present invention, in order to facilitate memory resource management, an array of pointers can be further set in this step, and the data pointer of the current node is pointed to the array of pointers, wherein each pointer of the pointer data The elements will respectively point to a memory space of a fixed size, and the memory space of a fixed size will be used to record the classification data contained in the classification directory corresponding to each leaf node. The number n of pointer elements contained in the pointer array can be preset according to the number of classified data, for example, 10, so that each leaf node can have 10 memory spaces with a fixed size. But instead of applying for n blocks of memory space for each leaf node when it is created, it is allocated on demand. When a memory space is full, the next memory space will be applied for, and each time The application allocates only one piece of memory space. The above-mentioned method of using fixed-size memory space and on-demand allocation is mainly to improve memory allocation efficiency and effectively avoid the dynamic expansion of memory space required when storing classified data in a memory space of any size.

F: Judging whether all the same-level directories of the classification directory corresponding to the current node have not added in the binary directory tree, if so, then perform step G; otherwise, perform step H.

G: set up a new node, make the sibling node pointer of current node point to the new node that this step is set up, and the node ID of described new node is set to be that one of current node's corresponding classification directory does not add in this binary directory tree The classification identifier of the same-level directory of the current node, that is, the new node corresponds to a same-level category directory of the category directory corresponding to the current node, and then returns to step C.

In this step, if the current node corresponds to an n-level classification directory, the node ID of the new node will be the classification identifier of another n-level classification directory that has not been added to the binary directory tree, such as the current node Corresponding to the notebook of the secondary classification directory, the node ID of the new node can be the classification identification 12 of the desktop computer of the secondary classification directory or the classification identification 13 of the office equipment of the secondary classification directory that has not been added to the binary directory tree.

H: return to the node corresponding to the upper level classification directory of the corresponding classification directory of the current node, and judge whether the node is the root node, if so, then end; otherwise, perform step 1.

I: make this node the current node, and return to step F.

By executing the above steps A-I, the binary directory tree for storing classified data has been established, and all nodes of the binary directory tree will be in one-to-one correspondence with all classified directories of the classified data. FIG. 4 shows a schematic diagram of a commodity catalog stored in the above-mentioned binary catalog tree. As shown in Figure 4, the child node pointer of the root node will point to a first-level classification directory obtained after one classification of various commodity data, such as the first-level child node corresponding to the computer directory. The child node pointer of the first-level child node will point to a second-level classification directory obtained by secondary classification of the first-level classification directory, such as the second-level child node corresponding to the notebook directory; and its brother node pointer will point to another first-level classification directory , such as the first-level child node corresponding to the jewelry category, and so on. The leaf nodes in the above-mentioned binary directory tree, for example, the data pointers corresponding to the nodes of classification directories such as IBM or DELL will point to a pointer array, and the pointer elements of the pointer array will point to the memory space for storing the commodity information contained in each classification directory, That is, a block of physical memory.

Below in conjunction with Fig. 5, describe in detail the method for inquiring about the classification data contained in a certain classification directory in the above-mentioned binary directory tree, as shown in Fig. 5, the method mainly includes the following steps:

a1. According to the classification identification of the classification directory to be queried or browsed, find the node corresponding to the classification directory in the binary directory tree;

Since the node ID of each node is exactly the classification identification of the corresponding classification directory of this node, the method for searching for the corresponding node described in this step can be to use the ID of the classification directory as an index to traverse the binary directory tree to find the classification directory the corresponding node;

a2. Determine whether the child node pointer of the node is NULL, if yes, execute a3; otherwise, execute step a4;

a3. Add the node to a container, and then perform step a5;

The container described in this step is a temporary memory space for temporarily storing leaf nodes;

a4. Read all the leaf nodes contained in the entire left branch of the node through a recursive algorithm, and add all the leaf nodes read into a container in turn, and then execute step a5;

a5. Read the leaf nodes sequentially from the container, obtain all classified data stored in the memory space according to the memory space pointed to by the read leaf node data pointer, and return them to the user.

If the data pointer of the leaf node of the above-mentioned binary directory tree points to a pointer array, it is necessary to further find the memory space for storing classified data through the pointer array in step a5.

Next, the method of adding classified data in the above binary directory tree will be described in detail, for example, the method of adding certain commodity information to a classified directory.

If the data pointer of the leaf node of the above-mentioned binary directory tree points to a memory space of any size and can be dynamically expanded, then at first find the node where the classification directory is located according to the classification identification of the classification directory to be added; The added classification data is added to the memory space pointed to by the node data pointer. If the memory space is full, it is necessary to expand the memory space pointed to by the node data pointer through the memory dynamic expansion operation first.

If the data pointer of the leaf node of the above-mentioned binary directory tree points to a pointer array, the following steps need to be performed, as shown in Figure 6:

b1: find the node where the classification directory is located in the binary directory tree according to the classification identification of the classification directory to which the classification data will be added;

The method adopted in this step is the same as the method described in step a1;

b2: set the first pointer element of the pointer array pointed to by the node data pointer as the current pointer element;

b3: judge whether the memory space pointed to by the current pointer element is NULL, if yes, then execute step b4; otherwise, execute step b6;

b4: Apply for a memory space of a fixed size to the memory, and make the pointer element point to the newly applied memory space, and then perform step b5;

b5: Add the classification data information to be added in the memory space pointed to by the current pointer element, and then end;

b6: judge whether the memory space pointed to by the current pointer element is full, if yes, then execute step b7; otherwise, execute step b5;

b7: Set the current pointer element as the next pointer element of the pointer array, and then return to step b3.

In this step, if the current pointer element is the last pointer element of the pointer array, and the memory space it points to is full, then corresponding classification data cannot be added to the current directory tree, and an error message should be returned to the user.

It can be seen from the above preferred embodiments that since the size of each node of the binary directory tree is fixed and occupies very little space, using a binary directory tree instead of a multi-fork directory tree to store classification information can greatly save memory resources , so that more classified data can be stored and higher storage efficiency can be obtained. In addition, due to the simple algorithm and low overhead of the generation of the binary tree and the movement, addition, and deletion of nodes, and in the process of moving, adding, or deleting a node, only the pointer of its parent node needs to be modified without considering The allocation and recycling of the storage space of its parent node makes it easy to manage classified data using a binary directory tree, and it is possible to point to the change operation of the classified directory under the normal operating environment of the system without downtime.

After testing, in an actual application, if there are 10 million items and a total of 2,000 smallest classification directories, using the above-mentioned binary directory tree method, the possible nodes in the system, including leaf nodes and non-leaf nodes, are 3,000 in total. , the space occupied by each node is about 16 bytes (the node ID, child node pointer, sibling node pointer and data pointer each need 4 bytes), and each product only needs 4 characters when only storing the product ID node storage space, then the total memory space required by all nodes and commodities is about 3000×16+10,000,000×4=40.048 megabytes. It can be completely stored in the computer memory space, which can greatly improve the retrieval efficiency of data.

In the method of querying and browsing the classification data contained in a certain classification directory in the above-mentioned binary directory tree and the method of adding classification data in the binary directory tree, it is necessary to first traverse the binary directory tree according to the classification identification of the classification directory The method to find the node where the classification directory is located, this traversal operation will consume more time.

In order to facilitate the search for each classification directory, another preferred embodiment of the present invention pre-generates a mapping table of the node ID of the corresponding node of the classification directory and the pointer to the physical memory block where the node is located in memory, and executes the above steps A to I to generate In the process of the binary directory tree, further perform the following operations in step C: save the mapping relationship between the node ID of the current node described in step C and the pointer pointing to the memory space where the current node is located in the pre-generated mapping table.

In this way, since the node ID of each node is exactly the classification identifier of the corresponding classification directory of the node, the method of querying and browsing the classification data contained in a certain classification directory in the above-mentioned binary directory tree and in the binary directory tree In the method for adding classified data, at first directly according to the classification identification of the classification directory to which the classification data will be added, the node ID of the node corresponding to the classification directory and the mapping table pointing to the physical memory block pointer where the node is located can be found pointing to the classification The pointer of the memory space where the node corresponding to the directory is located, and then directly locate the node corresponding to the classification directory through the pointer, without traversing the binary directory tree. For example, there are now 10 million items distributed under 1,000 leaves, so that there are 10,000 items under each leaf node on average. If the user needs to browse a category, which contains 200,000 items, the node corresponding to the category can be directly located through the mapping relationship between the pre-saved node ID and the pointer to the memory space where the node is located. , therefore, the total number of products to be retrieved by the system is only 20W, without filtering from the entire 10 million products, and every time the user chooses to search for the next level of classification, the total number of products to be retrieved will decrease rapidly, thereby greatly The search efficiency of nodes is improved, and the management efficiency of classified data is further improved.

Claims (8)

1. a date storage method is characterized in that, comprising:

Described data are at least once classified, obtain the split catalogs at different levels of grouped data and described grouped data, described grouped data is stored in the memory headroom of computing machine;

Adopt the split catalogs at different levels of the described grouped data of y-bend structure category tree storage, store each node on the described directory tree with the memory headroom of fixed size, described each node comprise at least this node node identification, child nodes pointer, brotgher of node pointer and the data pointer of corresponding split catalog;

A, set up the root node of described directory tree, the brotgher of node pointer that makes this root node is for empty, data pointer is empty, and set up a new node, the new node that makes the child nodes pointed of described root node be set up is with the one-level split catalog of described new node corresponding to described grouped data;

B, utilize recursive algorithm to set up respectively and the split catalogs at different levels of described grouped data node one to one, for each node, if the pairing split catalog of this node comprises the split catalog of next stage, one of the child nodes pointed that then makes this node corresponding to this node the node of corresponding split catalog next stage split catalog, and make this node data pointer for empty, otherwise, make this node child nodes pointer for empty, and make this node data pointed be used to preserve the memory headroom of the grouped data that the pairing split catalog of this node comprised; If comprised all nodes in the described directory tree corresponding to corresponding split catalog peer of this node institute split catalog, the brotgher of node pointer that then makes this node is for empty, otherwise, one of the brotgher of node pointed that makes this node corresponding to this node corresponding split catalog catalogue at the same level and be not included in node in the described directory tree;

In internal memory, generate a mapping table in advance, and the mapping relations between the pointer of the node identification of when setting up each node, in the mapping table that generates in advance, preserving described node and this node place memory headroom of sensing.

2. the method for claim 1 is characterized in that, step B is described utilize recursive algorithm in described directory tree, set up with all split catalogs of described grouped data one to one all nodes may further comprise the steps:

C, make that newly-established node is a present node, and judge whether the pairing split catalog of present node has the next stage split catalog, if have, the data pointer that present node then is set is for empty, set up a new node again, the new node that the child nodes pointed that makes present node is set up in this step, and with described new node corresponding to present node a next stage split catalog of corresponding split catalog, return this step C then; Otherwise the child nodes pointer that makes present node is for empty, and the data pointer of present node is pointed to the memory headroom that is used to preserve the grouped data that the corresponding split catalog of present node comprised, execution in step D then;

D: judge whether the pairing split catalog of present node has the split catalog at the same level that does not join in this directory tree, if have, then set up a new node, the new node that makes this step of brotgher of node pointed of present node be set up, and with described new node corresponding to present node a split catalog at the same level that does not join in this directory tree of corresponding split catalog, return step C then; Otherwise, turn back to present node the pairing node of upper level split catalog of corresponding split catalog, and judge whether this node is root node, if then finish; Otherwise, make that this node is a present node, and return this step D.

3. method as claimed in claim 1 or 2, it is characterized in that, the described data pointer that makes node points to the memory headroom that is used to preserve the grouped data that the corresponding split catalog of this node comprised: make the data pointer of node point to an array of pointers, each pointer element of described pointer data will be pointed to the memory headroom of fixed size respectively, and the memory headroom of described fixed size will be used for the grouped data that the pairing split catalog of minute book node is comprised.

4. method as claimed in claim 3 is characterized in that, described method further comprises adds grouped data to certain split catalog, is specially:

A1: in described directory tree, find node that should split catalog according to the split catalog that will add to;

A2: first pointer element that this node data pointer array of pointers pointed is set is current pointer element;

A3: judge that whether current pointer element memory headroom pointed is empty, if, then to the memory headroom of a fixed size of internal memory application, and make this pointer element point to the memory headroom of new application, carry out A4 then; Otherwise, judge whether current pointer element memory headroom pointed is full, if it is the next pointer element of array of pointers that the current pointer element then is set, and returns this step then; Otherwise, execution in step A4;

A4: in the memory headroom of current pointer element directed, add the assortment data information that to add.

5. method as claimed in claim 4 is characterized in that, when setting up each node, makes the class indication of the node identification of each node by the corresponding split catalog of this node;

Steps A 1 is described to find the node at described this split catalog place to comprise according to the split catalog that will add to:

Class indication according to the split catalog that will add finds the pointer that points to its corresponding node place memory headroom in described mapping table;

Directly navigate to the node of the described split catalog correspondence that will add to by described this pointer.

6. a data enquire method is characterized in that, described data are kept in the memory headroom of computing machine through the grouped data that obtains behind at least one subseries; Adopt the at different levels split catalogs of the described data of y-bend structure category tree storage through the grouped data that obtains after the first separation at least, each node on the described directory tree takies the memory headroom of fixed size, and comprise at least this node node identification, child nodes pointer, brotgher of node pointer and the data pointer of corresponding split catalog; In internal memory, generate a mapping table in advance, and the mapping relations between the pointer of the node identification of when setting up each node, in the mapping table that generates in advance, preserving described node and this node place memory headroom of sensing; Comprise:

A, in described directory tree, find the pairing node of the split catalog that to inquire about according to described mapping table;

B, judge that whether the child nodes pointer of this node is empty, if then this node is joined in the container, then execution in step d; Otherwise, execution in step c;

C, read the whole left branch of this node by recursive algorithm and comprise all leaf nodes, and all leaf nodes that will read join in the container successively, then execution in step d;

D, read leaf node successively from described container, the memory headroom according to reading leaf node data pointer points to obtains all grouped datas of storing in the described memory headroom, returns to the user as Query Result.

7. method as claimed in claim 6 is characterized in that, when setting up each node, makes the class indication of the node identification of each node by the corresponding split catalog of this node;

Step a is described to find the pairing node of the described split catalog that will inquire about to comprise in described directory tree according to mapping table:

A1, in described mapping table, find the pointer that points to its corresponding node place memory headroom according to the class indication of the split catalog that will inquire about;

A2, directly navigate to the pairing node of the described split catalog that will inquire about, browse by described this pointer.

8. method as claimed in claim 6 is characterized in that, described container is the interim memory headroom that is used for temporarily depositing leaf node.

Images