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

Concurrent updating method of balance tree and read-write system

An update method and balancing tree technology, applied in the field of data processing, can solve problems such as inability to parallelize, increase request latency, and block, and achieve the effects of reducing write-write conflicts, increasing concurrency, and saving CPU resources.

Active Publication Date: 2020-02-21
SHANGHAI JIAO TONG UNIV
View PDF6 Cites 3 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

However, the update of the balanced tree needs to add a barrier when updating each layer of the tree, resulting in blocking between each layer, which cannot be completely parallel
In addition, for a single read and write request, the request delay will also increase

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
  • Concurrent updating method of balance tree and read-write system
  • Concurrent updating method of balance tree and read-write system

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0036] The present invention will be described in detail below in conjunction with specific embodiments. The following examples will help those skilled in the art to further understand the present invention, but do not limit the present invention in any form. It should be noted that those skilled in the art can make several changes and improvements without departing from the concept of the present invention. These all belong to the protection scope of the present invention.

[0037] like figure 1 As shown, the specific process of the concurrent update method applicable to the balanced tree of the present invention is shown, and the location of the request key-value pair and the balance of the tree are completed. like figure 2 Shown is a schematic diagram of four worker threads and a B+ tree as an example. Combine the following figure 1 A detailed description of the update steps of the balanced tree:

[0038] In step S1, the server receives a request for updating the bal...

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 provides a balance tree concurrent updating method and a read-write system, and the method comprises the steps: caching a request for updating a balance tree at a leaf node in a positioning stage, then delaying the structure adjustment of the balance tree to a balance stage, and enabling a task to be divided to different working threads for execution. According to the method, redundant time-consuming operations and requests can be reduced to save CPU resources, task parallelism and data parallelism are fully utilized to improve the performance of updating the balance tree, and the performance of updating the balance tree under the condition of concurrent updating and the performance of querying the balance tree under the condition of reading and writing concurrency are improved.

Description

technical field [0001] The invention relates to the field of data processing, in particular to a method for concurrently updating a balanced tree and a reading and writing system. Background technique [0002] Balanced tree is a widely used data structure. It has the characteristic that each node has roughly the same number of subtree nodes. Therefore, it can make full use of the structure of dendrogram to make the access to nodes reach logarithmic complexity. Common balanced trees include AVL tree, red-black tree, B tree, B+ tree, etc. These trees are indexed in file systems (such as Btrfs), operating systems (such as the Linux kernel), database indexes (such as MySQL), etc. [0003] Because for each update request (including inserting a key-value pair, updating the value of a key-value pair, deleting a key-value pair, etc.), the balanced tree may trigger time-consuming self-balancing operations (such as rotation, splitting, merging, etc.) The concurrency control of "writ...

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): G06F16/22G06F16/23G06F9/50
CPCG06F16/2246G06F16/2315G06F9/5027G06F2209/5018
Inventor 陈榕沈斯杰陈海波臧斌宇
Owner SHANGHAI JIAO TONG UNIV
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

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com