CN108021678B - Key value pair storage structure with compact structure and quick key value pair searching method - Google Patents

Abstract

The invention relates to a compact key-value pair storage structure and a fast key-value pair search method, belonging to the technical field of real-time big data processing and key-value query. Based on the combined structure of hierarchical hash table and Bloom filter, the first layer uses a 2-left hashing hash structure for storage, and each layer of hash table is used as an auxiliary table to save the conflicting data in the upper table, and Combined with Bloom filter to save conflicting data, use "Bloom filter to determine whether the searched key exists in the current set of results" as an index to improve search speed, thereby improving storage space utilization, making the structure compact and fast Find the software platform requirements. The invention can effectively solve the problems of current large-scale key-value pair storage and search time uncertainty, unsteady search speed, slow software implementation and running speed that cannot meet application requirements and the like.

Description

A compact key-value pair storage structure and a fast key-value pair search method

technical field

The invention relates to a compact key-value pair storage structure and a fast key-value (key-value) pair search method, in particular to a multi-level hash table (hash table) and a bloom filter (bloom filter, BF) ) key-value pair storage and search method, belonging to the technical field of real-time big data processing and key-value query.

Background technique

With the increasing scale of the Internet and the growing network traffic, the requirements for large data storage and search rates in the field of computer technology are getting higher and higher. The key-value search problem is widely used in various directions of the computer field, such as big data processing and high-speed networks.

However, the performance of the key-value pair lookup method is severely limited by hardware resources. Therefore, under the trend of network function virtualization, it is more important to adapt to the software platform and more suitable for the development of the Internet. In a software platform, multiple tasks are processed at the same time, and the storage and search methods cannot occupy an entire cache by themselves. Therefore, this method should carefully control the size of the structures placed in the cache and avoid frequent replacement. However, most of the existing methods are more suitable for hardware platforms, and are not high enough in terms of search speed and cache usage efficiency.

The existing key-value pair search methods are mainly divided into hash table search, tree search, and search method based on Bloom filter. The hash table method is a more traditional method, which can perform key-value pair insertion, deletion, and search with a certain time complexity of O(1). It is done in O(1) complexity every time. Therefore, the basic data structure design of the method simply using the hash table cannot meet the current requirements for the search speed of key-value pairs, and reducing hash collisions requires larger storage space, resulting in low space utilization.

Methods based on Bloom filter data structure mainly rely on the simple and compact properties of Bloom filter structure. The main methods include the method of combining multiple Bloom filters, the method of combining Bloom filters with data encoding, and the data structure based on the deformation of Bloom filters. These structures changed the structure of the original Bloom filter and improved a certain space utilization rate, but destroyed the original simple and compact characteristics of the Bloom filter, so they did not play the due effect of the Bloom filter. .

The invention relates to a key-value pair search method with compact and fast characteristics, provides a key-value pair storage structure with a compact structure, improves the space utilization rate of the traditional hash table method, and completes the key-value pair by determining the time complexity. Value pair search, the proposed compact key-value pair storage structure and fast key-value pair search method mainly involve the following two problems:

(1) Based on the multi-layer hash table design, the 2-left hashing hash structure is used as the first layer of the multi-level hash table to ensure the compactness of the structure and the high utilization of space, while reducing hash collisions;

(2) The conflict data in the corresponding layer hash table is stored through the multi-layer Bloom filter, and the result of whether the search key exists in the current layer conflict data set is provided as the search index, which improves the search speed and reduces the number of memory accesses.

SUMMARY OF THE INVENTION

The purpose of the present invention is to overcome the defect that the key-value pair storage structure of the existing method is not compact enough, and to solve the problems of the current large-scale key-value pair storage and search time uncertainty, the software implementation running speed is too slow to meet the application requirements, etc. , to meet the requirement of reasonable use of cache for less data replacement, a compact key-value pair storage structure and a fast key-value pair search method are proposed.

The idea of the present invention is based on the combination of hierarchical hash table and Bloom filter. The first layer uses a 2-left hashing hash structure for storage, and each layer of hash table is stored as an auxiliary table in the upper table for storage. Conflicting data, combined with Bloom filter to save conflicting data, using "Bloom filter to determine whether the searched key exists in the current set of results" as an index to improve the search speed, thereby improving storage space utilization. Software platform requirements for compact structure and fast lookup. A compact key-value pair storage structure and a fast key-value pair search method, including a compact key-value pair storage structure and a fast key-value pair search method;

Among them, a compact key-value pair storage structure, referred to as the storage structure, includes a λ-layer hash table. Starting from the second-layer hash table, the total number of storage blocks contained in each layer of the hash table decreases in a proportional sequence. Wherein, the preferred proportionality factor is 10;

Among them, the first-layer hash table, that is, the first-layer hash table, uses a 2-left hashing hash table, which has two sub-tables on the left and right, and each sub-table contains the same number of storage blocks; for the remaining layers Hash table, there is no concept of sub-table;

Wherein, each storage block includes N storage units, and the size of each storage unit is M bits;

Wherein, the range of M*N is smaller than the size of the computer cache line using the storage structure, the preferred N is 8, and the preferred M is 32 or 64 bits;

The first storage unit in each storage block stores the number of occupied storage units in the storage block, and the remaining storage units store key-value pairs;

Among them, the key-value pair includes a key and a value; the "value" of the key and the "check value" of the key are stored in the specific storage; the "value" part of the storage can store the value itself or point to the storage location of the value itself. Pointer, hereinafter collectively referred to as value; the calculation of the "check value" of the key can use a commonly used check algorithm, such as crc cyclic redundancy check or md5 check algorithm;

Except for the last layer of hash table, each layer of hash table corresponds to a Bloom filter. Starting from the first layer of Bloom filter, the size of the space occupied by each layer of Bloom filter decreases in a proportional sequence. , wherein, the preferred scaling factor is 10;

A fast key-value pair search method, including a key-value pair data storage process and a key-value pair search process;

Among them, the key-value pair data storage process is the key-value pair insertion process, referred to as the insertion process; the key-value pair search process is referred to as the search process;

The specific steps of the insertion process are as follows:

Step 1, set the number of hash table layers and the number of storage blocks included in each layer of the hash table, and set the size of the Bloom filter corresponding to each layer of the hash table;

Step 2, set the number N of the storage units included in each storage block of the hash table, set the size of each storage unit to be M bits;

The preferred solution of step 2 is to ensure that the size of the memory block M*N bits is equal to or smaller than the size of the computer cache line, so that the entire memory block is transferred into the cache when accessing the memory block, and multiple times when accessing different units of the memory block is avoided. Cache replacement for faster lookup times;

Step 3, insert data into the first-layer hash table, namely 2-left hashing, if there is no conflict, the key-value pair is inserted successfully, and skip to step 5; if there is a conflict, mark the data in the first layer corresponding to in the bloom filter, and execute step 4;

Among them, the inserted data is the "value" part of the key-value pair, and the "check value" of the key is also stored;

The specific process of step 3 is: perform two hash operations on the keys in the key-value pair, and use the two hash calculation results to determine a storage block respectively in the left and right sub-tables of 2-left hashing;

Among them, the hash operation of each layer of hash table is fixed, and here the two hash operations of the first layer are also fixed;

When the following two situations occur, indicating that the inserted data conflicts, you need to skip to step 4:

3.1A The storage units in the two storage blocks are all occupied, that is, the number of storage units in the two storage blocks is the same, both N-1, which is equal to the maximum number of key-value pairs that can be stored in the block, indicating that an insertion has occurred. Conflict, go to step 4;

3.1B If the check value stored in all the storage units in the two storage blocks exists in the same storage unit as the "check value" to be inserted into the data or the key-value pair to be inserted, it indicates that an insertion conflict has occurred, and the process proceeds to step 4;

When the two inserted data conflict situations of 3.1A and 3.1B are not satisfied, that is, when the inserted data does not conflict, there are the following two situations:

3.2A The number of occupied cells in the two storage blocks is different, and the inserted data, that is, the value of the key and the check value of the key, are saved to the first free storage block with fewer occupied cells. In the storage unit, skip to step 6;

3.2B The number of occupied cells in the two storage blocks is the same, then the data will be inserted, that is, the value corresponding to the key and the check value of the key will be saved to the first free storage cell of the left storage block. to step 6;

Step 4, determine whether the current layer is the last layer, and according to the judgment result, if it is the last layer, then jump to step 7, if the current layer is not the last layer in the hash table structure, it should be distributed to the corresponding layer of the current layer. Add the current key to the Rum filter set, skip to step 5;

Step 5: Jump into the next layer of the hash table, perform a hash operation, use the result of the hash operation to determine the location of a storage block, and perform the following operations by judging whether the storage block and the current key conflict: when an insertion occurs When the data conflicts, you need to skip to step 4: when the inserted data does not conflict, insert the data, that is, save the value of the key and the check value of the key to the first free storage unit of the storage block, and enter the step 6;

Among them, there are two situations in which the inserted data conflicts and you need to skip to step 4 as follows:

5.1A If the storage units in the storage block are full, that is, the number of storage units in the storage block is N-1, which is equal to the maximum number of key-value pairs that can be stored in the block, it indicates that an insertion conflict occurs, and you need to skip to step 4;

5.1B If the check value stored in all storage units in the storage block exists in the same storage unit as the "check value" of the data to be inserted or the key-value pair to be inserted, it indicates that an insertion conflict occurs, and it is necessary to skip to step 4;

Step 6, the data insertion is successful, that is, the key-value pair insertion function is successfully called, the function returns 1, and the insertion process ends;

Step 7, the data insertion fails, that is, the key-value pair insertion function fails to be called, the function returns 0, and the insertion process ends;

So far, from step 1 to step 6 or step 7, the insertion process is completed;

The second part of the key-value pair search process, that is, for a given key in the key-value pair, the process of finding the value in the corresponding key-value pair, referred to as the search process, the specific steps are as follows:

Step 8, search for the key in the given key-value pair in the first-layer Bloom filter set, by judging whether the key is saved in the set, decide to skip to step 10 or step 9, specifically:

8.1 If the key does not exist in the first-level Bloom filter set, go to step 9;

8.2 If the key exists in the first-level Bloom filter set, go to step 10;

Step 9, perform two hash calculations in 2-left hashing, and determine a storage block in the left and right sub-tables as a result; Calculated check value "comparison, check whether there is an equal situation, and perform the following operations according to the judgment result:

9.1 If there is an equal situation, it means that the value stored in the unit is the value corresponding to the searched key, and skip to step 13;

9.2 If there is no equality, the value corresponding to the key does not exist in this storage structure, and skip to step 14;

Step 10, enter the next layer of Bloom filter, search for the given key in the next layer of Bloom filter set, and perform the following operations by judging whether the key is in the Bloom filter set:

10.1 If the key exists in the Bloom filter set, by judging whether the layer where the current Bloom filter is located is the last layer, it is decided to skip to step 11 or step 10, specifically:

10.1A If the current Bloom filter layer is not the last layer, skip to step 10;

10.1B If the current Bloom filter layer is the last layer, skip to step 11;

10.2 If the key does not exist in the Bloom filter set of this layer, enter the hash table of the corresponding layer of the current Bloom filter, and skip to step 12;

Step 11, enter the last layer of hash table;

Step 12: Find the check value corresponding to the key in the hash table of the current layer, perform a hash operation on the key, determine a storage block in the hash table through the result of the hash operation, and traverse each non-volatile storage block in the storage block. Check whether the check value of the empty cell is equal to the check value of the current key. According to whether there is an equality, it is judged whether to jump to step 13 or step 14, specifically:

12.1 If there is an equal situation, that is, an equal check value is found, then go to step 13;

12.2 If there is no equal condition, that is, no equal check value is found, then go to step 14;

Step 13, the search function is called successfully, the function returns the value saved in the current storage unit, and ends the search;

Step 14, the search function fails to call, the function returns 0, and the search ends;

So far, from step 1 to step 13 or step 14, a quick key-value pair search method is completed.

beneficial effect

Compared with the existing method, the present invention has a compact key-value pair storage structure and a fast key-value pair search method, and has the following beneficial effects:

1. The method of the present invention ensures the compactness of data storage by taking the 2-left hashing hash table as the first layer of the hierarchical hash table, and by using the Bloom filter to store conflicting data, the Bloom filter is effectively reduced. Occupied space, that is, effectively solve the problem of low utilization of storage space;

2. Compared with the problems of slow search speed and incompatibility with the software platform of the existing method, the method can adapt to the cache size of the software platform, improve the search speed, and ensure real-time performance.

Description of drawings

1 is a schematic flowchart of a method (insertion process) for fast searching of key-value pairs with a compact structure according to an embodiment of the present invention;

FIG. 2 is a schematic flowchart of a fast search method (search process) for a key-value pair with a compact structure according to an embodiment of the present invention;

3 is a schematic diagram of a compact key-value pair storage structure in the present invention;

4 is a schematic diagram of using 2-left hashing in the insertion process in Embodiment 1 of the fast key-value pair search method;

5 is a schematic diagram of using 2-left hashing in the insertion process in Embodiment 2 of the quick key-value pair search method;

FIG. 6 is a schematic diagram of a search process used in Embodiment 2 of the quick key-value pair search method.

Detailed ways

In order to make the objectives, technical solutions and advantages of the present invention clearer, the specific embodiments of the present invention will be described in detail below with reference to the accompanying drawings. This embodiment is implemented on the premise of the technical solution of the present invention, and provides a detailed implementation manner and a specific operation process, but the protection scope of the present invention is not limited to the following embodiments.

The present invention is a compact key-value pair storage structure and a fast key-value pair search method based on a layered hash table and a Bloom filter. The specific steps are divided into two parts. Figure 1 shows the first part, the key The value pair insertion process, Figure 2 shows the second part, the key-value pair search process.

Example 1

The specific steps of the first part of the key-value pair insertion process include:

Step 1, set the number of hash table layers and the number of storage blocks included in each layer of the hash table, and set the size of the Bloom filter corresponding to each layer of the hash table;

In this embodiment, as shown in Figure 3, the number of layers of the hash structure is set to 4, the first layer of hash table 2-left hashing includes 204,800 storage blocks, the second layer of hash table includes 500 storage blocks, and the third layer of hash table includes 500 storage blocks. The secondary hash table includes 50 storage blocks. The fourth-level hash table includes 5 storage blocks;

Set the Bloom filter size of the first layer to 5000 bytes, and the lower layer to decrease to 500 bytes and 50 bytes in turn;

Step 2, set the number N of the storage units included in each storage block of the hash table, set the size of each storage unit to be M bits;

In the embodiment, set N to be 8 and M to be 32 bits; the size of each storage block is 8*32=256 bits; each storage unit includes a "value" part and a "check value" part, and the value part occupies 16 bits. , the check value part occupies 16 bits;

The first layer is a 2-left hashing data structure, which consists of two sub-tables, as shown in Figure 4; each sub-table consists of the same number of storage blocks, in this embodiment, each sub-table contains 102,400 storage blocks ;

Step 3, insert data into the first-layer hash table, and execute the operation according to whether there is a conflict;

In this embodiment, as shown in FIG. 4 , two hash operations Hash1(key1) and Hash2(key1) are performed on key1 in the key-value pair (key1, value1), where Hash1 is the hash used by the left sub-table function, Hash2 is the hash function used by the right sub-table, the results of the two hash operations correspond to two storage blocks in the left and right sub-tables in 2-left hashing respectively;

Check the first unit of the two storage blocks. In the figure, the two storage blocks have been occupied by 2 and 4 units respectively, and there is no check value conflict, then save the check values of value1 and key1 to the left In the first free unit of the storage block of the sub-table, the counter of the first unit is incremented by 1, the storage step is completed, and the step 4 is entered;

Step 4, the insertion is successful, the function returns 1, and the adding step is ended;

The second part of the key-value pair search process, the specific steps are as follows:

Step 5: Search for the given key in the first-level Bloom filter set, and perform the following operations by judging whether the key is saved in the set:

In this embodiment, if the key does not exist in the first-layer Bloom filter set, perform step 6;

Step 6, through the key key1, search the value corresponding to the key in the first layer 2-left hashing structure, and judge the execution steps according to the search result;

In the present embodiment, first perform Hash11 (key1) and Hash12 (key1) operations on key1, and find a storage block respectively in the two sub-tables of 2-lefthashing;

Calculate the check code of key1, and compare it with all the check values in the two storage blocks. At this time, the same check value is found in the left storage block, indicating that the search is successful, and then go to step 7;

Step 7, return the found value1, and end the search;

Example 2

The first part of the key-value pair insertion process, in conjunction with Figures 3 and 5, the specific steps are as follows:

Step 1, set the number of hash table layers and the number of storage blocks included in each layer of the hash table, and set the size of the Bloom filter corresponding to each layer of the hash table;

In this embodiment, the settings are the same as those in Embodiment 1;

Step 2, set the number N of the storage units included in each storage block of the hash table, set the size of each storage unit to be M bits;

In this embodiment, the settings are the same as those in Embodiment 1;

Step 3, insert data into the first-layer hash table, and execute the operation according to whether there is a conflict;

In this embodiment, two hash operations Hash1 (key2) and Hash2 (key2) are performed on key2 in the key-value pair (key2, value2), and the two positions corresponding to the values are shown in Figure 5, both of which are occupied. 7 units are full, so there is an insertion conflict, the dotted line 1 in Figure 3 represents an insertion conflict, and enter step 4;

Step 4, judge whether the current layer is the last layer, and operate according to the judgment result;

The current layer is not the last layer in the hash table structure, and the current key should be added to the Bloom filter set corresponding to the current layer, as shown by the solid line 2 in Figure 3, and then skip to step 5;

Step 5, jump into the next layer of hash table, perform a hash operation, use the result of the hash operation to determine the location of a storage block, and perform the following operations by judging whether the storage block and the current key conflict:

In this embodiment, enter the second-layer hash table;

In the second-layer hash table, a hash operation is performed, and the operation result determines a storage block position. In this embodiment, a hash operation is performed on key2 to determine a storage block;

In the current storage block, 3 data have been stored, but it is not full. Then check whether the check value of key2 is the same as the check value of the data stored in the current storage block. The same check code is found here, so key2 is in the second layer. A conflict also occurs in the hash table, and the dotted line 3 in Figure 3 indicates that a conflict occurs in the second layer;

At this point, repeat step 4, and add key2 to the second layer of Bloom filter, as shown in solid line 4 in Figure 3;

Enter the third-layer hash table, insert key2 into the third-layer hash table; perform a hash operation on key2 to map key2 to a certain storage block in the third-layer hash table;

In the current storage block, the storage is not full. At the same time, verify that the check value of key2 is the only one in the storage block. Store the check codes of key2 and key2 in the first empty unit, as shown in solid line 5 in Figure 3, enter step 6;

Step 6, the insertion is successful, the function returns 1, and the adding step is ended;

The second part of the key-value pair search process, in conjunction with Figure 6, the specific steps are as follows:

Step 7, look up key2 in the first-layer Bloom filter set, and execute the operation according to whether it is found;

In this embodiment, it is judged whether key2 exists in the first-layer Bloom filter, and the result is yes, as shown by the solid line 1 in Figure 6, then go to step 8;

Step 8, enter the next layer of Bloom filter, in the next layer of Bloom filter set, the given key is searched, by judging whether the key is in this Bloom filter set, carry out the following operations;

In this embodiment, key2 exists in the second-layer Bloom filter set, and is not the last layer, as shown by the solid line 2 in Figure 6, so repeat step 8, that is, enter the third-layer Bloom filter , find out whether key2 is in the set;

As shown by the dotted line 3 in Figure 6, key2 does not exist in the third-layer Bloom filter set, enter step 9;

Step 9, enter the hash table of the corresponding layer of the current Bloom filter, and execute step 10;

In this embodiment, enter the third-layer hash table;

Step 10, look up the value corresponding to the key in the current hash table, and judge the execution step according to the search result;

In this embodiment, in the third-layer hash table, a hash operation is performed, a storage block is determined according to the operation result, and the storage block is searched to find out whether there is a check value that is the same as the check value of key2;

The same check value is found in this embodiment, and the value stored in the storage unit is value2 or a pointer to value2;

Step 11, return value2, and the search ends.

in conclusion

The invention is mainly composed of a compact key-value pair storage structure and a key-value pair quick search method. The quick search method is divided into an adding process and a search process. By using a multi-layer hash table to store data, especially using a 2-left hashing hash table as the first layer to store key-value pairs in a multi-layer hash table, the compactness of the key-value pair storage structure is guaranteed. By using the Bloom filter to record the conflicting data in the corresponding hash table, the number of memory accesses is reduced and the utilization of the cache is improved. The time overhead of key-value pair search is relatively constant, because more than 95% of the data will be stored in 2-left hashing, and the key-value pair search in 2-left hashing requires an average of 1.5 memory accesses, which achieves a constant search speed. Purpose. By using a Bloom filter structure that is small enough to be stored in the cache, its lookup does not generate memory access times, so the lookup is extremely fast, and the purpose of speeding up the key-value pair lookup in software implementation is achieved.

Since then, the storage and fast search method of key-value pairs based on the first layer 2-left hashing and using Bloom filter to record hash conflict items has been completed.

Although the embodiments of the present invention are described in conjunction with the accompanying drawings, for those skilled in the art, some improvements can be made without departing from the principles of the present invention, which should also be regarded as belonging to the protection scope of the present invention. .

Claims (4)

1. A fast key value pair searching method comprises a storage structure based on combination of a layered hash table and a bloom filter, wherein the storage structure is stored by using a 2-left hashing structure through a first layer, each layer of hash table is used as an auxiliary table to store data with storage conflict in an upper layer table, each layer of hash table is combined with the bloom filter to store the conflict data, and the bloom filter is used for judging whether a searched key has a result in a current set or not as an index to improve the searching speed, so that the storage space utilization rate is improved, the structure is compact, and the fast searching software platform is realized, and the fast key value pair searching method is characterized in that: the storage structure comprises lambda-layer hash tables, and the total storage block number contained in each layer of hash table is decreased in an equal ratio sequence from the second layer of hash table, wherein the equal ratio factor is 10;

the first-layer hash table comprises a left sub-table and a right sub-table, and each sub-table comprises the same number of storage blocks; for the rest of the layers of hash tables, the concept of sub-tables does not exist;

the first storage unit in each storage block stores the number of occupied storage units in the storage block, and the key value pairs are stored in the other storage units;

wherein a key-value pair comprises a key and a value; stored in the specific storage are the "value" of the key and the "check value" of the key; wherein the stored "value" portion may store the value itself or a pointer to a storage location of the value itself, hereinafter collectively referred to as the value; the "check value" of the key may be calculated using commonly used checking algorithms, including the crc cyclic redundancy check or md5 checking algorithm;

except the last layer of hash table, each layer of hash table corresponds to one bloom filter, and the space occupied by each layer of bloom filter decreases in an equal ratio sequence from the first layer of bloom filter, wherein the equal ratio factor is 10;

the key-value pair data storage process and the key-value pair searching process comprise the following steps:

the first part of key-value pair data storage process, namely key-value pair insertion process, which is called insertion process for short, comprises the following specific steps:

step 1, setting the number of layers of hash tables, the number of storage blocks contained in each layer of hash table, and the size of a bloom filter corresponding to each layer of hash table;

step 2, setting the number N of storage units contained in each storage block of the hash table, and setting the size of each storage unit as M bits;

step 3, inserting data into a first layer hash table, wherein the first layer hash table uses a 2-left hashing hash table, if the data does not conflict, the key value pair is successfully inserted, and the step 5 is skipped; if so, marking the data in the bloom filter corresponding to the first layer, and executing the step 4;

step 4, judging whether the current layer is the last layer, jumping to step 7 if the current layer is the last layer according to the judgment result, and if the current layer is not the last layer in the hash table structure, adding a current key to a bloom filter set corresponding to the current layer and jumping to step 5;

step 5, jumping into the next layer of hash table, performing a hash operation, determining a storage block position by using the hash operation result, and performing the following operations by judging whether the storage block and the current key have conflict or not: when the conflict of the inserted data occurs, jumping to the step 4; when the inserted data is not conflicted, storing the inserted data, namely the value of the key and the check value of the key into the first free storage unit of the storage block, and entering the step 6;

step 6, the data insertion is successful, namely the key value is successfully called for the insertion function, the function returns to 1, and the insertion process is ended;

step 7, the data insertion fails, namely the key value fails to call the insertion function, the function returns to 0, and the insertion process is ended;

to this end, from step 1 to step 6 or step 7, the insertion process is completed;

the second partial key value pair searching process, that is, the process of searching for the value in the corresponding key value pair for the key in the given key value pair, is referred to as the searching process for short, and includes the following specific steps:

step 8, searching the key in the given key value pair in the first layer bloom filter set, and determining whether to jump to step 10 or step 9 by judging whether the key is stored in the set, specifically:

8.1 if the key does not exist in the first layer bloom filter set, execute step 9;

8.2 if the key is present in the first layer bloom filter set, performing step 10;

step 9, performing hash calculation twice in 2-left shifting, and determining a storage block in the left and right sub-tables respectively according to the result; comparing the check value in each non-empty unit in the two storage blocks with the check value calculated according to the current key, checking whether the check values are equal, and deciding to jump to step 13 or step 14, wherein the specific steps are as follows:

9.1 if there is equal condition, it represents that the value stored in the unit is the value corresponding to the searched key, and jumps to step 13;

9.2 if the key is not equal, the value corresponding to the key does not exist in the storage structure, and the step 14 is skipped;

step 10, entering a next layer bloom filter, searching a given key in a next layer bloom filter set, and performing the following operations by judging whether the key is in the bloom filter set:

10.1 if the key exists in the bloom filter set, determining to jump to step 11 or step 10 by judging whether the layer where the current bloom filter is located is the last layer, specifically:

10.1A, if the layer where the current bloom filter is located is not the last layer, jumping to the step 10;

10.1B, if the layer where the current bloom filter is located is the last layer, jumping to the step 11;

10.2 if the key does not exist in the layer bloom filter set, entering a hash table of a layer corresponding to the current bloom filter, and jumping to the step 12;

step 11, entering the last layer of hash table;

step 12, searching a check value corresponding to the key in the hash table of the current layer, performing a hash operation on the key, determining a storage block in the hash table according to a hash operation result, traversing the check value of each non-empty unit in the storage block and comparing whether the check value is equal to the check value of the current key, and judging whether to jump to step 13 or step 14 according to whether the check values are equal, specifically:

12.1, if the condition of equality exists, namely an equal check value is found, entering a step 13;

12.2 if there is no equality condition, i.e. no equal check value is found, go to step 14;

step 13, the function is searched for and called successfully, the function returns to the value stored in the current storage unit, and the search is finished;

step 14, searching function call failure, returning the function to 0 and finishing searching;

to this end, from step 8 to step 13 or step 14, a fast key-value pair lookup method is completed.

2. The fast key-value pair lookup method according to claim 1, wherein: the scheme of the step 2 is to ensure that the size M x N bits of the memory block is equal to or smaller than the size of a computer cache line, so that the whole memory block is transferred into a cache when the memory block is accessed, multiple cache replacement is avoided when different units of the memory block are accessed, and the search time is shortened.

3. The fast key-value pair lookup method according to claim 1, wherein: in step 3, the inserted data is the 'value' part of the key value pair, and the 'check value' of the key is also stored; the specific process of the step 3 is as follows: performing two times of hash operation on the keys in the key value pair, and respectively determining a storage block in a 2-left shifting left sub-table and a 2-left shifting right sub-table by using two hash calculation results;

the hash operation of each layer of hash table is fixed, and the two hash operations of the first layer are also fixed;

when the following two situations occur, which indicate that the inserted data conflicts, it is necessary to jump to step 4:

3.1A, if the storage units in the two storage blocks are all occupied, namely the number of the storage units in the two storage blocks is the same, both the storage units are N-1 and equal to the maximum key value pair number which can be stored in the block, indicating that an insertion conflict occurs, and entering the step 4;

3.1B, if the check values stored in all the storage units in the two storage blocks have the same storage unit as the check value of the data to be inserted or the key value pair to be inserted, indicating that an insertion conflict occurs, and entering the step 4;

when two cases of collision of insertion data that do not satisfy 3.1A and 3.1B, i.e., when the insertion data do not collide, there are two cases as follows:

3.2A, if the occupied numbers of the units in the two storage blocks are different, storing the inserted data, namely the value of the key and the check value of the key, into the first idle storage unit of the storage block with the smaller number of occupied units, and jumping to the step 6;

3.2B, if the occupied numbers of the units in the two storage blocks are the same, storing the inserted data, namely the value corresponding to the key and the check value of the key, into the first free storage unit of the left storage block, and jumping to the step 6.

4. The fast key-value pair lookup method according to claim 1, wherein: in step 5, inserting data collision, and two situations that need to jump to step 4 are as follows:

5.1A, if the storage units in the storage block are full, namely the number of the storage units in the storage block is N-1 and is equal to the maximum key value pair number which can be stored in the block, indicating that an insertion conflict occurs;

and if the check values stored in all the storage units in the 5.1B storage block have the same storage units as the 'check values' of the data to be inserted or the key value pairs to be inserted, indicating that insertion conflict occurs.

Images