Approximate membership query secondary index for immutable storage environment

Key-value storage system is widely used in various Web applications because of its excellent write performance. Current key-value storage systems mainly use Bloom filter to optimize non-primary key query performance, but has shortcomings such as query efficiency is affected by the number of data segments and the possibility of accessing redundant data segments caused by misjudgment. In order to optimize the query ability of key-value system analysis processing, a new secondary index was proposed for the data access characteristics of one writes and multiple reads. By building a global index, the increase in query latency caused by multiple filter probes is avoided. In addition, the pre-probe recursive expulsion strategy was proposed to optimize the efficiency of index construction. Compared with traditional methods, this secondary index can return exactly correct sequence of data segment numbers when processing existing data item queries. Furthermore, this secondary index uses a range query scheme based on logical chain to realize range query. Experimental results show that the index structure is effective. Compared to the baseline structure, this secondary index improves query performance by about 10 to 50 times.