KR20140012377A - Method of forming index file, method of searching data and system for managing data using dictionary index file, recoding medium - Google Patents

Abstract

According to the present invention, the number of data entries in the dictionary index file is reduced, which greatly reduces the number of searches of the primary index file and the data file, thereby shortening the search time of the data to be searched. To this end, in particular, a data file generation step of adding data address values to the sorted data and storing the data in which the field values are filled in the plurality of fields in a table form according to the collection order; A primary index file generation step of sorting by a group having the same key value with respect to a key (Key), which is one of a plurality of fields, and adding and storing index address values to the key values according to the sorting order; And a dictionary index file generating step of adding and storing a range of index address values while uniquely aligning key values of the primary index file by each key value. Is initiated.

Description

Method of forming index file, method of searching data and system for managing data using dictionary index file, Recoding medium}

The present invention relates to an index file generation method, a data retrieval method using a dictionary index file, a data management system, and a recording medium. More specifically, the present invention relates to an index file generation method for quickly searching data using a dictionary index file, a data retrieval method using a dictionary index file, a data management system, and a recording medium.

Types of data retrieval include: i) reading the data from the beginning to the end of the data stored in the table one by one (full table scan), ii) creating an index for a specific column in the table, and then Method for index search (index scan), iii) a method of constructing an index with values of 0 and 1 (bitmap index scan), iv) a method of storing two or more joined tables in the same block structure (index cluster) scan), v) A very effective way to retrieve a row from a large table using a hash algorithm (hash cluster scan).

On the other hand, there is a conventional index search method and apparatus related to the search method using the index (Publication No. 10-2008-0046905). The prior art searches for a first field corresponding to a first key value at a predetermined index, and a second field at a level corresponding to a search request at an index based on the searched first field when a predetermined search request is input. And extracting an identifier corresponding to the searched second field. The prior art relates to a technique of extracting an identifier by searching for a first field and a second field corresponding to a first key value using the same index, and providing metadata or content of the content.

An index refers to a data object that is structured separately so that table rows can be identified by the same path to improve data retrieval speed. For large amounts of data, an index can be used to retrieve the data quickly. Using indexes for data retrieval has the advantage of speeding up retrieval, reducing the load on the system and ultimately improving the overall performance of the system, while creating indexes can be time consuming. In addition, the index may take up database space and additional space may be required.

If the accumulated data count is numerous, the computer may have to enter the address (or location) where each data is stored in order to find the data related to the key value that the user wants to search. There may be a delay in obtaining the search result. There is nothing else. In addition, if the computer does not search sequentially from the beginning of the data file (i.e. from the middle of the data file) when searching for data related to a particular key value, the computer may forward in the forward direction of the search start point. Since the search proceeds, it becomes a considerable difficulty to make the search in the backward direction. If the search for the data in the backward direction is cumbersome, the computer has to perform the search in the forward direction again from any point of the data in the backward direction.

The present invention was created to solve the above problems, and the first object of the present invention is to search for data by searching only the location of data related to a specific key value through a dictionary index file, even if a computer or the like does not search all data files. The present invention provides an index file generation method, a data retrieval method using a dictionary index file, a data management system, and a recording medium that can reduce time.

In addition, a second object of the present invention is to provide an index file generation method capable of managing the dictionary index file itself in memory by reducing the size of the dictionary index file, a data retrieval method using a dictionary index file, a data management system, and a recording medium. .

An object of the present invention as described above is a data file generation step of adding data address values to the sorted data and storing the sorted data in a table form according to the order in which the field values are filled in the plurality of fields; A primary index file generation step of sorting by a group having the same key value with respect to a key (Key), which is one of a plurality of fields, and adding and storing index address values to the key values according to the sorting order; And a dictionary index file generation step of adding and storing a range of index address values while uniquely sorting key values of the primary index file for each key value. By providing.

In addition, in the primary index file generation step, the primary index file may be arranged such that data address values are arranged together with key values.

Further, in the dictionary index file generation step, a dictionary index address value may be added to and stored in each key value of the dictionary index file.

And, if there is additional data collected, the index file generation method updates the data file, the primary index file and the dictionary index file, while the data address value of the data file, the index address value of the primary index file, and the dictionary index. The range of index address values of the file may be modified and stored.

Meanwhile, an object of the present invention provides an index address value range obtaining step of obtaining information on an index address value range of a key value to be searched by searching a dictionary index file among the generated index files; A data address value obtaining step of obtaining information on a data address value corresponding to the index address value by searching the index address value included in the obtained index address value range in the primary index file; And a data acquiring step of obtaining the data corresponding to the data address value by searching the obtained data address value in the data file.

In the obtaining of the index address range, the number of data including the key value to be searched is calculated based on the range of index address values, compared with the total number of data, and then the data file is searched through the primary index file. And a search path determining step of determining whether to search the data file immediately.

The determining of the search path may include determining to search the data file via the primary index file when the ratio of the number of data including the key value to the total number of data is smaller than the preset number. have.

Meanwhile, an object of the present invention is to create a data file by adding a data address value to the sorted data while sorting in a table form according to the collection order of data in which the field values are filled in a plurality of fields. The primary index file is created by adding index address values to the key values according to the sorting order by sorting by group having the same key value for any one selected field among the fields, and the key value of the primary index file. A data collection engine generating a dictionary index file by adding a range of index address values while uniquely arranging them by each key value; Search the dictionary index file to obtain information about the range of index address values of the key values to be searched, and search the index address values included in the obtained index address value ranges in the primary index file to correspond to the index address values. A data retrieval engine for acquiring information on the value and retrieving the acquired data address value from the data file to obtain data corresponding to the data address value; And a database unit for storing a data file, a primary index file, and a dictionary index file, which can be achieved by providing a data management system using a dictionary index file.

In addition, the data management system controls the data collection engine so that the data collection engine generates the data file, the primary index file, and the dictionary index file and stores the data file in the first database unit or the second database unit, and the data search engine pre-indexes the data collection engine. And a controller configured to control a data search engine to search for a data file based on the file.

The database unit may further include a first database unit which stores a data file and a primary index file; And a second database unit storing the dictionary index file.

Then, the data search engine calculates the number of data including the key value to be searched based on the range of index address values and compares it with the total number of data, and then searches the data file via the primary index file or not. It may be characterized in that it is determined whether to search immediately, and if the ratio of the number of data including the key value to the total number of data is smaller than the preset number, the data file is searched through the primary index file.

Meanwhile, an object of the present invention can be achieved by providing a computer-readable recording medium having recorded thereon a program capable of generating and searching the primary index file and the dictionary index file.

According to the present invention, the number of data entries in the dictionary index file is reduced, which greatly reduces the number of searches of the primary index file and the data file, thereby shortening the search time of data related to the key value to be searched.

In addition, since the number of data related to the key value can be confirmed only by searching the dictionary index file, the search path of the data can be determined, thereby reducing the search time of the data.

In addition, it is possible to manage the dictionary index file in memory by reducing the capacity of the dictionary index file.

1 is a view schematically showing the types of index files that can be generated by the method of generating an index file according to the present invention;
2 is a view for explaining a method for generating an index file according to the present invention;
3 is a view for explaining a process of inserting additional data in the index file generation method of the present invention;
4 is a view for explaining a data retrieval method using the inventor index file;
5 is a block diagram of a data management system using the dictionary index file of the present invention.

Hereinafter, preferred embodiments of the present invention will be described in detail with reference to the accompanying drawings. It should be noted that the same components of the drawings are denoted by the same reference numerals and signs as possible even if they are shown on different drawings. In the following description of the present invention, detailed description of known functions and configurations incorporated herein will be omitted when it may make the subject matter of the present invention rather unclear.

Meanwhile, in the present invention, the data used for generating the data file, the primary index file, and the dictionary index file may correspond to all data that can be created in a table form with a plurality of fields. Specifically, log data used to create a log file may be representative, other data containing customer information (including fields such as name, phone number, address, email address, place of work, position, etc.), and employees of the company Data (including fields such as name, department, position, address, contact, salary, etc.), and data containing information about books held by the library or bookstore (author, year of publication, classification code, publisher). Various data, such as fields, and the like, may be used. However, the following description will be given taking log data such as a computer as a specific example for convenience of description.

In addition, in the present invention, the term Key refers to a specific field selected to create a primary index file or a dictionary index file among a plurality of fields constituting data, and the key value refers to a specific data value for the key.

<How to create index file>

1 is a diagram for explaining the types of index files that can be generated by the method of generating an index file according to the present invention, taking log data as an example. The log format of the log data shown at the top of FIG. 1 is time, source IP, target IP, source port, target port, action, and rule. It consists of various fields such as number (Rule No). In addition, the table at the lower right of FIG. 1 is a data file arbitrarily configured in accordance with the log format of log data, and the action shows log information of allow or disallow, but only Allow is shown in FIG. In the index file generating method of the present invention, it can be seen that various primary index files and dictionary index files can be generated based on each field of log data.

For example, as shown in FIG. 1, only the source IP field is extracted from log data to generate a primary index file and a dictionary index file pair (index # 1), or only a target IP field is extracted to extract a primary index file and Create a primary index file pair (index # 2), extract only the source port to create a primary index file and a dictionary index file pair (index # 3), or extract only the target port to create a primary index file and a dictionary index file pair. Can be generated (index # 4). 2 is a view for explaining a method for generating an index file according to the present invention. Hereinafter, a method of generating an index file will be described in detail with reference to FIG. 2, and log data will be described with specific examples. In FIG. 2, for convenience of description, field values included in fields of log data are briefly displayed in Korean, English, numbers, etc., such as aaa, 1111, abcd, and Kanada.

1. Data file creation step ( S110 )

The data file generating step (S110) is a step in which the data collection engine 100 adds and stores a data address value to the sorted data while sorting the data in which each field value is filled in a plurality of fields in a table form. Say. 2 shows a log file as an example of a data file. That is, the log file includes fields such as time, source IP, target IP, source port, target port, action (log information of allow or deny) and rule number.

For example, assuming that the data file in FIG. 2 contains 1 billion log data and A of the log data is the source IP field, each field value included in A (aaa, aab, aaa, aab, Data address values (0, 50, 100, 150, 200, 250, ...) corresponding to aaa, aab ...., respectively, are added by the data collection engine 100 to generate a data file. At this time, the log data is sorted according to the collection order, and a data file is created.

2. Create the primary index file ( S120 )

The primary index file generation step S120 is a step in which the data collection engine 100 generates a primary index file based on the data file generated in the data file generation step S110. Specifically, by sorting by group having the same key value for a key, which is one selected from among a plurality of fields included in the data file, by adding an index address value to the key values according to the sorting order, Creating an index file. That is, data address values are sorted together with key values in the primary index file.

Referring to FIG. 2 as a specific example of log data, in the primary index file generation step S120, each key value included in A is the same as in B based on the data file generated in the data file generation step S110. The primary index file is created by sorting by group having key values. At this time, an index address value is added to each key value while generating a primary index file. That is, an index address value of 0 to 70 is added to the key value aaa included in B, an index address value of 80 to 140 is added to the key value aab, and an index address value of 150 to 180 is added to the key value aac.

3. Pre-index file creation step ( S130 )

In the pre-index file generation step S130, the data collection engine 100 uniquely sets the key values of the primary index file for each key value based on the primary index file generated in the primary index file generation step S120. Creating a dictionary index file by adding a range of index address values while sorting. That is, in the pre-index file generation step (S130), a dictionary index file is added by adding a range of index address values for duplicate key values based on the primary index file generated in the primary index file generation step (S120). Create Meanwhile, a dictionary index address value is added and stored in each key value of the dictionary index file.

Referring to FIG. 2, which uses log data as an example, the dictionary index file generation step (S130) generates a dictionary index file based on the primary index file. The dictionary index file contains one uniquely each key value (aaa, aab, aac ....) and an address for each duplicate key value (aaa, aab, aac ....) in the primary index file. Contains a range of values. Here, the range of address values for each key value is represented by a From index address value C and a To index address value D. That is, for the unique key value aaa, the starting index address value is 0 and the last index address value is 70, for the unique key value aab, the starting index address value is 80, the last index address value is 140, and another unique key value aac For, the starting index address value is 150 and the last index address value is added as 180 and stored.

4. Insert additional data ( S140 )

3 is a diagram illustrating a process of inserting additional data in a method of generating an index file according to the present invention with specific examples of log data. Additional data insertion step (S140) is, if there is additionally collected data, while the data collection engine 100 updates the data file, the primary index file and the dictionary index file, the data address value of the data file, primary index file The step of modifying and storing the range of the index address value and the index address value of the dictionary index file.

Referring to FIG. 3 using log data as an example, when data having a data address value of 950 is added at the end of the data file (1), the key value aab included in the field A of the data file is primary. The primary index file in which the index address value is modified is inserted into the last part of the sorted key value aab of the index file (②). In addition, as the key value aab having a data address value of 950 was inserted into the primary index file, the range of the index address value of the key value aab was modified to 80 to 150, and the range of the index address value of the key value aac was modified to 160 to 190. . Meanwhile, the range of the index address values of the key value aab and the key value aac, which are modifications of the primary index file, is also reflected and stored in the dictionary index file (③).

<Data retrieval method>

4 is a view for explaining a data retrieval method using the dictionary index file of the present invention. The data retrieval method using the inventor's dictionary index file is performed by the following procedure.

1. Obtaining an index address range S210 )

The index address value range obtaining step (S210) refers to a step in which the data search engine 200 acquires information on an index address value range of a key value to be searched by searching a dictionary index file. Meanwhile, in the step of obtaining the index address range (S210), the number of data including the key value to be searched is calculated based on the range of the index address value, compared with the total number of data, and then the data file is searched through the primary index file. The method may further include a search path determining step S215 for determining whether or not to search for a data file immediately. Here, when the ratio of the number of data including the key value to the total number of data is smaller than the preset number, the data file may be searched through the primary index file. For example, if the ratio of the number of data including the key value to the total number of data is less than 0.5, the data file can be searched through the primary index file, but differently set to 0.3, 0.4, or other numbers. Can be.

Referring to FIG. 4 using log data as an example, when data for key value aab is to be obtained, a range of index addresses 80 to 150 for key value aab is obtained through the dictionary index file (①). Here, it is possible to determine how many pieces of data including the key value aab exist in the data file by using a formula, and specifically, the data including the key value aab is stored in the data file through the formula (150-80) / 10 + 1 = 8. You can see that there are eight. If the total number of data is 1 billion and the ratio of the number of data including the key value to the total number of data is less than 0.5, if the data file is searched through the primary index file, the total number of data 10 Since the ratio of the number 8 of the data containing the key value aab to one billion is much smaller than 0.5, the data search engine 200 searches the data including the key value aab from the data file via the dictionary index file and the primary index file. Done.

2. Data Address value  Acquisition stage ( S220 )

In the data address value obtaining step (S210), the data search engine 200 searches for an index address value included in the index address value range obtained in the index address value range obtaining step (S210) from the primary index file and applies the index address value. Acquiring information on a corresponding data address value.

Referring to FIG. 4 using log data as an example, when searching a data file through a primary index file through a search path determining step (S215), an index address of a key value aab to be searched through a primary index file search The range of values is found to be 80 to 150, and data address values 50, 150, 250, 350, 450, 550, 650 and 950 for the key value aab are obtained (2).

3. Data Acquisition Step ( S230 )

The raw log data extraction step (S230) refers to a step in which the data search engine 200 obtains data corresponding to the data address value by searching the data address value found through the data address value acquisition step S220 in a data file.

Referring to FIG. 4 using log data as an example, a search is performed on a data file only for data address values of key values aab of 50, 150, 250, 350, 450, 550, 650, and 950. Obtain the corresponding data (③).

<Data Management System>

5 is a block diagram of a data management system (hereinafter, referred to as a data management system) using the inventor's dictionary index file. As shown in FIG. 5, the data management system using the dictionary index file according to the present invention includes a data collection engine 100, a data search engine 200, a first database unit 310, and a second database unit 320. It is configured to include a database unit 300 and the control unit 400. Since the data collection engine 100 generates the index file and the data search engine 200 searches for the data, it has already been described above, and thus the detailed description thereof will be omitted.

The data collection engine 100 generates a data file by adding data address values to the sorted data while sorting the data in which the field values are filled in the plurality of fields in a table form according to the collection order. In addition, a primary index file is generated by adding index address values to key values in a sorted order by sorting groups having the same key value with respect to a key, which is a selected field among a plurality of fields. The dictionary index file is generated by adding a range of index address values while uniquely sorting key values of the primary index file for each key value. At this time, the data collection engine 100 collects data from security devices or servers to generate a primary index file and a dictionary index file.

The data search engine 200 searches for a dictionary index file and obtains information on an index address value range of a key value to be searched. The index address value included in the obtained index address value range is searched in the primary index file to obtain information on the data address value corresponding to the index address value. Thereafter, the obtained data address value is searched in the data file to obtain data corresponding to the data address value. On the other hand, the data search engine 200 calculates the number of data including the key value to be searched based on the range of the index address value and compares it with the total number of data, and then searches the data file via the primary index file or data. It is possible to determine whether to search the file immediately. In this case, the data file may be searched through the primary index file when the ratio of the number of data including the key value to the total number of data is smaller than the preset number.

The data file, the primary index file, and the dictionary index file generated by the data collection engine 100 are stored in the database unit 300. Specifically, the data file generated by the data collection engine 100 and the primary index file are stored in the first database unit 310, and the dictionary index file generated by the data collection engine 100 is the second database unit. Stored at 320.

In the meantime, the data management system 100 generates a data file, a primary index file, and a dictionary index file so that the data collection engine 100 stores the data file in the first database unit 310 or the second database unit 320. ), And the controller 400 may control the data search engine 200 to search the data file based on the dictionary index file.

In addition, the data management system may further include an input unit (not shown) for inputting a specific key value to be searched by the user, and various means such as a keyboard, a mouse, and a touch screen may be used as the input unit. The input of a specific key value to be searched through the input unit may be performed by selecting any one of the index numbers created based on each field, and selecting a key value in the dictionary index file of the selected index number. For example, if index # 1 is selected from index # 1, index # 2, index # 3, and index # 4, then among the key values in the dictionary index file of index # 1 (for example, aaa, aab, aac) You can select one and enter the key value you want to search. On the other hand, after the index number is selected, the user may select a key value to be searched by directly inputting a key value to be searched.

In addition, the data management system may further include a display unit (not shown) capable of outputting data contents searched by the data search engine 200. Such a display unit may be added with a function capable of inputting a touch type to perform a role as an input unit.

While the present invention has been described in connection with what is presently considered to be the most practical and preferred embodiment, it is to be understood that the invention is not limited to the disclosed embodiments. Further, it is obvious that various modifications and variations can be made without departing from the scope of the technical idea of the present invention by anyone having ordinary skill in the art.

100: data collection engine
200: data search engine
300: database unit
310: first database portion
320: second database unit
400:

Claims (12)

A data file generation step of adding data address values to the sorted data and storing the data in which the field values are filled in the plurality of fields in a table form according to the collection order;
A primary index file generation step of adding index address values to and storing the key values according to the sorting order while sorting by group having the same key value with respect to a key which is one of the plurality of fields; And
A dictionary index file generation step of adding and storing a range of the index address value while uniquely sorting the key values of the primary index file for each key value. Way.
The method of claim 1,
In the primary index file generation step,
And the data address values are arranged together with the key values in the primary index file.
The method of claim 1,
In the dictionary index file generation step,
And a dictionary index address value is added to each key value of the dictionary index file.
The method of claim 1,
The method of generating the index file,
If there is additionally collected data, updating the data file, the primary index file and the dictionary index file, the data address value of the data file, the index address value of the primary index file and the dictionary index file An index file generation method comprising modifying and storing a range of index address values.
An index address value range obtaining step of obtaining information on an index address value range of a key value to be searched by searching a dictionary index file among the index files generated by any one of claims 1 to 4;
A data address value obtaining step of obtaining information on a data address value corresponding to the index address value by searching the index address value included in the obtained index address value range in a primary index file; And
And a data acquiring step of retrieving the acquired data address value from a data file to obtain data corresponding to the data address value.
6. The method of claim 5,
The index address value range obtaining step,
After calculating the number of data including the key value to be searched based on the range of the index address value and comparing it with the total number of data, whether to search the data file or the data file directly through the primary index file And a search path determining step of determining.
The method according to claim 6,
The search path determination step,
If the ratio of the number of data including the key value to the total number of data is less than a predetermined number, it is determined to search the data file via the primary index file, characterized in that How to retrieve data.
A data file is created by adding data address values to the sorted data while sorting the data in which the field values are filled in the plurality of fields in a table form according to the collection order, and a key which is any one selected from the plurality of fields. The primary index file is created by adding index address values to the key values according to the sorting order by sorting the groups having the same key value with respect to (Key), and uniquely storing the key values of the primary index file for each key value. a data collection engine generating a dictionary index file by adding the range of the index address values while sorting uniquely;
Search the dictionary index file to obtain information about an index address value range of a key value to be searched, and search the index address value included in the obtained index address value range in a primary index file to provide the index address value. A data search engine that obtains information on a corresponding data address value, and retrieves the obtained data address value from a data file to obtain data corresponding to the data address value; And
And a database unit for storing the data file, the primary index file and the dictionary index file.
The method of claim 8,
The data management system comprises:
Control the data collection engine to generate the data file, the primary index file, and the dictionary index file and store the data file in the first database unit or the second database unit;
And a control unit which controls the data search engine to allow the data search engine to search the data file based on the dictionary index file.
The method of claim 8,
The database unit,
A first database unit for storing the data file and the primary index file; And
And a second database unit for storing the dictionary index file.
The method of claim 8,
The data search engine,
After calculating the number of data including the key value to be searched based on the range of the index address value and comparing it with the total number of data, whether to search the data file or the data file directly through the primary index file Decide,
If the ratio of the number of data including the key value to the total number of data is less than a predetermined number, it is determined to search the data file via the primary index file, characterized in that Data management system.
A computer-readable recording medium having recorded thereon a program capable of generating and retrieving the primary index file and the dictionary index file according to any one of claims 1 to 7.

Images