Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

Key-Value storage system-oriented indexed searching method and system

A storage system and query method technology, which is applied in the field of index query oriented to the Key-Value storage system, to achieve the effects of reducing read and write latency, reducing search, and improving data query speed and performance.

Active Publication Date: 2017-05-31
ANHUI UNIVERSITY
View PDF4 Cites 11 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0003] Key-value databases generally use a tree structure to organize data. With the advent of the era of big data, it is necessary to find specific data in massive amounts of data. If the traditional tree traversal form is used, it will undoubtedly cause huge time overhead. , so an algorithm that can quickly index specific data is essential

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Key-Value storage system-oriented indexed searching method and system
  • Key-Value storage system-oriented indexed searching method and system
  • Key-Value storage system-oriented indexed searching method and system

Examples

Experimental program
Comparison scheme
Effect test

Embodiment 2

[0082] refer to Figure 5 , Figure 5 It is a method flow chart of Embodiment 2 of a Key-Value storage system-oriented index query method proposed by the present invention;

[0083] refer to Figure 6 , Figure 6 It is an implementation diagram of Embodiment 2 of a Key-Value storage system-oriented index query method proposed by the present invention;

[0084] Such as Figure 5 and Figure 6 Shown, the concrete steps of the embodiment 2 that the present invention proposes are:

[0085] (1) First retrieve the deepest block node;

[0086] (1.1) Obtain the key value of the key-value data item to be retrieved. Suppose the key to be retrieved is: 001010010..., the maximum depth k of the tree is calculated through the properties of the complete binary tree and the maximum node number of the tree to be 5, so the key is taken first The first five digits are 00101;

[0087] (1.2) 00101 has 2 "0"s before the first "1" appears, so that the number j=2, so first set a variable i, t...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention discloses a Key-Value storage system-oriented indexed searching method and system. The method comprises the steps of S1, acquiring a Key-Value data item, storing the Key-Value data item into block, and generating a prefix complete binary tree according to block nodes; S2, acquiring a key value, and determining a key value digit number k according to the height of the binary tree, wherein the key value is a binary number; S3, acquiring first k digits of the key value, traversing from the first digit of the first k digits of the key value, searching the first 1 in the first k digits of the key value, recording a number j of digits in front of the first 1; S4, judging whether j is smaller than k or not, if j is smaller than k, enabling an objective result i to be equal to 2j, and executing S5, and if j is not smaller than k, enabling the objective result i to be equal to 2k-1-1, and executing S6; S5, cyclically searching from a (j+2)th digit of the key value, and when 1 is searched, enabling i to be equal to 2*(i+1); otherwise, enabling i to be equal to 2*i+1; stopping searching to obtain the objective result i when j is equal to k, and executing S6; S6, through the i value, searching block[i] in the prefix complete binary tree, judging whether the block[i] is not-null or not, and if the block[i] is not-null, outputting a value of the objective result i ; if the block[i] is null, enabling k to be equal to k-1, and then executing S3 until k is equal to 0.

Description

technical field [0001] The invention relates to the technical field of data index query, in particular to an index query method and system oriented to a Key-Value storage system. Background technique [0002] With the rapid development of the Internet, the world today has entered the era of "big data". The latest report of the international data company IDC predicts that within ten years from 2014, the total amount of data generated globally every year will increase by 40%, or about The total amount of data will double every two years, and by 2020 the total amount of global data will reach 44ZB. With the rapid growth of data volume, the form of data is also developing from traditional structured data to unstructured or semi-structured data forms. Traditional relational databases are stretched for the storage capacity of these data. Indexing, web serving of high-traffic sites, and sending streaming media data. In addition, for a specific system, most of the retrieval is bas...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
IPC IPC(8): G06F17/30
CPCG06F16/2246
Inventor 孙辉陈国栋徐殷
Owner ANHUI UNIVERSITY
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products