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

R-tree index optimization method based on multi-granularity distributed read-write locks based on leaf nodes

A leaf node and optimization method technology, applied in the field of database indexing, can solve problems such as reducing parallelism, resource waste, and low resource utilization

Active Publication Date: 2021-05-04
NORTHEASTERN UNIV LIAONING
View PDF3 Cites 0 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

However, there are problems of blocking waiting for locks and low concurrency, especially when queries and updates are frequent and the R tree level is relatively high
Because when using the R-tree index, the root node of the R-tree is locked, and the entire R-tree is monopolized, so many nodes that are not affected by the update cannot be accessed concurrently, which reduces parallelism and causes a lot of waste of resources.
like figure 1 As shown, if there is a query for the data in grid No. 20, and an update is for the data in grid No. 63, the two areas do not intersect. When the query operation is performed, the update operation waits for the root lock, by This results in poor resource utilization

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
  • R-tree index optimization method based on multi-granularity distributed read-write locks based on leaf nodes
  • R-tree index optimization method based on multi-granularity distributed read-write locks based on leaf nodes
  • R-tree index optimization method based on multi-granularity distributed read-write locks based on leaf nodes

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0026] In order to make the object, technical solution and advantages of the present invention clearer, the present invention will be further described in detail below in conjunction with the accompanying drawings and specific examples. These examples are illustrative only and not limiting of the invention.

[0027] The specific implementation steps of distributed read-write locks for R-tree leaf nodes:

[0028] Step 1: First, operate in the HBase-based R-tree index to obtain specific request information, obtain the specific grid id to be operated according to the information, and find the R-tree leaf node where the grid is located. Input range query and update information, including id and lower left and upper right coordinate information. Then get the ID and latitude and longitude of the moving object, and then calculate the cellID of the grid according to the latitude and longitude of the moving object;

[0029] Step 2: If Figure 6 As shown, the dotted ellipse is the lo...

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 an R-tree index optimization method based on multi-granularity distributed read-write locks of leaf nodes. After the leaf node is locked, the head element of the lock waiting queue acquires the lock, and when the update operation causes the R-tree index structure to change, other elements in the lock waiting queue cannot continue to acquire locks at the leaf node, and the nodes of these locks are temporarily Delete to make it execute the query operation again from the root node to ensure the correctness of the result. Read-write locks are established on leaf nodes, which reduces the granularity of locks, supports a higher degree of parallelism, and improves the execution efficiency of operations such as queries and updates.

Description

technical field [0001] The invention relates to the field of database indexing, in particular to an R-tree index optimization method based on multi-granularity distributed read-write locks of leaf nodes. Background technique [0002] Mobile applications represented by Location Based Service (LBS) have entered the era of mobile big data and become an important part of people's daily life. quality of life. With the expansion of the scale of mobile applications, the queries in mobile services also show distinct streaming characteristics. Existing systems cannot effectively handle the challenges faced in terms of scalability, real-time, reliability and performance. Data processing in the era of mobile big data requires not only a computing platform with stronger and more flexible storage and processing capabilities, but also processing and optimization technologies for related mobile services based on the computing platform. [0003] In the processing and optimization technol...

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
Patent Type & Authority Patents(China)
IPC IPC(8): G06F16/22
Inventor 王波涛田箫李睿亢建强
Owner NORTHEASTERN UNIV LIAONING
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