WO2011020360A1 - Document storage method - Google Patents

Abstract

A document storage method is disclosed. The method discloses: mapping the content of a document to the tree structure according to the designated document types, in which the type information of each node is defined in the document type; storing the content of each node for constructing the tree structure and the information of the relationship between nodes; recording the storage location of the node data in the node index table; in which the node data comprises the node content; storing the node index table. With the storage method, it can improve the access performance of the document.

Description

Method for storing documents Technical field

 The present invention relates to computer storage technology, and in particular to a method for storing a document.

Background technique

Extensible Markup Language (XML) is a document description language in which documents described in this language are called XML documents.

XML documents have many advantages. XML is a meta-markup language. Developers can define their own tags according to their needs. XML documents are well-defined and structured, and have strong anti-destructive capabilities. The information represented by XML is platform-independent. The platform here can be understood as different applications and can be understood as different operating systems. For large and complex documents, XML not only allows the vocabulary in the specified document, but also allows the specified elements to be between Relationship. An XML document consists of a document type definition (DTD)/schema (Schema) and XML text, DTD/ Schema is a grammar rule for a set of tags, indicating how the XML text is organized. This way of composition makes the XML document realize the separation of content and form, which achieves many of the above advantages.

However, the disadvantage of XML documents is that after storing a document as an XML document, if you want to access an object, you need to first parse the entire document, convert it into a tree structure, and then search for the object to be accessed. Make an access. It can be seen that after the storage method is used to store a certain document, when the user accesses part of the content of the document, the system needs to firstly analyze the entire document by using resources, and then select the content that the user is interested in for display, thereby prolonging the processing time. , which reduces access performance and wastes system resources.

technical problem

In view of this, the present invention provides a method for storing a document, which can improve access performance.

Technical solution

To achieve the above object, the present invention adopts the following scheme:

A method of storing a document, comprising:

Maps the content of the document to a tree structure according to the specified document type; wherein the type information of each node is defined in the document type;

Storing the contents of the nodes constituting the tree structure and the relationship information between the nodes;

Recording a storage location of the node data in the node index table; wherein the node data includes a node content;

Store the node index table.

Beneficial effect

When storing a certain document by using the above technical solution, first, according to the document type of the document, the document content is mapped to each node in the corresponding tree structure and the data thereof. In this way, the document is made up of nodes, and the nodes are organized by a tree structure. Then, each node data corresponding to the document is stored, and the storage location of the node data is recorded in the node index table. In the above manner, a document can be stored in a storage medium in a tree structure, and a storage format with a node index is used. For such a document stored in a tree structure and a node index manner, when the user accesses part of the content of the document, the node corresponding to the content can be directly accessed without the need to process the entire document in advance. It saves system resources, improves access performance, and enables fast search of nodes.

In addition, the method of the present invention still retains the configuration of the document type, inheriting the advantages of the XML document. The document storage method of the invention can support the storage of complex tree structure data, small storage space, good expansibility, incremental modification, and easy to improve storage security.

DRAWINGS

FIG. 1 is a general flow chart of a document storage method of the present invention.

FIG. 2 is a specific flowchart of a document storage method according to an embodiment of the present invention.

FIG. 3 is a schematic diagram of a block number array and an array block corresponding data block.

Figure 4 is a schematic diagram of a free block table.

Figure 5 is a flow chart of shrinking the document storage space.

BEST MODE FOR CARRYING OUT THE INVENTION

In order to make the objects, technical means and advantages of the present invention more comprehensible, the present invention will be further described in detail below with reference to the accompanying drawings.

The basic idea of the present invention is to pre-configure a document type having a tree structure defined by at least one node type, and define a document storage format including a node index table and a node data area. When storing a document, the document content is first mapped to the corresponding nodes and their data in the corresponding tree structure according to the document type of the document. Then, according to the length of the document, a certain storage space is allocated to the document in the storage medium, and the storage area is further allocated to the node index table and the node data area in the storage space. Finally, each node data corresponding to the document is stored in the node data area, and the correspondence between each node and the storage location of the node data is recorded in the node index table.

In the embodiment of the present invention, for the convenience of description, the files stored according to the above storage manner may be collectively referred to as a SurXml document. (XML document defined by Sursen).

FIG. 1 is a general flow chart of a document storage method of the present invention. As shown in Figure 1, the method includes:

Step 101: Preconfigure a document type having a tree structure defined by at least one node type; and define a document storage format including a node index table and a node data area.

The core of the present invention is to store the document directly in the storage medium in a tree structure. The document type configured in this step represents the specific organization of the tree structure.

Step 102: Determine, according to the document type configured in step 101, the document type of the document, and map the content of the document to each node in the corresponding tree structure and the data according to the document type.

Step 103: Allocate a storage space for the document according to the length of each node in the corresponding tree structure and the length of the data, and allocate a storage area for the node index table and the node data area in the allocated storage space.

Step 104: Store the data of the node in the node data area, and record the correspondence between each node and the storage location of the node data in the node index table. In short, the storage location of the node data is recorded in the node index table.

So far, the storage method flow of the present invention ends. In the above process, step 102 and step 103 are performed sequentially. In fact, step 103 may be performed first and then step 102 may be performed, or two steps may be performed simultaneously.

In the above description, although the concept of "node data area" is given, those skilled in the art can understand that the concept is for convenience of description and is not a necessary technical feature. In addition, those skilled in the art can also understand that step 103 is an optional step, that is, after mapping the content of the document into each node in the tree structure and its data, the data of the node can be stored, and the node is recorded. The storage location of the point data.

The node data usually includes the content of the node. In an embodiment of the present invention, the relationship information with other nodes is further included. It should be noted that, in an embodiment of the present invention, the content of each node and the relationship information between the nodes are stored in the node data area, but only the node content is recorded in the node index table. The storage location, that is, the relationship information between the nodes, may not be recorded in the node index table.

The above annotated descriptions are also applicable to all of the following embodiments, and are not described again.

Embodiments of the invention

The foregoing is a general overview of a method for storing a document in the storage medium of the present invention. Specific embodiments of the storage method are described below by way of specific embodiments.

Example:

FIG. 2 is a specific flowchart of a document storage method according to an embodiment of the present invention. As shown in Figure 2, the method includes:

Step 201: Preconfigure a document type defined by at least one node type and having a tree structure, and define a document storage format including a file header, a node index table, and a node data area.

In an embodiment of the present invention, the configured document type includes the following information: a, which types of nodes (node types) are included in the document; b, names of various types of nodes included in the document, and nodes included in the node The name/type of each attribute; c, possible parent-child relationship between various nodes. With the above information, the document type can describe a specific tree structure. As an example of a simple document type, in the document type, there are several page sub-nodes under the root node, and there are several text and image sub-nodes under each page sub-node. . Specifically, each node type defines a node type tag that uniquely identifies a node type. In this step, a document storage format with a node index is also defined, which is specifically a file header, a node index table, and a node data area. Wherein, the file header is used to provide entry information for accessing the file, and it cannot be understood that the entry information for accessing the file must be stored at the head of the file. In fact, it may be agreed to store the entry information in any part of the file, such as the end of the file; The node index table is used to record the specific storage location of each node data to facilitate retrieval of each node data; the node data area is used to store each node data.

When you want to store a document, do the following.

Step 202: Referring to the document type configured in step 201, determine a document type of the document to be stored, and store the document type information.

In this step, after the document type is determined, the document type information is stored. This involves both the representation of the document type and the storage of the document type information.

Document types can be represented in two formats: type tables, such as custom type tables, and XML Schema/DTD/Relax NG, where Relax NG is a document type definition proposed by OASIS.

(1) Type table format:

A type table is a data structure. Any data structure that can describe information about a document type can be considered as a type table. An example implementation is given here, but the actual possible implementation is not limited to this example:

The definition of the attribute, including the name and type. Here, you can define a unique tag for each attribute, using the attribute tag as the name of the attribute; the type of the attribute can be the data type of the attribute, or you can define a unique tag for each attribute type.

Struct attr

{

 String name;

 String type;

};

The definition of the node: including the node name, attribute list, and list of child node names;

Struct node

{

 String name;

 Vector<attr> attr_list;

 Vector<string> sub_node_name_list;

};

Document definition: Specify the root node name

Struct document

{

 String root_node_name;

};

This is a very simple definition method that does not include iterations, selections, sequences, repetitions, etc., but most of the document type information can also be described using the above structure.

(2) XML DTD/Schema/Relax NG format

Although XML documents are linear in physical storage, they are logically a tree structure composed of nodes. Therefore, the DTD/Schema/Relax used to describe the XML document type Formats such as NG can also be used to describe the type of document of the present invention.

In addition, whether it is DTD, Schema or Relax NG, which supports defining names, attributes, and child nodes for nodes; this method has good support for iteration, selection, sequence, and repetition of child nodes, compared with the simple method given by the type table format. Describe more complex document types.

Here is a document type definition using the Schema description, DTD and Relax Although the form of NG is different, the three are similar in nature. In addition, the actual document type is not limited to this example:

<?xml version="1.0" encoding="UTF-8"?>

<xs:schema Xmlns:xs="http://www.w3.org/2001/XMLSchema" elementFormDefault="qualified" attributeFormDefault="unqualified">

 <xs:element name="document_root">

 <xs:annotation>

 <xs:documentation>Comment describes your Root element</xs:documentation>

 </xs:annotation>

 <xs:complexType>

 <xs:sequence>

 <xs:element name="page_obj" type="page"/>

 </xs:sequence>

 </xs:complexType>

 </xs:element>

 <xs:complexType name="page">

 <xs:sequence>

 <xs:choice>

 <xs:element name="text_obj" type="text"/>

 <xs:element name="image_obj" Type="image"/>

 </xs:choice>

 </xs:sequence>

 </xs:complexType>

 <xs:complexType name="text">

 <xs:attribute name="encoding" type="xs:string" Use="required"/>

 <xs:attribute name="text_str" type="xs:string" Use="required"/>

 </xs:complexType>

 <xs:complexType name="image">

 <xs:attribute name="type" type="xs:string" Use="required"/>

 <xs:attribute name="data" type="xs:string" Use="required"/>

 </xs:complexType>

</xs:schema>

The document type can be represented by either of the above two methods. The following describes how the document type information is stored.

A linear character sequence is stored for storing document type information. Specifically, for the document type represented by the type table format, a set of serialization functions may be specified according to the custom type table used, and the data of the type table is converted into a linear character sequence; for using DTD/Schema/Relax The document type represented by the NG format, because the DTD/Schema/Relax NG file itself is already a linear character sequence, so DTD/Schema/Relax can be stored directly. The NG file itself. Of course, before storing the document type information, the document type information to be stored may be pre-processed, such as encryption, compression, and transformation, and then the processing result is stored as document type information.

When storing document type information, document type information can be stored remotely, stored locally, or stored in program logic. The following describes the different implementations of storing document type information in three storage locations.

(1) Document type information can be stored locally, and so-called local storage refers to storing document type information in a specific file in which a document is stored. Here is an example method:

In the file, add a custom storage area for storing document type information, and specify the method of the area, including but not limited to the following method: a specified length of area starting from a specified position in the file; in the document A specific node or attribute is added to the type's tree structure as a storage for document type information.

After the document type information is stored locally, the program accessing the document uses the document type information inside the document by default.

(2) The document type information can be stored remotely, and the so-called remote storage refers to storing document type information in other file systems external to the stored document. Document type information when stored remotely, including but not limited to the following methods: remote or distributed file systems, such as Network File System (NFS), WIN2000 Distributed File System (DFS), Andrew File System (AFS); local file system Web page (WEB) server; File Transfer Protocol (FTP) server. After the document type information is stored in the remote, the URL or path information of the remote document type information is also stored in the SurXml document, and the method of selecting the storage location is the same as the method of selecting the storage location of the document type information by the local storage method. The program that accesses the SurXml document finds the document type information based on the URL or path information saved in the document.

(3) In addition to the above two types of storage of document type information (ie, stored inside or outside the document), the document type information may also be stored in the program logic for accessing the SurXml document. Specifically, it can be hard coded through a set of application program interface (API) functions. Before accessing the contents of the SurXml document, the application needs to call the API function to create document type information data in the memory; or directly store the document type information. In the source code or binary image of the application that accesses the SurXml document, the program that accesses the SurXml document can directly copy the document type information into memory for use. This non-explicit storage method can only support a limited number of document types, and the program needs to assign an ID to each document type. In the SurXml document, it is necessary to store the ID of the document type used.

When storing the document type information, it is also possible to adopt any combination of the above three storage methods. For example, some document type information is stored remotely, part of the document type information is stored locally, or part of the document type information is stored in the program logic.

Step 203: Map the content of the document to each node in the corresponding tree structure and its data according to the document type.

In this embodiment, the data defining the node includes content information and location information of the node. Specifically, the content information of the node is used to describe the content of the document corresponding to the node, including the node type tag, the node length, the name/tag and the value of the node attribute; the location information of the node is used to describe the node. The position of the point in the tree structure corresponding to the entire document may also be referred to as related node index information. The related node index information includes a parent node ID of the node, a left and right brother node ID of the node, a leftmost child node ID of the node, a number of child nodes of the node, and all child node IDs of the node. Among them, the ID of the left and right brother nodes and all the child node IDs of the nodes are optional. Without these two contents, the position of the node in the tree structure can be clearly expressed, and the two contents are added. The goal is to increase the speed of retrieval.

In this step, the document content is mapped to different nodes and their data according to the document type. For example, when mapping a PDF document, each page is mapped to a page node, and the text information part and the image information part in the page are respectively mapped to two child nodes of the page node, and the node IDs are respectively A and B. The content information of the page node includes: the node type is marked as a page node, the node length value, the name/tag and the value of the node attribute include information such as a header, a footer, and a page number. The relevant node index information of the page node includes: the parent node is the root node of the PDF document, the left and right sibling nodes are other page nodes, the leftmost child node ID is A, the number of child nodes is 2, and all child nodes The ID is A and B.

Step 204: Allocate a storage space for the document according to the length of each node and its data, and allocate respective storage areas for the file header, the node index table, and the node data area in the storage space.

Generally speaking, the length of the file header is either fixed or short, and does not require complicated storage allocation mechanism support, and can directly allocate a fixed storage area; and for the node index table and the node data area, The length thereof increases as the number of nodes increases. Therefore, in the present embodiment, the shrinkable storage allocation and recovery mechanism is used to allocate and organize the storage areas of the node index table and the node data area. In addition, this mechanism is also used for storage allocation of large objects.

The shrinkable storage allocation and recovery mechanism employed in an embodiment of the present invention is similar to the inode/freelist mechanism in the UNIX file system. Specifically, the node index table and the node data area are respectively treated as a UNIX file, and each corresponds to an inode.

In the inode/freelist mechanism, the entire storage space is divided into three parts: super block, inode table and data block, as shown in Table 1.

 Super block  Inode table  data block

 Table 1

 Similar to the UNIX file system, in this embodiment, the super block and inode of Table 1 Tables are used for the allocation and organization of storage space, while the actual data is in the data block section.

 Table 2 shows the structure inside the super block.

 Free block table  Idle Inode Table  Inode0

 Table 2

In Table 2, the free block table is used for allocation and reclamation of storage space. Since the inode table is a fixed-size area, the number of inodes recorded is also determined. The free space in the inode table can be managed by using the idle INODE table. Inode0 is an extension of the super block in the original unix file system according to an embodiment of the present invention, and is used for expanding and shrinking the storage space occupied by the inode table. In this embodiment, a special inode, inode0, may be added to the superblock, where the block number in which the inode table is located is recorded, in which case the inode table is located in the data block. In another embodiment of the present invention, the inode 0 is recorded in the super block as an inode number, and the inode 0 itself is stored in the inode table.

The following briefly introduces the relationship between inodes and files in the UNIX file system. Each file corresponds to an inode. The inode is used to record the block number of the data block contained in the file corresponding to it, that is, the specific storage location of the file data corresponding to the inode. An array of block numbers is stored in each inode. The first few items of the block number record record the block number of the block in which the file data of the inode is stored, and the indirect block is recorded in the last three items of the block number array. The block number of the indirect block and the cubic indirect block. The so-called indirect block refers to the data block in which the block number of the data block is recorded. Through the content of the indirect block, the block number of the corresponding data block can be found, and the data block storing the file data is further found according to the block number; A block refers to a data block in which an indirect block number is recorded, and a cubic indirect block refers to a data block in which a secondary indirect block is recorded. Figure 3 is a schematic diagram of a block number array and an array block corresponding to the data block. Wherein, 301 is a data block, 302 is an indirect block, 303 is a secondary indirect block, and 304 is a cubic indirect block.

For relatively small files, you can use only the first block of data blocks in the inode to record the storage location of the file; for larger files, you can use the last indirect in addition to the block number of the block in the block number array. The storage location of the block number entry of the block, the secondary indirect block, and the cubic indirect block, especially for the storage of the node data area, can play a large role. Of course, the number of block number entries of the indirect block can be arbitrarily set, and can continue to include four indirect blocks, five indirect blocks, or the like, or not, depending on the file size corresponding to the inode.

In an embodiment, the node index table and the node data area are both regarded as a UNIX file, and an inode is set for the node index table, marked as inode1, and an inode is set for the node data area, and is marked as inode2; Then inode1 records the specific storage location of the node index table, and inode2 records the specific storage location of the node data area.

Step 205: Store the data of the node in the node data area, and record the correspondence between each node and the storage location of the node data in the node index table.

There are three ways to store node data in the node data area: tlv mode, SlottedPage mode, and inode mode.

Tlv is the node type tag (tag) + node length (length) + node value (value), in this storage mode, all nodes are arranged in a certain order, inside each node, the type name is in front Next, the node length is stored, and finally the attribute value of the node and the ID of other related nodes.

In the node data area, the nodes sequentially stored in the tlv manner are linearly arranged from the head. After all node data has been stored, there may be a certain amount of unused free area in the node data area. In this embodiment, at the end of the node data area, the offset of the free area starting in the data area is recorded to facilitate management of the free area. It is of course also possible to reserve a node data area in the node data area in advance to record the offset of the free area starting in the data area.

The following describes the SlottedPage method. To achieve this storage method, the node data is divided into fixed-size pages, each node is located on a specific page, and multiple nodes can be stored in one page. At the front and the back of the page, the data of the array and node of each node offset in the page are recorded respectively, and the offset array and the node data are relatively increased. In the SlottedPage storage mode, inside the page, the data of the node can be freely moved in the free area of the page. In this way, it is more flexible when modifying the node data, especially when the length of the node data changes, and the paging storage is more suitable for the environment using the cache; the disadvantage is that the length of the node is affected by the page size. Constraints only apply to smaller nodes.

Nodes or attributes with large lengths, such as images, video, audio, etc., are not suitable for storage in the form of tlv or slotted pages. If you use the tlv method to store the node data, it will occupy a large amount of memory when loading the node data. If you use the SlottedPage method, you cannot create a larger node object due to the limitation of the page size.

In this embodiment, the node with a relatively large length can be stored by using the aforementioned inode/freelist mechanism. Specifically, an inode is set in the inode table for the large node to be stored, the storage location of the node data is recorded by the block number array, and the inode number corresponding to the node is recorded in the node data area.

After storing the node data, it is also necessary to record the correspondence between the node and the storage location of the node data in the node index table. For the different storage methods of the node data, the storage location of the node data can be expressed in different ways.

When the node data is stored in the tlv mode, the starting offset of the node data in the node data area may be used to indicate the storage location of the node data.

When the node data is stored in the SlottedPage mode, the storage location of the node data may be represented by the page address where the node is located and the index of the offset array element in the node. Thus, when the node data moves within the page, although the offset within the page may change, the index of the offset array element does not change, so the node data storage location indicated in the node index table does not A change has occurred. When the node data is retrieved, the location of the node data can be accurately located by combining the node data storage location indicated in the node index table and the value of the offset array element in the page.

When the node data is stored in the inode/freelist mode, the inode number corresponding to the node may be recorded in the node index table as the storage location of the node data.

When the correspondence between the node ID and the storage location of the node data is recorded, the index may be recorded. That is, the ID of the node is mapped to the storage location of the data of the node in the node data area. The implementation of the node index can be as follows:

1) Hash index

The node ID is used as a key value to establish a hash table, and the hash table stores the storage location of the node data in the node data area.

2) B-tree (or B+ tree) index

Create a B-tree (or B+ tree) with the node ID as the key.

3) Linear table

If the number of nodes is small, a linear table can also be used to store the node ID and the corresponding storage location.

In the case of a large number of nodes, it is recommended to use a hash index or a B-tree (B+ tree) index. In the well-known implementation methods of the two indexes, there are algorithms for implementing the paging storage mode, and therefore, Controlling the number of pages cached in memory to control the memory footprint of the index table, can quickly map the node ID to the storage location of the node without taking up a lot of memory.

In short, for any node, the node data needs to be stored in the node data area, and then the node index table is filled according to the storage location of the node data in the node data area.

Step 206: Store identification information and entry information of the accessed document in the file header.

The main purpose of the header is to describe the file, providing some metadata and entry information for accessing the contents of the file. In an embodiment of the present invention, it is not necessary to store the identification information of the access document in the file header, and the identification information may be replaced by a file suffix.

The entry information required by the file header of the SurXml document formed by the present invention includes: a node index table and a storage location and length of the node data area in the file; one or more root nodes (the logical structure of the SurXml document is a tree type) Therefore, the node may form the ID of a tree or a tree. The storage location of the node index table and the node data area in the file is the corresponding inode number.

The description information that SurXml's file header needs to provide can be quite arbitrary, but must include one or more unique identifiers so that applications that need access to the file content can identify the document as SurXml.

For the structure of the SurXml file header, here are some possible scenarios:

1) Binary data (offset, length, root node ID, etc.) is converted to text data using a text format, borrowing the ini file format, x=y.

2) Use text format, borrow xml file format, like <x>y</x>, treat binary data as 1.

3) Use the binary format to store various metadata and entry information in a hard-coded offset and length.

4) Store the metadata and the name and value of the entry information in binary format, and store them sequentially in the file header.

5) Other text or binary formats.

An example of a file header is given below, using the xml form:

<SurSenXml ver = 1.0, manufacturer = Sursen.com>

<License>Unlimited</License>

 <Description>example Document</Description>

 <DataEntry>

 <NodeIndex>0x00000175</NodeIndex>

 <NodeData>0x00000a00</NodeData>

 <RootNodeID>12345</RootNodeID>

 </DataEntry>

</SurSenXml>

The following options are available for how to locate the starting offset and length of the header data in a file:

1) The starting offset of the file header data can be fixed or recorded to a fixed offset position in the file;

2) The length of the header data can be fixed or recorded to a fixed offset position in the file;

3) some combination of design 1) and design 2);

4) For the design of 1) and design 2), the starting offset and length of the file header data are recorded at a fixed offset position, and can be further deepened, and the offset of o2 is recorded at a fixed offset position o1. Shift, record o3... at the o2 offset, and record the offset and length of the file header data at on.

At this point, the process of storing a document in a file is completed.

In the above stored procedure, step 206 is performed after step 205. In fact, step 206 may also be performed concurrently with step 205 or before step 205.

For the SurXml document stored in the above manner, when the application accesses the document, first determine the SurXml document type, and then determine the node ID corresponding to the content to be accessed, by searching for the node ID in the node index table. The entry of the node determines the storage location of the node data, and then accesses the node data. It can be seen that when accessing the document, the entire document does not need to be parsed, and the node data can be directly accessed, the access speed is fast, the processing is convenient, and the access performance is greatly improved.

The SurXml document stored in the above manner may not occupy the storage space allocated for the SurXml document, that is, the storage space allocated for the document has a free area. The storage method of the present invention can effectively manage the free area in the document storage space and the free area in the document internal node data area.

The management of free space in the storage space allocated for the document is done through the free block table. The free block table is stored in portions, and each portion contains one or more consecutive blocks in which the block number of the free block that is not allocated in the storage space is recorded. The first free block number entry in each part of the free block table records the starting block number of the lower part of the free block table, and the first free block number entry of the last part of the free block table is 0, indicating that this part is The last part of the free block table. Figure 4 shows a schematic diagram of a free block table. In the figure, 401 is the free block table shown in Table 1, which is the first part of the entire free block table, and the first item records the starting block number a of the lower part of the free block table, from which the free block can be found. The next portion 402 of the table, and so on, up to 405, the value of the first entry in 405 is 0, indicating that this is the last portion of the free block table.

When a free block is allocated or reclaimed, it is taken from the end of the free block table. First allocate or reclaim the free block pointed to by the last part of the free block table.

The storage space occupied by the SurXml document can be expanded and contracted. The expansion of the storage space is relatively simple. It is only necessary to incorporate the expanded free space into the management of the free block table. In fact, the new free block number is appended to the end of the free block table.

The shrinkage of the storage space occupied by the SurXml document is more complicated. Figure 5 is a flow chart for shrinking the storage space. As shown in Figure 5, the process includes:

Step 501, determining a target shrinkage amount of the storage space and a number of free blocks in the original storage space.

In this step, when determining the number of free blocks in the original storage space, in addition to the portion of the free block in the super block, the data blocks occupied by the rest of the free block table are also counted in the free space.

In step 502, it is determined whether the shrinkage of the storage space is possible. If yes, step 503 and subsequent steps are performed, otherwise the flow is ended.

In this step, it is determined whether the shrinkage of the storage space is possible: if the target shrinkage amount of the storage space is greater than the length of the free space, it is determined that the shrinkage is impossible to complete, otherwise the shrinkage can be determined.

Step 503: Determine whether the SurXml document occupies a non-idle data block in the contraction area of the tail of the storage space. If yes, perform step 504 and subsequent steps, otherwise perform step 505 and subsequent steps.

In step 504, the free data block of the non-shrinking area occupied by the SurXml document is replaced with the non-free data block of the shrinking area, and the corresponding inode and free block table are updated.

Step 505: Determine whether the data block storing the free block table is located in the contraction area of the end of the storage space occupied by the SurXml document, and if yes, perform step 506 and subsequent steps, otherwise step 507 is performed.

Step 506: Transfer the block number item describing the non-shrink area free block in the free block table located in the contraction area to the free block table of the non-shrink area.

In step 507, a new footer of the free block table is calculated, and the storage space occupied by the SurXml document is truncated according to the specified length.

In one embodiment of the invention, all of the free blocks may be shrunk.

The above is the management of the storage space occupied by the SurXml document. In the storage area allocated for the node data area, the organization and management of the free space is performed inside the storage area occupied by the node data area according to the storage mode of the node data.

In the tlv storage mode, at the end of the node data area, the offset of the free area starting in the data area is recorded to facilitate management of the free area.

In the SlottedPage storage mode, the free space inside each page of the node data area is managed by itself; if it is necessary to search for free space for the new node, it can search page by page; to improve the efficiency of the search, another pair can be established. The index of the free page indexed by the size of the free space in each page of the node data area, the index method that can be used includes: directly recording the number of the page and the size of the free space, sorting the page number with the size of the free space as the key value, B-tree /B+ tree (with free space size as key), and so on. The allocation, organization, and collection of the free page index storage in the node data area may use the inode/freelist mechanism to process the free page index of the node data area as a file corresponding to an inode.

Applying the above method makes it easy to manage free areas in the document. When a large free area appears in the node data area, the free area may be marked as a free data block of the SurXml document according to the policy, that is, the free area is deleted from the node data area. When the SurXml document requires a space contraction operation, compression is performed as described above. The management method of the free area makes the collection and release of the document space more convenient, and effectively improves the storage efficiency of the document.

In the process of storing the SurXml document in the manner shown in Figure 2, the operations involved in the node include: creating a node, deleting a node, adding a child node, and modifying the attributes of the node.

(One) When storing a document, for nodes that do not yet exist, storing the node data involves the operation of creating a node, such as adding a new table to an established document. The operation specifically includes the following steps:

a. Determine the node data, specifically, the node type tag and the node attribute data.

b. Find the free area in the node data area and allocate a certain amount of space for the node data. Specifically, it may be that a certain amount of space is allocated to the node data according to the node attribute data.

When searching for a free area, according to different storage manners of the node data in the node data area, the organization management method of the free space in the foregoing node data area is used.

c. Add an item in the node index table, assign a new node ID, and point to the storage location of the allocated node data in the node data area.

d. Record the input node data into the storage location of the node data area allocated for the node. Specifically, the input node type flag and the node attribute data are recorded into the storage location of the node data area allocated for the node.

(2) In the existing SurXml document, when the content of the document is deleted, the operation of deleting the node is involved, for example, deleting a form in the document. The operation specifically includes the following steps:

a. Determine the ID of the deleted node.

b. Find the node ID in the node index table to obtain the storage location of the node data in the node data area.

c. Mark the space corresponding to the storage location of the node data as idle.

d. The index entry corresponding to the node ID is deleted from the node index table.

(3) In the existing SurXml document, when a newly created node is connected with other nodes in the tree structure, the operation of adding the child node is involved, for example, the newly added table Establish a connection with the page on which it is located. The operation specifically includes updating the relevant node index information of the relevant node. Specifically, the following steps are included:

a. Determine the parent node ID, child node ID, and child node location.

Where the child node position refers to the position of the child node in all child nodes of the parent node.

b. Find the ID of the parent and child nodes in the node index table, and obtain the storage location of the parent node data.

c. In the node data area, update the child node ID list of the parent node, and update the parent node ID value of the child node.

In an embodiment of the present invention, when the parent node records only the number of child nodes and the ID of the first child node, updating the related node index information of the relevant node may also be: using the left and right brother nodes of the child node Point table traversal.

(4) The operation of deleting the child node corresponds to adding the child node, that is, canceling the connection relationship between the nodes, for example, moving a table from the current page. The operation specifically includes updating the relevant node index information of the relevant node. Specifically, the following steps are included:

a. Determine the parent node ID and the child node ID to be deleted.

b. Find the ID of the parent-child node in the node index table, and obtain the storage location of the pair of parent-child node data.

c. In the node data area, delete the input child node ID from the child node ID list of the parent node, and update the parent node ID value of the child node, specifically, the parent node may be the parent node. The node ID value is set to null, or it may be the ID of the parent node ID value as the original grandparent node.

In an embodiment of the present invention, when the parent node records only the number of child nodes and the ID of the first child node, updating the related node index information of the relevant node may also be: using the left and right brother nodes of the child node Point table traversal.

(5) When the SurXml document is modified, it may involve the operation of modifying the node attributes, for example, modifying some of the tables. The operation specifically includes the following steps:

a. Determine the node data, specifically determine the node ID, node attribute name, and node attribute value.

b. Find the node ID in the node index table to obtain the storage location of the node data.

c. Find the node data in the node data area and update the node data. Specifically, the corresponding node attribute value is updated according to the node attribute name.

d. If the space is insufficient, allocate a new free space, copy the node data to the new space, mark the data block where the original node data is located as idle, and update the node index table to replace the corresponding entry. Point to the new storage location.

Applying the SurXml document formed after the above method is stored may sometimes require operations such as encryption and lossless compression. These can all be achieved by performing a corresponding reversible transformation on the subtree of the document. The reversible transformation operation for specifying the SurXml document in the embodiment of the present invention specifically includes the following steps:

a. Determine the subtree root node ID and the transformation function corresponding to the content to be changed. For example, determine the subtree root node ID and encryption function. Since the encryption may be the entire document or a part of the document, in this step, it is necessary to determine the location of the encrypted portion in the entire document. Specifically, the subtree root node corresponding to the encrypted portion is determined.

b. Traverse the subtree according to the determined subtree root node ID.

In this step, the traversal can use depth-first traversal or breadth-first traversal.

c. Record the ID and data of each node traversed into the buffer, and process the data in the buffer by using the transformation function.

For example, the ID and data of each node traversed are recorded in a linear buffer, and the data in the buffer is processed by the determined encryption function. The operation in this step actually completes the process of encrypting the specified document content.

d. Update the node index table and node data.

In this step, in the node index table, the root node of the subtree is marked as the root of the transformation tree; the other transformation nodes in the subtree except the root node of the subtree are marked as internal nodes of the transformation tree, and The ID of the root node is recorded into the other transform node index. In order to ensure the connection relationship between nodes, all transformed node IDs remain unchanged.

In the node data area, the data in the buffer processed by the transform function (for example, the encryption function) is saved as the data of the root node of the subtree; at the same time, the other nodes in the subtree except the root node are emptied. The data.

At this point, the operation of transforming (such as encrypting) the specified document content is completed.

Corresponding to the above-described reversible transformation of the document, the transformed document may also be inversely transformed to obtain an initial document. The specific operations include the following steps:

a. Determine a subtree root node ID and an inverse transform function corresponding to the content of the inverse transform.

For example, determine the subtree root node ID and decryption function. Corresponding to the encryption process, in this step, it is necessary to determine the subtree root node ID corresponding to the part to be decrypted.

b. According to the subtree root node ID, find the storage location of the subtree root node data in the node data area in the node index table.

c. Use the inverse transform function to process the data of the root node of the subtree.

For example, use the decryption function to process the data of the root node of the subtree. Since the encrypted data of the entire subtree node is stored as the subtree root node data, as long as the subtree root node data is decrypted, the data of the entire subtree node is decrypted.

d. The data of the root node of the subtree after the inverse transform processing is sequentially restored to the data of each node according to the traversal order when the transform is performed.

For example, from the result of the decryption function processing, the data of each node is sequentially restored according to the traversal order of the encryption process.

e. Mark the subtree root node in the node index table and each internal node of the subtree as ordinary nodes.

At this point, the inverse transform operation ends.

The process of reversible transformation and inverse transformation such as compression is the same as that of the above embodiment, except that the corresponding encryption and decryption functions are replaced by functions such as compression and decompression, and will not be described here.

According to the above method, not only the entire document can be reversibly transformed, but also any subtree stored therein can be transformed, thereby realizing encryption, lossless compression and the like on part of the document.

An XML document is a common document format, and a SurXml document formed in accordance with the storage method of the present invention can also be converted to and from an XML format document.

Specifically, the specific process of converting an XML document into a SurXml document includes:

a. Get the schema or DTD of the XML document, and define the document type of the SurXml document according to the schema or DTD of the XML document.

b. Parse the XML document, convert each element into a node in the SurXml document, and set its properties in the corresponding node; and set the parent and child of each node in the SurXml document according to the parent-child relationship of each element in the XML document. relationship.

c. Generate a SurXml document based on the results of steps a and b.

The specific process of converting a SurXml document to an XML document includes:

a, get the document type definition of SurXml, if it is Schema or DTD or Relax NG, no further processing is required; if it is a custom type table, you need to convert the custom type table to Schema or DTD or Relax NG.

b. Traverse the tree structure in the SurXml document, convert the node into an XML element and set the corresponding attribute according to the corresponding definition of each node in the document type definition.

The process in this step is recursive, and the child nodes are converted to child elements in the XML document.

c. Generate an XML document based on the results of steps a and b.

Industrial applicability

As can be seen from the above technical solution, in the present invention, document types representing different tree structures are pre-configured, and the document storage format is defined to include a node index table and a node data area. With the above document storage format with node index, a fast search of nodes can be achieved. When storing a document, the document content is first mapped to the corresponding nodes and their data in the corresponding tree structure according to the document type of the document. In this way, the document is made up of nodes, and the nodes are organized by a tree structure. Then, according to the length of the document, a certain storage space is allocated to the document in the storage medium, and the storage area is further allocated to the node index table and the node data area in the storage space. Finally, each node data corresponding to the document is stored in the node data area, and the correspondence relationship between each node and the storage location of the node data is recorded in the node index table, and the entry information of the access document is stored in the file header. . In the above manner, a document can be stored in a storage medium in a tree structure, and a storage format with a node index is used. For such a document stored in a tree structure and a node index manner, when the user accesses part of the content of the document, the node corresponding to the content can be directly accessed without the need to process the entire document in advance. The system resources are saved and the access performance is improved; in addition, the method of the present invention still retains the configuration of the document type and inherits the advantages of the XML document. The document storage method of the invention can support the storage of complex tree structure data, small storage space, good expansibility, incremental modification, and easy to improve storage security.

Further, when the present invention allocates a storage area to the node index table and the node data area, the node index table and the node data area are treated as two files respectively, and the mechanism similar to UNIX inode/freelist is used. The allocation, organization, and recycling of these two storage areas make the two storage areas easy to shrink and expand, simplifying operations when adding nodes and growing node data.

The above are only the preferred embodiments of the present invention and are not intended to limit the scope of the present invention. Any modifications, equivalent substitutions, improvements, etc. made within the spirit and scope of the present invention are intended to be included within the scope of the present invention.

Sequence table free content

Claims (31)

A method for storing a document, comprising: Maps the content of the document to a tree structure according to the specified document type; wherein the type information of each node is defined in the document type; Storing the contents of the nodes constituting the tree structure and the relationship information between the nodes; Recording a storage location of the node data in the node index table; wherein the node data includes a node content; Store the node index table. According to claim 1 The method is characterized in that the type information of the node includes a node type tag, a node type name, information of all legal attributes of the node type, and a node type of all legal child nodes of the node type. The method according to claim 2, wherein the attribute information comprises an attribute tag, an attribute name, and an attribute type. The method of claim 1, wherein the node content comprises a node type tag, a node length, a name/tag and a value of a node attribute; and Or, the node data further includes relationship information between the node and other nodes. The method according to claim 4, wherein the relationship information between the node and other nodes comprises: a leftmost child node ID of the node And the number of child nodes of the node. The method according to claim 5, wherein the related node index information further comprises: a parent node identifier ID of the node, and Or, the left and right brother node IDs, and / or, all child node IDs of the node. The method of claim 1 wherein tlv (type tag, length, value) mode, slottedpage mode, and Any one or combination of the inode/freelist modes stores the content of the nodes and the relationship information between the nodes  The method of claim 7 wherein said tlv The method is: sequentially storing the node type mark, the node length, and the attribute name of each node in a predetermined storage space / a tag and a value; wherein the storage location of each node data is: a starting offset of each node data in the predetermined storage space; The slottedpage The method is: dividing a predetermined storage space into a plurality of pages, storing data of each node on a specific page, and storing an offset array in the page, indicating that each node in the page is within the page a starting offset; the storage location of the node data is: a page address where the node data is located and an element index corresponding to the node data in the offset array; The inode/freelist mode is: set an inode for each node And storing the block number of the data block occupied by the node; storing the node data in the data block, and storing the inode number corresponding to the node in the inode table; wherein the storage location of the node data is: Node corresponding Inode number. According to claim 8 The method is characterized in that content of each node and relationship information between nodes are stored in a node data area, the method further comprising: managing a free space in the node data area. The method according to claim 9, wherein when the content of each node and the relationship between the nodes are in tlv When the mode is stored in the node data area, the managing the free space in the node data area is: At the end of the node data area, record the offset of the free area starting in the data area; When the content of each node and the relationship between the nodes are slottedpage When the mode is stored in the node data area, the managing the free space in the node data area is: Establish a free page index for indexing the size of the free space in each page in the node data area; When the content of each node and the relationship information between the nodes are inode/freelist When the mode is stored in the node data area, the managing the free space in the node data area is: The free block in the node data area is managed by the free block table. According to claim 1 The method is characterized in that the content of each node and the relationship information between the nodes are stored in the node data area; between the contents of the nodes constituting the tree structure and the nodes Before the relationship information, further includes: The respective storage areas are allocated for the node index table and the node data area. According to claim 1 The method of the present invention, further comprising: allocating a storage area for the file header; wherein the file header stores the identification information and the entry information of the accessed document. The method of any of claims 1 further comprising expanding and shrinking the storage space occupied by the document. The method of claim 13 wherein the inode/freelist mechanism is used to shrink the storage space occupied by the document; The inode/freelist mode is: set an inode for each node to record the data block block number occupied by the node; store the node data in the data block, in the inode The inode number corresponding to the storage node in the table. The method according to claim 14, wherein the storage space occupied by the extended document comprises: filling a block number of the extended free block into the end of the free block table. The method according to claim 14, wherein the storage space of the contracted document comprises: Determining whether there is a non-idle data block in the contracted area at the end of the current storage space of the document, and if so, replacing the free data block of the non-shrinking area of the current storage space with the non-idle data block of the contracted area, and updating the corresponding Inode and free block table; Determining whether the data block storing the free block table is located in the contraction area of the current storage space, and if so, transferring the block number item describing the non-shrink area free block in the free block table located in the contraction area to the free block table of the non-shrink area in; Calculate the new footer of the free block table and truncate the current storage space. According to the claims The method of claim 16, further comprising: before determining whether there is a non-idle data block in the contraction area of the tail of the current storage space of the document, further comprising: It is possible to determine the shrinkage of the storage space based on the determined target shrinkage amount and the number of free blocks in the current storage space. According to claim 17 The method is characterized in that the determining the shrinkage of the storage space is possible: determining whether the target shrinkage amount is greater than a free space of a current storage space, and if so, determining that shrinkage of the storage space is possible. The method according to any one of claims 1 to 18, characterized in that the method further comprises: adding, deleting, and/or the node data Or, modify it. The method of claim 19, wherein the adding the node data comprises: Determining node data; Find free areas and allocate space for node data; Add an entry in the node index table, assign a new node ID, and point to the storage location allocated for the node data; The entered node data is recorded to the storage location assigned to the node. The method of claim 19, wherein deleting the node data comprises: Determine the ID of the deleted node; Find the node ID in the node index table to obtain the storage location of the node data. Marking the space corresponding to the storage location of the node data as idle; The index entry corresponding to the node ID is deleted from the node index table. According to claim 20 or 21 The method is characterized in that, when the added node data has a connection relationship with other nodes, or when the deleted node data has a connection relationship with other nodes, the method further includes: Update the relevant node index information of the relevant node. The method of claim 19, wherein modifying the node data comprises: Determining node data; Find the node ID in the node index table to obtain the storage location of the node data. Update node data. According to claim 23 The method is characterized in that, when the modification of the node data results in insufficient space, the method further includes: Allocate new free space, copy the node data to the new space, mark the data block where the original node data is located as idle, update the node index table, and point the corresponding table entry to the new storage location. A method according to any one of claims 1 to 18, further comprising: transforming and inversely changing the stored document. The method of claim 25, wherein the transforming the stored document comprises: Determining a subtree root node ID and a transformation function corresponding to the content to be transformed; Traversing the subtree according to the subtree root node ID; Recording the ID and data of each node traversed into the buffer, and processing the data in the buffer by using the transformation function; In the node index table, mark the root node of the subtree as the root of the transformation tree, mark other nodes in the subtree except the root node of the subtree as internal nodes of the transformation tree, and Recording the subtree root node in other node indexes ID ; The data in the buffer is saved as data of the root node of the subtree, and data of other nodes in the subtree except the root node of the subtree is cleared. The method according to claim 25, wherein the inverse transforming the stored document comprises: determining a subtree root node ID corresponding to the content of the inverse transform And inverse transform function; Finding a storage location of the subtree root node data in the node index table according to the subtree root node ID; Processing the data of the root node of the subtree using the inverse transform function; The data of the root node of the subtree after the inverse transform processing is sequentially restored to the data of each node according to the traversal order when the transform is performed; In the node index table, the subtree root node and each node of the subtree are marked as ordinary nodes. The method according to any one of claims 1 to 18, further comprising: converting the stored document into an extensible markup language XML document; and / or , convert the XML document to the stored document. The method of claim 28, wherein said converting said stored document to an extensible markup language XML The documentation includes: Traversing the tree structure of the stored document, converting the node to an XML element and setting the corresponding attribute according to the corresponding definition of each node in the document type, and converting the child node to Child elements in an XML document; Generate an XML document based on the results of the above steps. According to the claims The method of claim 29, wherein when the document type of the stored document is a type table, before the traversing the tree structure of the stored document, the method further comprises: Convert the document type to Schema , DTD , or Relax NG . The method of claim 28, wherein converting the XML document to the stored document comprises: Schema, DTD, or Relax NG based on the XML document Defining document type information of the stored document; Parsing the XML document, converting each element to a node in the stored document, setting its properties in the corresponding node; and according to XML The parent-child relationship of each element in the document sets the parent-child relationship of each node in the stored document. The stored document is generated according to the results of the above two steps.

Images