CN116932850A - Data indexing method, device, electronic equipment and storage medium - Google Patents

Abstract

The application provides a data indexing method, a device, an electronic device and a storage medium, wherein the embodiment of the application can be applied to multimedia data indexing scenes such as video, voice and the like, and the method comprises the following steps: according to the inverted chain length of each index fragment, splicing inverted chain data with the inverted chain length not greater than a preset threshold value into a first index block, and splicing inverted chain data with the inverted chain length greater than the preset threshold value into a second index block; storing the first index block and the second index block in a storage block; establishing a hash table, wherein the hash table comprises a plurality of key values and code values corresponding to the key values, the key values respectively correspond to different index fragments, and the code values comprise index modes corresponding to the index fragments; and carrying out data indexing of the fragments to be indexed in the storage block according to the key values of the fragments to be indexed and the corresponding indexing modes. The technical scheme of the embodiment of the application rapidly acquires the inverted chain data of the fragments to be indexed.

Description

Data indexing method, device, electronic equipment and storage medium

Technical field

The present application relates to the field of information retrieval technology, specifically, to a data indexing method, device, electronic equipment and storage medium.

Background technique

In search engines, inverted index is a common method for data indexing in search engines. Most of the current inverted index methods use one search method for one zipper. In order to save memory in index storage, compression is performed, such as for postinglist( The storage design of the inverted chain includes uncompressed continuous storage, compressed storage with variable length encoding, compressed storage with PForDelta (inverted index compression algorithm), etc., and at the same time, the block method is used to split and store the extremely long inverted chain. Chain arrangement, use skiplist (skip list) between blocks to speed up search. When searching, a unified binary search or sequential search is used to find the document collection of a given term (index fragmentation).

The above-mentioned single inverted index storage method is compressed in the early stage, and the online decompression time during subsequent searches will increase the search delay. In addition, the binary index method prolongs the indexing time in some cases and cannot meet the needs of fast data index operations. Get the requirements for term document collection.

Contents of the invention

In order to solve the above technical problems, embodiments of the present application provide a data indexing method and device, electronic equipment, and computer-readable storage media.

According to one aspect of the embodiment of the present application, a data indexing method is provided, including: according to the inverted chain length of each index fragment, splicing inverted chain data whose inverted chain length is not greater than a preset threshold into a first index block, and splice the inverted chain data whose inverted chain length is greater than the preset threshold into a second index block; store the first index block and the second index block in a storage block; establish a hash table , the hash table includes a plurality of key values and a coding value corresponding to each key value, the plurality of key values respectively correspond to different index fragments, the coding value includes an indexing method corresponding to the index fragment, and each index fragment The indexing method of a slice is related to the index block where the inverted chain data of the corresponding index fragment is located; the data of the fragment to be indexed is indexed in the storage block according to the key value of the fragment to be indexed and the corresponding indexing mode.

According to one aspect of the embodiment of the present application, a data indexing device is provided, including: an index block acquisition module configured to, according to the length of the inversion chain of each index fragment, retrieve inversions whose length is not greater than a preset threshold. chain data is spliced into a first index block, and inverted chain data with an inverted chain length greater than the preset threshold is spliced into a second index block; a storage module is configured to combine the first index block and the second index block The index block is stored in the storage block; the hash table creation module is configured to create a hash table. The hash table includes a plurality of key values and a coding value corresponding to each key value. The plurality of key values respectively correspond to different Index fragmentation, the encoding value includes the indexing mode of the corresponding index fragmentation, and the indexing mode of each index fragmentation is related to the index block where the inverted chain data of the corresponding index fragmentation is located; the index module is configured to be based on the fragmentation to be indexed The key value and the corresponding indexing method are used to index the data of the fragment to be indexed in the storage block.

In one embodiment, the index block acquisition module includes:

An alignment unit configured to align the inverted chain data of each index fragment whose inverted chain length is greater than a preset threshold;

The second index block acquisition unit is configured to splice the aligned inverted chain data of each index fragment to obtain the second index block.

In one embodiment, the number of storage blocks is multiple, and the storage module includes:

A first storage unit configured to store the data of the first index block in the first storage block;

The second storage unit is configured to store the data of the second index block in the second storage block in a preset byte alignment manner.

In one embodiment, the coded value of the hash table also includes the storage location of the inverted chain data corresponding to the index fragment in the first storage block or the second storage block; the index module includes:

A first index data acquisition unit configured to confirm, based on the hash table, the first key value corresponding to the fragment to be indexed and the indexing method and storage location corresponding to the first key value;

A first indexing unit configured to, if the first key value corresponds to a first indexing method, index the inversion of the to-be-indexed fragment in the first storage block according to the first indexing method and the corresponding storage location. chain data;

The second indexing unit is configured to, if the first key value corresponds to the second indexing method, index the inversion of the to-be-indexed fragment in the second storage block according to the second indexing method and the corresponding storage location. chain data.

In one embodiment, the storage module includes:

A third storage unit configured to store the first index block and the second index block in the storage block in a preset byte alignment manner, wherein the length of the storage block is equal to or greater than the The sum of the lengths between the first index block and the second index block, and the data of the first index block in the storage block is stored after the data of the second index block.

In one embodiment, the coded value of the hash table also includes the storage location of the inverted chain data corresponding to the index fragment in the storage block; the index module includes:

The second index data acquisition unit is configured to confirm the second key value corresponding to the fragment to be indexed and the indexing method and storage location corresponding to the second key value based on the hash table;

The third indexing unit is configured to index the inverted chain data of the fragment to be indexed in the storage block according to the third indexing method and the corresponding storage location if the second key value corresponds to the third indexing method. , the third indexing method is set for indexing the inverted chain data in the first index block;

The fourth indexing unit is configured to index the inverted chain data of the fragment to be indexed in the storage block according to the fourth indexing method and the corresponding storage location if the second key value corresponds to the fourth indexing method. , the fourth indexing method is set for indexing the inverted chain data in the second index block.

In one embodiment, the hash table creation module includes:

The initial hash table creation unit is configured to preset an initial hash table, where the initial hash table includes a plurality of initial key values and an initial coding value corresponding to each initial key value;

The key value acquisition unit is configured to overwrite the initial key value with the hash value of each index fragment, and obtain multiple key values;

The index mode allocation unit is configured to allocate an index mode to the corresponding index fragment according to the index block where each inverted chain data is located;

The coded value acquisition unit is configured to overwrite the position of the inverted chain data of each index fragment in the storage block and the corresponding index mode with the corresponding initial coded value to obtain the hash table.

In one embodiment, the coded value acquisition unit includes:

The area division section is configured to divide each initial encoding value into areas to obtain the index mode area, data length area and offset area corresponding to each initial encoding value;

The index mode area coverage section is configured to cover the index mode information corresponding to each index shard in the corresponding index mode area;

The data length area coverage section is configured to cover the inverted chain length information of each index fragment in the corresponding data length area;

The offset area covering block is configured to cover the starting position information of the inverted chain data of each index fragment in the storage block with the corresponding offset area to obtain the hash table.

In one embodiment, the indexing method includes a binary indexing method set for indexing the inverted chain data in the first index block, and indexing for the inverted chain data in the second index block. The set instruction set indexing method; the data indexing device also includes:

An index rate acquisition module configured to index the inverted chain of each index fragment based on the binary indexing method and the instruction set indexing method, and obtain the first index rate and the second index rate of each index fragment accordingly;

The preset threshold acquisition module is configured to compare the numerical size between the first index rate and the second index rate corresponding to each index fragment in the preset length order according to the inverted chain length of each index fragment, and calculate the value according to the obtained The results are compared to determine the preset threshold.

According to an aspect of an embodiment of the present application, an electronic device is provided, including one or more processors; a storage device configured to store one or more computer programs. When the one or more computer programs are processed by the Or when executed by multiple processors, the electronic device implements the data indexing method as described above.

According to an aspect of an embodiment of the present application, a computer-readable storage medium is provided, with computer-readable instructions stored thereon. When the computer-readable instructions are executed by a processor of the computer, the computer is caused to perform the above-mentioned steps. Data indexing methods.

According to an aspect of an embodiment of the present application, a computer program product or a computer program is provided, the computer program product or the computer program including computer instructions, and the computer instructions are stored in a computer-readable storage medium. The processor of the computer device reads the computer instructions from the computer-readable storage medium, and the processor executes the computer instructions, so that the computer device performs the data indexing method provided in the above various optional embodiments.

According to one aspect of an embodiment of the present application, a computer program product is provided, including a computer program that implements the steps in the template generation method as described above when executed by a processor.

In the technical solution provided by the embodiments of the present application, the inverted chain data is divided into different index blocks based on the inverted chain length information, and different indexing methods are assigned to different index blocks to use a hash table to determine the index to be indexed The indexing method of shards enables fast indexing of inverted chain data corresponding to the index shards.

It should be understood that the above general description and the following detailed description are only exemplary and explanatory, and do not limit the present application.

Description of the drawings

The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate embodiments consistent with the application and together with the description, serve to explain the principles of the application. Obviously, the drawings in the following description are only some embodiments of the present application. For those of ordinary skill in the art, other drawings can be obtained based on these drawings without exerting creative efforts. In the attached picture:

Figure 1 is a schematic diagram of an implementation environment involved in this application;

Figure 2 is a flow chart of a data indexing method according to an exemplary embodiment of the present application;

Figure 3 is a histogram of inverted chain length distribution of each index shard shown in an exemplary embodiment of the present application;

Figure 4 is a schematic diagram of inverted chain data distribution according to an exemplary embodiment of the present application;

Figure 5 is a schematic structural diagram of a first index block and a second index block according to an exemplary embodiment of the present application;

Figure 6 is a schematic structural diagram of a hash table according to an exemplary embodiment of the present application;

Figure 7 is a schematic diagram of the regional structure of coded values according to an exemplary embodiment of the present application;

Figure 8 is a flow chart of step S210 in the embodiment shown in Figure 2 in an exemplary embodiment;

Figure 9 is a schematic diagram of the completion processing operation according to an exemplary embodiment of the present application;

Figure 10 is a flow chart of step S230 in the embodiment shown in Figure 2 in an exemplary embodiment;

Figure 11 is a flow chart of step S270 in the embodiment shown in Figure 2 in an exemplary embodiment;

Figure 12 is a flow chart of step S270 in the embodiment shown in Figure 2 in another exemplary embodiment;

Figure 13 is a schematic diagram of a memory block structure according to an exemplary embodiment of the present application;

Figure 14 is a flow chart of step S250 in the embodiment shown in Figure 2 in another exemplary embodiment;

Figure 15 is a flowchart of step S1470 in the embodiment shown in Figure 14 in another exemplary embodiment;

Figure 16 is a flow chart of a data indexing method according to another exemplary embodiment of the present application;

Figure 17 is a schematic structural diagram of a data indexing device according to an exemplary embodiment of the present application;

FIG. 18 shows a schematic structural diagram of a computer system suitable for implementing an electronic device according to an embodiment of the present application.

Detailed ways

Reference will now be made in detail to exemplary embodiments, examples of which are illustrated in the accompanying drawings. When the following description refers to the drawings, the same numbers in different drawings refer to the same or similar elements unless otherwise indicated. The implementations described in the following exemplary embodiments do not represent all implementations consistent with this application. Rather, they are merely examples of apparatus and methods consistent with aspects of the application as detailed in the appended claims.

The block diagrams shown in the figures are functional entities only and do not necessarily correspond to physically separate entities. That is, these functional entities may be implemented in software form, or implemented in one or more hardware modules or integrated circuits, or implemented in different networks and/or processor devices and/or microcontroller devices. entity.

The flowcharts shown in the drawings are only illustrative, and do not necessarily include all contents and operations/steps, nor must they be performed in the order described. For example, some operations/steps can be decomposed, and some operations/steps can be merged or partially merged, so the actual order of execution may change according to the actual situation.

It should also be noted that the “multiple” mentioned in this application refers to two or more. "And/or" describes the relationship between related objects, indicating that there can be three relationships. For example, A and/or B can mean: A exists alone, A and B exist simultaneously, and B exists alone. The character "/" generally indicates that the related objects are in an "or" relationship.

Artificial Intelligence (AI) is a theory, method, technology and application system that uses digital computers or machines controlled by digital computers to simulate, extend and expand human intelligence, perceive the environment, acquire knowledge and use knowledge to obtain the best results. In other words, artificial intelligence is a comprehensive technology of computer science that attempts to understand the essence of intelligence and produce a new intelligent machine that can respond in a similar way to human intelligence. Artificial intelligence is the study of the design principles and implementation methods of various intelligent machines, so that the machines have the functions of perception, reasoning and decision-making.

Artificial intelligence technology is a comprehensive subject that covers a wide range of fields, including both hardware-level technology and software-level technology. Basic artificial intelligence technologies generally include technologies such as sensors, dedicated artificial intelligence chips, cloud computing, distributed storage, big data processing technology, operation/interaction systems, mechatronics and other technologies. Artificial intelligence software technology mainly includes computer vision technology, speech processing technology, natural language processing technology, and machine learning/deep learning.

Machine Learning (ML) is a multi-field interdisciplinary subject involving probability theory, statistics, approximation theory, convex analysis, algorithm complexity theory and other disciplines. It specializes in studying how computers can simulate or implement human learning behavior to acquire new knowledge or skills, and reorganize existing knowledge structures to continuously improve their performance. Machine learning is the core of artificial intelligence and the fundamental way to make computers intelligent. Its applications cover all fields of artificial intelligence. Machine learning and deep learning usually include artificial neural networks, belief networks, reinforcement learning, transfer learning, inductive learning, teaching learning and other technologies.

The data indexing methods and devices, electronic devices, and storage media proposed in the embodiments of this application involve artificial intelligence technology, machine learning, and other technologies. These embodiments will be described in detail below.

First, please refer to Figure 1, which is a schematic diagram of an implementation environment involved in this application. The implementation environment includes a terminal 100 and a server 200. The terminal 100 and the server 200 communicate through a wired or wireless network.

It should be understood that the number of terminal devices 100 and servers 200 in Figure 1 is only illustrative. According to actual needs, there can be any number of terminals 100 and servers 200 .

In some embodiments of the present application, the data indexing method may be executed by the server 200 , and accordingly, the data indexing device is configured in the server 200 . The terminal 100 is used to receive multiple index fragments and inverted chains corresponding to the index fragments. One index fragment corresponds to one inverted chain, and the inverted link data in the inverted chain is index data related to the corresponding index fragments. , and the index data obtained by different index fragments is different, which is reflected in the inverted chain data, that is, the inverted chain lengths of each index fragment are different, and then the terminal 100 sends each index fragment and the inverted chain to the server 200 . Among them, the server side 200 processes the index fragments and the inverted chain, first splices the inverted chain data into different index blocks according to the length of the inverted chain of each index fragment, and stores the index blocks, and then provides different data for different index fragments. Different indexing methods are set for the inverted chain data in the index block to index the data in the stored data using the hash table to determine the indexing method of the fragments to be indexed, and then the server 200 also sends the data indexing results to the terminal 100 , the indexing results of the fragments to be indexed can be visualized through the display module provided by the terminal 100 .

Exemplarily, after receiving multiple index fragments and their corresponding inverted links, the terminal 100 sends the index fragments and their corresponding inverted links to the server 200. The chain length is to splice the inverted chain data whose length is not greater than the preset threshold into the first index block, and the inverted chain data whose length is greater than the preset threshold is spliced into the second index block; The first index block and the second index block are stored in the storage block; a hash table is established. The hash table includes multiple key values and the encoding values corresponding to each key value. The multiple key values correspond to different index fragments and the encoding values. Including the indexing method of the corresponding index fragment, the indexing method of each index fragment is related to the index block where the inverted chain data of the corresponding index fragment is located; then the server 200 needs to index the inverted chain data of the pending index fragment. , index the data of the fragment to be indexed in the storage block according to the key value of the fragment to be indexed and the corresponding indexing method, to obtain the inverted chain data of the fragment to be indexed.

Among them, the terminal 100 includes but is not limited to mobile phones, computers, intelligent voice interaction devices, smart home appliances, vehicle-mounted terminals, aircraft, etc., such as smart phones, tablets, laptops, computers and other electronic devices that can realize image visualization. This document No restrictions are imposed. Embodiments of the present invention can be applied to the field of data indexing, including but not limited to various scenarios such as video search, text search, and music search. The server 200 can be an independent physical server, or a server cluster or distributed system composed of multiple physical servers. Multiple servers can form a blockchain, and the server is a node on the blockchain. The server 200 It can also provide cloud services, cloud databases, cloud computing, cloud functions, cloud storage, network services, cloud communications, middleware services, domain name services, security services, CDN (Content Delivery Network, content distribution network), as well as big data and artificial intelligence Cloud servers for basic cloud computing services such as intelligent platforms are not subject to any restrictions here.

Figure 2 is a flow chart of a data indexing method according to an exemplary embodiment. The data indexing method can be applied to the implementation environment shown in Figure 1 and is specifically executed by the server 200 in the implementation environment. It should be understood that It should be noted that this method can also be used in other exemplary implementation environments and specifically executed by devices in other implementation environments. This embodiment does not limit the implementation environments to which this method is applicable.

As shown in Figure 2, in an exemplary embodiment, the method may include steps S210 to S270, which are described in detail as follows:

Step S210: According to the inverted chain length of each index fragment, splice the inverted chain data whose inverted chain length is not greater than the preset threshold into the first index block, and combine the inverted chain data whose inverted chain length is greater than the preset threshold. The data is spliced into the second index block.

An index shard corresponds to an inverted chain. The inverted chain data in the inverted chain includes documents and related information that meet the index sharding conditions. Different index shards correspond to different documents and related information, so different index shards correspond to different documents and related information. The length of the inverted chain of the film may also be different.

In this embodiment, the inverted chain data corresponding to each index fragment can be spliced into different index blocks according to the inverted chain length of the index fragment (ie, term) for subsequent inverted chain data to be indexed. index.

First, a threshold can be preset. The preset threshold can be confirmed based on the speed of inverted chain indexing using different methods for different inverted chain lengths. For example, binary indexing is usually used to index the data of the shards to be indexed. , but when the inverted chain length is too long, the binary indexing method is slow, and other indexing methods can be selected to compare the indexing speed, such as each instruction set in Intel SIMD (IntelSingle Instruction Multiple DataIntel Single Instruction Multiple Data Technology) , each instruction set in SISD (Single Instruction Single Data, single instruction single data technology), etc. There are no specific restrictions on other indexing methods here.

Then, inverted chain data of different lengths can be indexed through different indexing methods, and a preset threshold is determined based on the indexing rate of inverted chain data of different inverted chain lengths in different indexing methods. The inverted chain length is greater than the preset threshold. The rate of index fragments with a set threshold when indexed through index method A is greater than the rate when indexed through index method B. The index fragment whose inverted chain length is not greater than the preset threshold has a faster rate when indexed through index method A. The rate is lower than the rate when indexing through index mode B, and then multiple index fragments can be spliced into different index blocks according to the preset threshold.

Of course, the preset thresholds in different indexers are different, which are related to the hardware environment, compiler, and indexing method in which the indexer runs.

For example, Table 1 shows the length distribution of each index fragment (term) in the P1 index library in a certain index platform, and Figure 3 shows the inverted chain length distribution diagram of each index fragment in the P1 index. From Table 1 and Figure 3 It can be seen that 97% of the inverted chain lengths are concentrated in the length interval [1,720], and then the binary index method of the C++ standard library and the binary index method based on SIMD acceleration are used to index each inverted chain in the P1 index library. The data is indexed and it is concluded that when the length of the inverted chain is less than 720, the search speed of the binary search using the C++ standard library is faster than the binary index method based on SIMD (that is, the instruction set index method. The instruction set index method can be used through the SIMD instruction The centralized instructions accelerate the binary index method, such as AVX2 acceleration instructions to accelerate binary search).

Table 1

When the length of the inverted chain is greater than 720, the binary index method based on SIMD acceleration can obtain the optimal performance. That is, when indexing in the P1 index library, the preset threshold can be set to 720 to reduce the index in the P1 index library. The index fragments are divided into two different index blocks. It can be seen that the binary index method has a faster indexing rate when the inverted chain length is small, but when the inverted chain length is large, its indexing rate cannot meet the fast Data indexing requirements, and the binary index method is still used at this time, which will cause increased latency.

All inverted chain data in the P1 index library are distributed as shown in Figure 4. Of course, the figure only shows some index fragments with their inverted chain data, and there are also index fragments with the same inverted chain length. Fragment, here for simplicity, the inverted chain data with the same inverted chain length is not shown. In Figure 4, term represents the index fragment, docid is the number of the document related to the index fragment, and docid constitutes the inverted chain data corresponding to the term.

Then, the inverted chain data corresponding to the terms whose inverted chain length is less than or equal to 720 in Figure 4 are spliced to obtain the first index block as shown in Figure 5. At the same time, the inverted chain data corresponding to the term whose inverted chain length is greater than 720 is obtained. The row chain data is spliced to obtain the second index block as shown in Figure 5, and when subsequently indexing the data in the index block, use the corresponding indexing method with a higher speed, such as inversion in the first index block The chain data uses the binary index method, and the inverted chain data in the second index block uses the instruction set index method in SIMD.

Of course, since the terms whose inverted chain length is greater than 720 here use binary index based on SIMD, before splicing the inverted chain data corresponding to the terms whose inverted chain length is greater than 720, the inverted chain data corresponding to each term will also be spliced. The chaining data is rounded to multiples of 1024 to meet the needs of SIMD instructions and improve the indexing speed of SIMD instructions.

When splicing the inverted chain data, the splicing order of the inverted chain data corresponding to each term may be uncertain. In Figure 4, the inverted chain data corresponding to term1 can be spliced after the inverted chain data corresponding to term3, but each The order of docids in the inverted chain data corresponding to the term must be fixed. For term3 in Figure 4, the order of docid numbers in the inverted chain data must be fixed, that is, docid6, docid7, docid8, and docid9 in the first index block. splicing in order.

Step S230: Store the first index block and the second index block in the storage block.

In this embodiment, the first index block and the second index block can be stored in one storage block, or they can be stored separately. However, when storing data in the index block, it is necessary to ensure that the storage method is consistent with the first index block or the second index block. Corresponds to the preset indexing method in the block.

For example, when the first index block corresponds to the preset binary index method and the second index block presets the instruction set index method, since the SIMD instruction set index method is not efficient at 4 bytes, in order to ensure the normal use of the index method , then when storing the second index block, it needs to be stored in a 4-byte aligned manner. Therefore, regardless of whether the first index block and the second index block are stored in the same storage block, it is necessary to ensure that the second index block is aligned with 4 bytes. Aligned for storage.

Of course, the above is only an exemplary indexing method, and other indexing methods can also be used. Different indexing methods can have different storage methods for corresponding index blocks. For example, 8-byte alignment, 16-byte alignment, etc. can also be used. storage method to ensure the accuracy and efficiency of subsequent data indexing based on this indexing method. There are no specific restrictions here.

Step S250: Create a hash table. The hash table includes a plurality of key values and a coded value corresponding to each key value. The coded value includes an indexing method corresponding to the index fragment.

In this embodiment, the inverted chain data in the storage block can be indexed through a hash table. Figure 6 is a structural diagram of a hash table, which includes multiple key values (keys) and each key value. Corresponding encoding value (value), a key value corresponds to an index shard, the key value can be the hash value corresponding to the index shard, or it can also be the name of the corresponding index shard (each key value as shown in Figure 6 That is the name of the index fragment), there are no specific restrictions here, the encoding value is represented by structural data, such as uint64_t (64-bit integer value, 8 bytes), uint32_t (32-bit integer value, 4 words) section) and other structure data, as shown in Figure 6, each encoding value is represented by uint64_t.

The encoded value in this embodiment needs to implement the indexing of the inverted chain data corresponding to the key value (ie, index fragment), which includes the indexing method of the corresponding index fragment and the storage location in the storage block. In this embodiment The encoding value can be divided into three areas, as shown in Figure 7, the index mode area, the data length area and the offset area. This index mode area is the index mode corresponding to the index fragmentation, which is the same as each index block in step S210. The index method set in is the same. The data length area and offset area determine the storage location of the corresponding inverted chain data. Specifically, the offset area is the offset of the inverted chain data corresponding to the index fragment in the storage fast. offset((The offset method returns or sets the offset (position) of the matching element relative to the document and returns the offset coordinate of the first matching element). The data length area is the inverted chain data in the corresponding index fragment in the storage block. The length, that is, the length of the index from the offset position to ensure that all inverted chain data corresponding to the index fragments are searched.

Step S270: Index the data of the fragment to be indexed in the storage block according to the key value of the fragment to be indexed and the corresponding indexing method.

In this embodiment, after obtaining the hash table and storage block, if it is necessary to index the fragment to be indexed, the corresponding key value and the encoding value corresponding to the key value are confirmed in the hash table according to the fragment to be indexed, Then according to the indexing method, offset position, and data length in the encoding value, the inverted chain data of the fragment to be indexed can be indexed.

In current indexes, multiple terms are often co-indexed, and the intersection operation of multiple terms is very frequent. Users will experience it almost every time they search. How to quickly complete the intersection operation to obtain a document collection containing multiple terms? is a common problem faced by search engines. The data indexing method proposed in this embodiment can also be used for multi-term intersection operations in the inverted retrieval process, that is, through hash tables and storage blocks, inverted indexes can be quickly Index the fragmented document collection (inverted chain data), and then interact with the multi-term document collection through skip tables to quickly obtain the index results.

In this embodiment, inverted chain length distribution information is used to match inverted chain data of different lengths to different indexing methods, and the optimal preset of inverted chain length is determined based on the operating environments of different indexing platforms and the types of indexing methods. Threshold, and also select a more efficient indexing method for the inverted chain data of each index shard; at the same time, based on the indexing method, different storage methods are also set to better match the indexing method and the storage method. In this storage and Under the best match of the search algorithm, better performance can be obtained, thereby greatly reducing the latency on the search link and providing users with better searches.

FIG. 8 is a flowchart of step S210 in the embodiment shown in FIG. 2 in an exemplary embodiment. As shown in Figure 8, in an exemplary embodiment, step S210 splices the inverted chain data whose length is not greater than the preset threshold into a first index block according to the inverted chain length of each index fragment, and The process of splicing inverted chain data with an inverted chain length greater than a preset threshold into a second index block may include steps S810 to S830, which are described in detail as follows:

Step S810: Align the inverted chain data of each index fragment whose inverted chain length is greater than the preset threshold.

In this embodiment, for inverted chain data that requires a special indexing method, alignment processing is first performed when splicing to obtain the index block.

If the inverted chain data in the second index block is indexed more efficiently using the non-binary index method, alignment processing is performed first according to the preset index method requirements. For example, when searching through the instruction set index method, due to SIMD is divided into blocks of 1024 int32_t. In order to meet the requirements of the instruction set index method, the value 1024 is used to complete the inverted chain data. When the length of the last block of the inverted chain is less than 1024 int32_t, 0x7FFFFFFF(int type) to fill in the missing tail (as shown in Figure 9). After filling in, since the inverted chain data is 1024, it can meet the needs of int32_ when indexing through the instruction set. At the same time , since it is an integer multiple of 1024, it can greatly improve the indexing speed.

Of course, the 0x7FFFFFFFF here is only for the example line. Since 0x7FFFFFFFF is the maximum value of an integer, it can be quickly filled. In other cases, other digits can also be used for filling, and there are specific restrictions here; at the same time , the completion according to 1024 is also exemplary, that is, for the instruction set indexing method proposed in this embodiment, in other indexing methods, the inverted chain data can also be completed through other alignment methods according to the requirements of the indexing method.

Step S830: Splice the aligned inverted chain data of each index fragment to obtain a second index block.

In this embodiment, after the index fragments are aligned, the inverted chain data of each index fragment is spliced. For the splicing process, please refer to step S210, that is, the inverted chain data corresponding to the two index fragments is spliced. The order between docids can be changed, but the order between docids within the inverted chain data corresponding to a single index shard cannot be changed.

In this embodiment, according to the needs of different indexing methods, the inverted chain data in the corresponding indexing method is first aligned and then spliced. On the basis of meeting the needs of the indexing method, it can also improve the speed of subsequent indexing through this method. and accuracy.

FIG. 10 is a flowchart of step S230 in the embodiment shown in FIG. 2 in an exemplary embodiment. As shown in Figure 10, in an exemplary embodiment, the number of storage blocks is multiple. The process of storing the first index block and the second index block in the storage block in step S230 may include steps S1010 to step S1030. Details The introduction is as follows:

Step S1010: Store the data of the first index block in the first storage block.

In this embodiment, the length of the inverted chain in the first index block is short. In this case, the binary index method is more efficient. The binary index method does not require a special storage method, so the data in the first index block can be directly stored. In a storage block, the memory length of the first storage block may be the same as or slightly larger than the memory length of the first index block.

Step S1030: Store the data of the second index block in the second storage block in a preset byte alignment manner.

The length of the inverted chain in the second index block is longer. In this case, the indexing delay using the binary index method is longer. Therefore, other index methods can be set to index the inverted chain data in the second index block. Different The indexing method requires different storage methods. For example, for the instruction set indexing method proposed above, it is processed according to 4 bytes during indexing. Therefore, when the data of the second index block is stored, it is also aligned according to 4 bytes. The method stores the data of the second index block in the second storage block.

Of course, the above is just an example. For the instruction set indexing method, it can also be stored in other byte-aligned methods, such as 8 bytes, 16 bytes, etc., which can realize subsequent indexing functions, but using 4 Bytes, its performance will be better; and for different indexing methods, according to the way they process data, different byte alignments can be set for storage to improve the efficiency of subsequent data indexing. There is no byte alignment here. be limited in specific ways.

In this embodiment, different index blocks are stored in different storage blocks. At the same time, different data storage methods are set according to the different indexing methods corresponding to the index blocks. By matching the storage method and the indexing method, a better data storage method can be obtained. Data indexing performance, greatly reducing data indexing delay.

FIG. 11 is a flowchart of step S270 in the embodiment shown in FIG. 2 in an exemplary embodiment. As shown in Figure 11, in an exemplary embodiment, the number of storage blocks in this method is multiple, and after it is applied to the storage method shown in Figure 10, step S270 is based on the key value of the fragment to be indexed and the corresponding The process of indexing the data of the fragments to be indexed in the storage block using the indexing method may include steps S1110 to S1150. The details are as follows:

Step S1110: Confirm the first key value corresponding to the fragment to be indexed and the indexing method and storage location corresponding to the first key value based on the hash table.

In this embodiment, when the inverted chain data of the fragment to be indexed needs to be indexed, its corresponding first key value can be confirmed in the hash table through the fragment to be indexed, and the encoding value corresponding to the first key value can be determined at the same time. As shown in Figure 2, the first index mode of the fragment to be indexed is determined according to the index mode area in the coded value, and the number of inverted chain data of the fragment to be indexed is determined according to the data length area and offset area in the coded value. The storage location in the block, and the corresponding indexing method can indicate the storage block where the inverted chain data of the fragment to be indexed is located; if the inverted chain data of the fragment to be indexed is located in the first index block, the first indexing method corresponds to The indexing mode in the first index block, and indicates that the inverted chain data of the fragment to be indexed is stored in the first storage block. If the inverted chain data of the fragment to be indexed is located in the second index block, then the first index The mode corresponds to the indexing mode in the second index block, and indicates that the inverted chain data of the fragment to be indexed is stored in the second storage block.

Step S1130: If the first key value corresponds to the first indexing method, index the inverted chain data of the fragments to be indexed in the first storage block according to the first indexing method and the corresponding storage location.

In this embodiment, the first indexing method is set for indexing the inverted chain data in the first index block, that is, it is set for indexing the inverted chain data stored in the first storage block. Therefore, if The index mode area in the first key value corresponds to the first index mode, which proves that the fragment to be indexed is located in the first index block and the first storage block. Then, according to the first index mode and the first key value indicated in The storage location indexes the inverted chain data of the shard to be indexed in the first storage block.

Step S1150: If the first key value corresponds to the second indexing method, index the inverted chain data of the fragments to be indexed in the second storage block according to the second indexing method and the corresponding storage location.

In this embodiment, the second indexing method is set for indexing the inverted chain data in the second index block, that is, it is set for indexing the inverted chain data stored in the second storage block. Therefore, if The index mode area in the first key value corresponds to the second index mode, which proves that the fragment to be indexed is located in the second index block and the second storage block. Then, according to the second index mode and the index indicated in the first key value, The storage location indexes the inverted chain data of the shard to be indexed in the second storage block.

This embodiment proposes that when different index blocks are stored in different storage blocks, the indexing method and storage location of the data index for the fragment to be indexed can be confirmed based on the key value and coding value of the fragment to be indexed in the hash table. , In this way, different indexing methods are used to index different fragments to be indexed, which greatly improves the indexing efficiency.

FIG. 12 is a flowchart of step S270 in the embodiment shown in FIG. 2 in another exemplary embodiment. As shown in Figure 12, in an exemplary embodiment, the first index block and the second index block are stored in a storage block, and step S270 is performed in the storage block according to the key value of the fragment to be indexed and the corresponding indexing method. The process of indexing the data of the fragments to be indexed may include steps S1210 to S1250, which are described in detail as follows:

Step S1210: Confirm the second key value corresponding to the fragment to be indexed and the indexing method and storage location corresponding to the second key value based on the hash table.

In this embodiment, the first index block and the second index block are stored in one storage block, and the length of the storage block is equal to or greater than the sum of the lengths between the first index block and the second index block. Refer to the steps in Figure 10 S1030, the second index block needs to be stored in a preset byte alignment manner.

In order to ensure that the storage space is not wasted, the length of the storage block can be set to the first index block and the second index block. At this time, the data in the first index block and the second index block can be stored in the storage block. , and in order to ensure that the data in the second index block is stored according to the preset bytes, the data in the second index block needs to be stored first, and then the data in the first index block is stored, as shown in Figure 13 The structural diagram of the memory block in one embodiment is shown.

Of course, the length of the storage block can also be greater than the sum of the lengths between the first index block and the second index block. In this case, the data of the first index block is not forced to be stored after the data of the second index block. It only needs to satisfy The second index block can be completely stored in preset bytes, ensuring that the data in the second index block is stored in preset bytes to match the indexing method in the second index block, and the second index can be subsequently updated. Increases the rate at which data is indexed when data in a block is indexed.

In this embodiment, when it is necessary to index the inverted chain data of the fragment to be indexed, the corresponding second key value can be confirmed in the hash table through the fragment to be indexed, and the encoding value corresponding to the second key value can be determined at the same time. For specific steps, please refer to step S1110 in Figure 11.

Step S1230: If the second key value corresponds to the third indexing method, index the inverted chain data of the fragments to be indexed in the storage block according to the third indexing method and the corresponding storage location.

The third indexing method is set for indexing the inverted chain data in the first index block. In this embodiment, the third indexing method is set for indexing the inverted chain data in the first index block. Therefore, , if the indexing mode area in the second key value corresponds to the third indexing mode, it proves that the fragment to be indexed is located in the first index block, and the storage location indicated in the third indexing mode and the second key value can be found in Index the inverted chain data of the shards to be indexed in the storage block.

Step S1250: If the second key value corresponds to the fourth indexing method, index the inverted chain data of the fragments to be indexed in the storage block according to the fourth indexing method and the corresponding storage location.

The fourth indexing method is set for indexing the inverted chain data in the second index block. In this embodiment, the fourth indexing method is set for indexing the inverted chain data in the second index block. Therefore, , if the index mode area in the second key value corresponds to the fourth index mode, it proves that the fragment to be indexed is located in the second index block, and then it can be based on the fourth index mode and the storage location indicated in the second key value. Index the inverted chain data of the shards to be indexed in the storage block.

In this embodiment, it is proposed that when different index blocks are stored in the same storage block, it is necessary to ensure the matching of the indexing method and the storage method according to the corresponding indexing method in the index block, so as to improve the indexing efficiency. The key value and coding value of the shard in the hash table confirm the indexing method and storage location of the shard data to be indexed. In this way, different shards to be indexed are indexed through different indexing methods, which greatly improves the indexing efficiency. .

FIG. 14 is a flowchart of step S250 in the embodiment shown in FIG. 2 in an exemplary embodiment. As shown in Figure 14, in an exemplary embodiment, the process of establishing the hash table in step S270 may include steps S1410 to step S1470, which are described in detail as follows:

Step S1410: Default initial hash table.

In this embodiment, an initial hash table (hashmap) is first created. The initial hash table includes multiple initial key values and initial encoding values corresponding to each initial key value. The initial key values are used to subsequently fill in the corresponding index points. The data of the slice, the initial encoding value is used to subsequently fill in the index method and storage location of the corresponding index slice.

Step S1430: Overwrite the initial key value with the hash value of each index fragment to obtain multiple key values.

In this embodiment, an initial key value may correspond to an index fragment, and then the hash value of the index fragment is filled in the corresponding initial key value to obtain a key value that can be used to indicate the index fragment.

Step S1450: Allocate an index mode to the corresponding index fragment according to the index block where each inverted chain data is located.

In this embodiment, the indexing method is allocated to the index fragments in the index block according to different index blocks. The indexing method of the inverted chain data in the same index block is the same, and the indexing method of the inverted chain data in different index blocks is different. Specifically Reference may be made to the index mode setting in step S210 in FIG. 2 .

Step S1470: Overwrite the position of the inverted chain data of each index fragment in the storage block and the corresponding index method with the corresponding initial encoding value to obtain a hash table.

As proposed in the above embodiment, the index block is stored in the storage block, that is, the inverted chain data in the index block is also stored in the storage block. Therefore, the index of each index shard can be stored in the storage block through the corresponding inverted data. The position of the inverted chain data of each index fragment in the storage block and the corresponding index method are overwritten with the corresponding initial encoding value to obtain the corresponding encoding value. In this way, through steps S1410 to step S1470, that is A hash table is available for data indexing.

Of course, the number of storage blocks can be one or more. When the number of storage blocks is multiple, the index method can also indicate the storage block where the inverted chain data corresponding to the key value is located. For details, please refer to Figure 10 to Figure 13 The scheme described.

In this embodiment, a hash table construction method is proposed to construct a hash table for data indexing through the above method. When data indexing is required, only the fragments to be indexed are known, and the corresponding key can be confirmed through the hash table. value and encoding value, thereby determining the indexing method and storage location corresponding to the fragment to be indexed to index the rehearsal data, thereby greatly improving the indexing rate.

FIG. 15 is a flowchart of step S1470 in the embodiment shown in FIG. 14 in an exemplary embodiment. As shown in Figure 15, in an exemplary embodiment, step S1470 overwrites the position of the inverted chain data of each index fragment in the storage block and the corresponding index mode with the corresponding initial encoding value to obtain the hash table. The process may include steps S1510 to S1570, which are described in detail as follows:

Step S1510: Divide each initial encoding value into regions to obtain the index mode area, data length area and offset area corresponding to each initial encoding value.

In this embodiment, the initial coded value is divided into regions to obtain the coded value area structure as shown in Figure 7. Of course, what is shown in Figure 7 is an exemplary structure in which the coded value is represented by uint64_t. In other embodiments, There are also other division methods, such as using different structure data, different bit value sizes for area division, etc., and there are no specific restrictions here.

In a specific embodiment, using uint64_t to represent the initial encoding value, the lower 40 bits of the initial encoding value can be divided into offset areas to store the offset offset of the inverted chain data in the storage block. Since the current The size of a single-machine inverted index generally rarely exceeds 1TB. Therefore, this offset can be set to a size of 1TB. Of course, different sizes can also be set for different situations, and there is no limit here.

The highest 4 bits in the initial encoding value are divided into the index mode area, which is used to indicate the index mode. As shown above, currently there are only two index modes involved, namely the index mode for the first index block and the index mode for the second index block. , then the highest 4 bits can take values of 0x0001 and 0x0002, which represent two indexing methods respectively. For example, the former represents the binary indexing method of the standard library, and the latter represents the instruction set indexing method. The middle 20 bits are divided into data length areas for Represents the data length after the offset. For example, when the highest 4 bits are 0x0001, the middle 20 bits represent the number of int32_t (4 bytes) data after the offset. When the highest 4 bits are 0x0002, the middle 20 The value of the bit represents the number of segments of data operated by a single SIMD instruction. For example, the AVX2 instruction (an instruction set in SIMD) can operate 256 bits at a time, so the 20-bit value represents how many such 256 bits there are.

Step S1530: Overwrite the index mode information corresponding to each index fragment in the corresponding index mode area.

In this embodiment, the indexing mode of each index fragment is related to the index block in which it is located, and the indexing mode information corresponding to each index fragment is overlaid in the corresponding index mode area.

Step S1550: Overwrite the inverted chain length information of each index fragment into the corresponding data length area.

The data length area is used to represent the data length after the offset, which is the length of the corresponding inverted chain data in the storage block. Therefore, the inverted chain length information of each index fragment can be overwritten in the corresponding data length area.

Step S1570: Overwrite the starting position information of the inverted chain data of each index fragment in the storage block with the corresponding offset area to obtain a hash table.

The offset area is used to indicate the offset offset of the inverted chain data in the storage block, which corresponds to the starting position of the inverted chain data in the storage block. The inverted chain data of each index fragment will be stored in the storage block. The starting position information is covered in the corresponding offset area, thereby obtaining the coding value corresponding to each index fragment, thereby obtaining the hash table used for data indexing.

In this embodiment, by dividing three areas and filling the corresponding data in the three areas, a coded value that can be used for data indexing is obtained. The indexing method of the corresponding index fragment can be obtained through the index mode area in the coded value. The data length area and offset area can obtain the starting position of the corresponding inverted chain data in the storage block and the length of the inverted chain data, which can indicate the position of the inverted chain data in the storage block, and the encoded value can be obtained through the above method , which can be used to subsequently shard different indexes and index data in different indexing methods to improve indexing efficiency.

Figure 16 is a flow chart of a data indexing method according to another exemplary embodiment. As shown in Figure 16, in an exemplary embodiment, the method is implemented before step S210 in Figure 2, and may include steps S1610 to S1630. The details are as follows:

Step S1610: Index the inverted chain of each index fragment based on the binary index method and the instruction set index method respectively, and obtain the first index rate and the second index rate of each index fragment accordingly.

The instruction set indexing method is a binary indexing method based on SIMD acceleration. This embodiment proposes a method for determining the preset threshold. At the same time, according to the length of the inverted chain in the index block, it is first confirmed that the inverted chain data in the first index block is indexed in the binary index method, and the inverted chain data in the second index block is indexed in binary index mode. The chain data is indexed using the instruction set index method.

At this time, the inverted chain data of each index shard can be indexed respectively through the binary index method and the instruction set index method, and the first index rate of each index shard in the binary index method and the instruction set index can be obtained accordingly. Second index rate in mode.

Step S1630: Based on the inverted chain length of each index fragment, compare the numerical values between the first index rate and the second index rate corresponding to each index fragment in the preset length sequence, and determine the preset rate based on the obtained comparison result. Set threshold.

In this embodiment, the inverted chain length of each index fragment is compared with the numerical value between the first index rate and the second index rate corresponding to each index fragment in order from short to long, and the first first index is The length of the inverted chain corresponding to the index fragment whose rate is less than the second index rate is used as the preset threshold; or,

According to the inverted chain length of each index fragment, compare the numerical values between the first index rate and the second index rate corresponding to each index fragment in order from long to short, and compare the first first index rate The length of the inverted chain corresponding to the index fragment greater than the second index rate is used as the preset threshold.

After determining the preset threshold, the binary indexing method can be set in the obtained first index block as the indexing method of the inverted chain data in the first index block, and the instruction set indexing method can be set in the second index block as the second index. The indexing method of the inverted chain data in the block. In this way, for different index blocks, set an indexing method with a faster indexing rate.

In this embodiment, the inverted chain data is indexed through different indexing methods to obtain inverted chain length thresholds under two indexing methods. Each inverted chain length threshold is used as a preset threshold. The indexing rate of chain data in a certain indexing method is greater than that of another indexing method, and the indexing rate of inverted chain data that is not greater than the preset threshold in another indexing method is greater than that of a certain indexing method, so that the indexing rate can be passed through this preset threshold. Set thresholds to determine different index blocks and better indexing methods under different index blocks, so as to achieve fast indexing of the fragments to be indexed.

Figure 17 is a schematic structural diagram of a data indexing device according to an exemplary embodiment. As shown in Figure 17, in an exemplary embodiment, the data indexing device includes:

The index block acquisition module 1710 is configured to splice the inverted chain data whose length is not greater than the preset threshold into the first index block according to the inverted chain length of each index fragment, and the inverted chain length is greater than the preset threshold. The threshold inverted chain data is spliced into the second index block;

Storage module 1730, configured to store the first index block and the second index block in the storage block;

The hash table creation module 1750 is configured to create a hash table. The hash table includes multiple key values and coding values corresponding to each key value. The multiple key values correspond to different index shards, and the coding values include corresponding index shards. The indexing method of each index fragment is related to the index block where the inverted chain data of the corresponding index fragment is located;

The index module 1770 is configured to index the data of the fragment to be indexed in the storage block according to the key value of the fragment to be indexed and the corresponding indexing method.

In this embodiment, the above-mentioned data indexing device can efficiently perform inverted indexing of index fragments and improve the speed of multi-term indexing.

In one embodiment, the index block acquisition module includes:

An alignment unit configured to align the inverted chain data of each index fragment whose inverted chain length is greater than a preset threshold;

The second index block acquisition unit is configured to splice the aligned inverted chain data of each index fragment to obtain the second index block.

In one embodiment, the number of storage blocks is multiple, and the storage module includes:

A first storage unit configured to store data of the first index block in the first storage block;

The second storage unit is configured to store the data of the second index block in the second storage block in a preset byte alignment manner.

In one embodiment, the coded value of the hash table also includes the storage location of the inverted chain data corresponding to the index fragment in the first storage block or the second storage block; the index module includes:

The first index data acquisition unit is configured to confirm the first key value corresponding to the fragment to be indexed and the indexing method and storage location corresponding to the first key value based on the hash table;

The first indexing unit is configured to, if the first key value corresponds to the first indexing method, index the inverted chain data of the fragments to be indexed in the first storage block according to the first indexing method and the corresponding storage location;

The second indexing unit is configured to, if the first key value corresponds to the second indexing mode, index the inverted chain data of the fragments to be indexed in the second storage block according to the second indexing mode and the corresponding storage location.

In one embodiment, the storage module includes:

The third storage unit is configured to store the first index block and the second index block in the storage block in a preset byte alignment manner, wherein the length of the storage block is equal to or greater than the length of the first index block and the second index block. and the data of the first index block in the storage block is stored after the data of the second index block.

In one embodiment, the coded value of the hash table also includes the storage location of the inverted chain data corresponding to the index fragment in the storage block; the index module includes:

The second index data acquisition unit is configured to confirm the second key value corresponding to the fragment to be indexed and the indexing method and storage location corresponding to the second key value based on the hash table;

The third indexing unit is configured to index the inverted chain data of the fragments to be indexed in the storage block according to the third indexing method and the corresponding storage location if the second key value corresponds to the third indexing method. The third indexing method is for the third indexing method. The inverted chain data in an index block is indexed and set;

The fourth indexing unit is configured to index the inverted chain data of the fragments to be indexed in the storage block according to the fourth indexing method and the corresponding storage location if the second key value corresponds to the fourth indexing method. The fourth indexing method is for the fourth indexing method. The inverted chain data in the second index block is indexed and set.

In one embodiment, the hash table creation module includes:

The initial hash table creation unit is configured to preset an initial hash table. The initial hash table includes multiple initial key values and initial coding values corresponding to each initial key value;

The key value acquisition unit is configured to overwrite the initial key value with the hash value of each index fragment to obtain multiple key values;

The index mode allocation unit is configured to allocate an index mode to the corresponding index fragment according to the index block where each inverted chain data is located;

The coded value acquisition unit is configured to overwrite the position of the inverted chain data of each index fragment in the storage block and the corresponding index method with the corresponding initial coded value to obtain a hash table.

In one embodiment, the coded value acquisition unit includes:

The area division section is configured to divide each initial encoding value into areas to obtain the index mode area, data length area and offset area corresponding to each initial encoding value;

The index mode area coverage section is configured to cover the index mode information corresponding to each index shard in the corresponding index mode area;

The data length area coverage section is configured to cover the inverted chain length information of each index fragment in the corresponding data length area;

The offset area coverage block is configured to cover the starting position information of the inverted chain data of each index fragment in the storage block with the corresponding offset area to obtain a hash table.

In one embodiment, the indexing method includes a binary indexing method set for indexing the inverted chain data in the first index block, and an instruction set set for indexing the inverted chain data in the second index block. Indexing method; the data indexing device also includes:

The index rate acquisition module is configured to index the inverted chain of each index fragment based on the binary index method and the instruction set index method respectively, and accordingly obtain the first index rate and the second index rate of each index fragment;

The preset threshold acquisition module is configured to compare the numerical size between the first index rate and the second index rate corresponding to each index fragment in the preset length order according to the inverted chain length of each index fragment, and calculate the value according to the obtained Compare the results to determine the preset threshold.

It should be noted that the data indexing device provided by the above embodiments and the data indexing method provided by the above embodiments belong to the same concept, and the specific manner in which each module and unit performs operations has been described in detail in the method embodiments. No further details will be given.

Embodiments of the present application also provide an electronic device, including: one or more processors; a storage device configured to store one or more programs. When one or more programs are executed by one or more processors, The electronic device is caused to implement the data indexing method provided in the above embodiments.

FIG. 18 shows a schematic structural diagram of a computer system suitable for implementing an electronic device according to an embodiment of the present application.

It should be noted that the computer system 1800 of the electronic device shown in FIG. 18 is only an example, and should not impose any restrictions on the functions and scope of use of the embodiments of the present application.

As shown in Figure 18, the computer system 1800 includes a central processing unit (Central Processing Unit, CPU) 1801, which can be loaded into a random computer according to a program stored in a read-only memory (Read-Only Memory, ROM) 1802 or from a storage part 1808. Access the program in the memory (Random Access Memory, RAM) 1803 to perform various appropriate actions and processes, such as performing the methods in the above embodiments. In RAM 1803, various programs and data required for system operation are also stored. The CPU 1801, ROM 1802, and RAM 1803 are connected to each other through a bus 1804. An input/output (I/O) interface 1805 is also connected to bus 1804.

The following components are connected to the I/O interface 1805: an input part 1806 including a keyboard, a mouse, etc.; an output part 1807 including a cathode ray tube (CRT), a liquid crystal display (LCD), etc., and a speaker, etc. ; a storage section 1808 including a hard disk, etc.; and a communication section 1809 including a network interface card such as a LAN (Local Area Network) card, a modem, etc. The communication section 1809 performs communication processing via a network such as the Internet. Driver 1810 is also connected to I/O interface 1805 as needed. Removable media 1811, such as magnetic disks, optical disks, magneto-optical disks, semiconductor memories, etc., are installed on the drive 1810 as needed, so that a computer program read therefrom is installed into the storage portion 1808 as needed.

In particular, according to embodiments of the present application, the process described above with reference to the flowchart may be implemented as a computer software program. For example, embodiments of the present application include a computer program product including a computer program carried on a computer-readable medium, the computer program including a computer program for performing the method shown in the flowchart. In such embodiments, the computer program may be downloaded and installed from the network via communications portion 1809, and/or installed from removable media 1811. When the computer program is executed by the central processing unit (CPU) 1801, various functions defined in the system of the present application are executed.

It should be noted that the computer-readable medium shown in the embodiments of the present application may be a computer-readable signal medium or a computer-readable storage medium, or any combination of the above two. The computer-readable storage medium may be, for example, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, device or device, or any combination thereof. More specific examples of computer readable storage media may include, but are not limited to: an electrical connection having one or more wires, a portable computer disk, a hard drive, random access memory (RAM), read only memory (ROM), removable Erasable Programmable Read Only Memory (EPROM), flash memory, optical fiber, portable compact disk read-only memory (Compact Disc Read-Only Memory, CD-ROM), optical storage device, magnetic storage device, or any of the above suitable The combination. As used herein, a computer-readable storage medium may be any tangible medium that contains or stores a program for use by or in connection with an instruction execution system, apparatus, or device. In this application, a computer-readable signal medium may include a data signal propagated in baseband or as part of a carrier wave, in which a computer-readable computer program is carried. Such propagated data signals may take many forms, including but not limited to electromagnetic signals, optical signals, or any suitable combination of the above. A computer-readable signal medium may also be any computer-readable medium other than a computer-readable storage medium that can send, propagate, or transmit a program for use by or in connection with an instruction execution system, apparatus, or device . Computer programs embodied on computer-readable media may be transmitted using any suitable medium, including but not limited to: wireless, wired, etc., or any suitable combination of the above.

The flowcharts and block diagrams in the accompanying drawings illustrate the architecture, functionality, and operations of possible implementations of systems, methods, and computer program products according to various embodiments of the present application. Each block in the flow chart or block diagram may represent a module, program segment, or part of the code. The above-mentioned module, program segment, or part of the code includes one or more executable components for implementing the specified logical function. instruction. It should also be noted that, in some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown one after another may actually execute substantially in parallel, or they may sometimes execute in the reverse order, depending on the functionality involved. It will also be noted that each block in the block diagram or flowchart illustration, and combinations of blocks in the block diagram or flowchart illustration, can be implemented by special purpose hardware-based systems that perform the specified functions or operations, or may be implemented by special purpose hardware-based systems that perform the specified functions or operations. Achieved by a combination of specialized hardware and computer instructions.

The units involved in the embodiments of this application can be implemented in software or hardware, and the described units can also be provided in a processor. Among them, the names of these units do not constitute a limitation on the unit itself under certain circumstances.

Another aspect of the present application also provides a computer-readable storage medium on which a computer program is stored. When the computer program is executed by a processor, the above data indexing method is implemented. The computer-readable storage medium may be included in the electronic device described in the above embodiments, or may exist separately without being assembled into the electronic device.

Another aspect of the present application also provides a computer program product or computer program, which includes computer instructions stored in a computer-readable storage medium. The processor of the computer device reads the computer instructions from the computer-readable storage medium, and the processor executes the computer instructions, so that the computer device executes the data indexing method provided in the above embodiments.

The above content is only a preferred exemplary embodiment of the present application and is not intended to limit the implementation of the present application. Those of ordinary skill in the art can easily make corresponding modifications or modifications based on the main concept and spirit of the present application. Therefore, the protection scope of this application should be subject to the protection scope required by the claims.

Claims (13)

1. A data indexing method, characterized by including: According to the inverted chain length of each index fragment, the inverted chain data whose inverted chain length is not greater than the preset threshold is spliced into the first index block, and the inverted chain data whose inverted chain length is greater than the preset threshold is spliced into the first index block. Spliced into the second index block; store the first index block and the second index block in a storage block; Create a hash table. The hash table includes a plurality of key values and a coding value corresponding to each key value. The plurality of key values respectively correspond to different index fragments. The coding value includes an indexing method corresponding to the index fragment. , the indexing method of each index fragment is related to the index block where the inverted chain data of the corresponding index fragment is located; Data indexing of the fragment to be indexed is performed in the storage block according to the key value of the fragment to be indexed and the corresponding indexing method. 2. The method according to claim 1, characterized in that, according to the inverted chain length of each index fragment, inverted chain data whose inverted chain length is not greater than a preset threshold is spliced into the first index block, And splicing the inverted chain data whose inverted chain length is greater than the preset threshold into a second index block, including: Align the inverted chain data of each index fragment whose inverted chain length is greater than the preset threshold; The aligned inverted chain data of each index fragment is spliced to obtain the second index block. 3. The method of claim 1, wherein the number of storage blocks is multiple, and storing the first index block and the second index block in the storage block includes: Store the data of the first index block in the first storage block; The data of the second index block is stored in the second storage block in a preset byte alignment manner. 4. The method according to claim 3, characterized in that the encoded value of the hash table further includes the inverted chain data corresponding to the index fragment in the first storage block or the second storage block. Storage location; the data indexing of the fragment to be indexed in the storage block based on the key value of the fragment to be indexed and the corresponding indexing method includes: Confirm the first key value corresponding to the fragment to be indexed and the indexing method and storage location corresponding to the first key value based on the hash table; If the first key value corresponds to the first indexing method, index the inverted chain data of the fragment to be indexed in the first storage block according to the first indexing method and the corresponding storage location; If the first key value corresponds to the second indexing method, the inverted chain data of the fragment to be indexed is indexed in the second storage block according to the second indexing method and the corresponding storage location. 5. The method of claim 1, wherein storing the first index block and the second index block in a storage block includes: The first index block and the second index block are stored in the storage block in a preset byte alignment manner, wherein the length of the storage block is equal to or greater than the length of the first index block and the The length sum between the second index blocks, and the data of the first index block in the storage block is stored after the data of the second index block. 6. The method according to claim 5, characterized in that the coded value of the hash table further includes the storage location of the inverted chain data corresponding to the index fragment in the storage block; The key value of the slice and the corresponding indexing method are used to index the data of the slice to be indexed in the storage block, including: Confirm the second key value corresponding to the fragment to be indexed and the indexing method and storage location corresponding to the second key value based on the hash table; If the second key value corresponds to the third indexing method, the inverted chain data of the fragment to be indexed is indexed in the storage block according to the third indexing method and the corresponding storage location, and the third indexing method Set for indexing the inverted chain data in the first index block; If the second key value corresponds to the fourth indexing method, the inverted chain data of the fragment to be indexed is indexed in the storage block according to the fourth indexing method and the corresponding storage location, and the fourth indexing method Set for indexing the inverted chain data in the second index block. 7. The method according to claim 1, characterized in that said establishing a hash table includes: Preset an initial hash table, which includes a plurality of initial key values and an initial code value corresponding to each initial key value; Cover the initial key value with the hash value of each index shard respectively to obtain multiple key values; Allocate an index method to the corresponding index shard according to the index block where each inverted chain data is located; The position of the inverted chain data of each index fragment in the storage block and the corresponding index mode are overwritten with the corresponding initial encoding value to obtain the hash table. 8. The method according to claim 7, characterized in that the position of the inverted chain data of each index fragment in the storage block and the corresponding index mode are overwritten with the corresponding initial encoding value to obtain the The above hash table includes: Divide each initial coding value into regions to obtain the index mode area, data length area and offset area corresponding to each initial coding value; Cover the index mode information corresponding to each index fragment in the corresponding index mode area; Cover the inverted chain length information of each index fragment in the corresponding data length area; The starting position information of the inverted chain data of each index fragment in the storage block is overwritten in the corresponding offset area to obtain the hash table. 9. The method of claim 1, wherein the indexing method includes a binary indexing method set for indexing the inverted chain data in the first index block, and a binary indexing method for the second index. The instruction set indexing method set by indexing the inverted chain data in the block; according to the inverted chain length of each index fragment, the inverted chain data whose length is not greater than the preset threshold is spliced into the first An index block, and before splicing the inverted chain data whose inverted chain length is greater than the preset threshold into a second index block, the method further includes: Index the inverted chain of each index fragment based on the binary indexing method and the instruction set indexing method respectively, and accordingly obtain the first index rate and the second index rate of each index fragment; According to the inverted chain length of each index fragment, compare the numerical values between the first index rate and the second index rate corresponding to each index fragment in the preset length sequence, and determine the preset value based on the obtained comparison result. threshold. 10. A data indexing device, characterized by comprising: The index block acquisition module is configured to splice the inverted chain data whose length is not greater than a preset threshold into the first index block according to the inverted chain length of each index fragment, and to splice the inverted chain data whose length is greater than the preset threshold into the first index block. Set the threshold inverted chain data to be spliced into the second index block; A storage module configured to store the first index block and the second index block in a storage block; A hash table creation module configured to create a hash table. The hash table includes a plurality of key values and a coding value corresponding to each key value. The plurality of key values respectively correspond to different index fragments. The coding value Including the indexing method of the corresponding index shard, the indexing method of each index shard is related to the index block where the inverted chain data of the corresponding index shard is located; An index module is configured to perform data indexing on the fragment to be indexed in the storage block according to the key value of the fragment to be indexed and the corresponding indexing method. 11. An electronic device, characterized in that it includes: one or more processors; Storage device, used to store one or more computer programs, when the one or more computer programs are executed by the one or more processors, so that the electronic device implements any one of claims 1-9 method described in the item. 12. A computer-readable storage medium, characterized in that computer-readable instructions are stored thereon. When the computer-readable instructions are executed by a processor of a computer, the computer is caused to execute any one of claims 1-9. method described in the item. 13. A computer program product, comprising a computer program, characterized in that, when executed by a processor, the computer program implements the method according to any one of claims 1 to 9.