Data read method, data update method, electronic device, and program product

Patent metadata

Field	Value
Publication number	US-12072937-B2
Application number	US-202218065569-A
Country	US
Kind code	B2
Filing date	Dec 13, 2022
Priority date	Sep 30, 2022
Publication date	Aug 27, 2024
Grant date	Aug 27, 2024

Abstract

Data reads and related data reading processes are described. An example data read method includes: receiving a data read request, the data read request being aimed at target node data stored in a target node of a B+ tree; acquiring node location information, the node location information indicating a storage location of node data in a node data set of the B+ tree, and the node data set including the target node data; and determining a target storage location of the target node data. Beneficially, data stored in the B+ tree can be read and updated efficiently while reducing computing overhead.

First claim

What is claimed is:

1. A method, comprising:
generating, by a system comprising at least one processor, a B+ tree structure for an append-only B+ tree, wherein the append-only B+ tree comprises nodes, wherein a subset of the nodes comprises leaf nodes that comprise data, the data comprising respective key-value pairs, and wherein the B+ tree structure comprises:
a single data block that comprises the key-value pairs respectively associated with the leaf nodes of the append-only B+ tree, and
a node location information array that specifies respective offsets of locations of the key-value pairs in the single data block relative to a reference location of the single data block;

receiving, by the system, a data read request for a data read, the data read request comprising a key associated with target node data stored in a target leaf node of the append-only B+ tree; and
based on the node location information and the key, identifying, by the system, using the respective offsets to perform a binary search of the single data block, a location of a key-value pair associated with the target node data.

2. The method of claim 1 , wherein the nodes of the append-only B+ tree further comprise a root node and index nodes.

3. The method of claim 1 , wherein the index nodes comprise index entries that define how to index from the root node to the index nodes to the leaf nodes.

4. The method of claim 1 , wherein the root node, the index nodes, and the leaf nodes are stored across distributed storage nodes.

5. The method of claim 1 , further comprising:
reading, in response to a determination that the target node data is stored in a cache, the target node data from the cache.

6. The method of claim 1 , further comprising:
reading the target node data from a target storage location of the target node data; and
storing, in response to a determination that a difference between a layer of the B+ tree where the target leaf node is located and a layer where the root node of the B+ tree is located is less than a threshold number of layers, the target node data in a cache.

7. The method of claim 1 , further comprising:
reading the target node data from a target storage location of the target node data; and
storing, in response to a determination that a number of reads of the target node data is greater than a threshold number, the target node data in a cache.

8. The method of claim 1 , wherein the key is a first key, the target node data is a first target node data, the target leaf node is a first target leaf node, the location is a first location, the key-value pair is a first key-value pair, and further comprising:
receiving, by the system, an update request comprising a second key and update data, wherein the second key is associated with second target node data stored in second target leaf node of the append-only B+ tree, and the update data applicable to a data update for the second target node data;
based on the node location information and the second key, identifying, by the system, using the respective offsets to perform another binary search of the single data block, a second location of a second key-value pair associated with the second target node data; and
updating, by the system, the second target node data using the update data.

9. A system, comprising:
a processor; and
a memory, coupled to the processor, that stores executable instructions that, when executed by the processor, facilitate performance of operations, comprising:
generating a B+ tree structure for an append-only B+ tree, wherein the append-only B+ tree comprises nodes, wherein a subset of the nodes comprises leaf nodes that comprise data, the data comprising respective key-value pairs, and wherein the B+ tree structure comprises:
a single data block that comprises the key-value pairs respectively associated with the leaf nodes of the append-only B+ tree, and
a node location information array that specifies respective offsets of locations of the key-value pairs in the single data block relative to a reference location of the single data block;

receiving a data read request for a data read, the data read request comprising a key associated with target node data stored in a target leaf node of the append-only B+ tree; and
based on the node location information and the key, identifying using the respective offsets to perform a binary search of the single data block in the memory, a location of a key-value pair associated with the target node data.

10. The system of claim 9 , wherein the nodes of the append-only B+ tree further comprise a root node and index nodes.

11. The system of claim 9 , wherein the index nodes comprise index entries that define how to index from the root node to the index nodes to the leaf nodes.

12. The system of claim 9 , wherein the root node, the index nodes, and the leaf nodes are stored across distributed storage nodes.

13. The system of claim 9 , wherein the operations further comprise:
reading, in response to a determination that the target node data is stored in a cache, the target node data from the cache.

14. The system of claim 9 , wherein the operations further comprise:
reading the target node data from a target storage location of the target node data; and
storing, in response to a determination that a difference between a layer of the B+ tree where the target leaf node is located and a layer where the root node of the B+ tree is located is less than a threshold number of layers, the target node data in a cache.

15. The system of claim 9 , wherein the operations further comprise:
reading the target node data from a target storage location of the target node data; and
storing, in response to a determination that a number of reads of the target node data is greater than a threshold number, the target node data in a cache.

16. The system of claim 9 , wherein the key is a first key, the target node data is a first target node data, the target leaf node is a first target leaf node, the location is a first location, the key-value pair is a first key-value pair, and wherein the operations further comprise:
receiving an update request comprising a second key and update data, wherein the second key is associated with second target node data stored in second target leaf node of the append-only B+ tree, and the update data applicable to a data update for the second target node data;
based on the node location information and the second key, identifying, using the respective offsets to perform another binary search of the single data block, a second location of a second key-value pair associated with the second target node data; and
updating the second target node data using the update data.

17. A non-transitory computer-readable medium having instructions stored thereon that, in response to execution, cause a system comprising a processor to perform operations comprising:
generating a B+ tree structure for an append-only B+ tree, wherein the append-only B+ tree comprises nodes, wherein a subset of the nodes comprises leaf nodes that comprise data, the data comprising respective key-value pairs, and wherein the B+ tree structure comprises:
a single data block that comprises the key-value pairs respectively associated with the leaf nodes of the append-only B+ tree, and
a node location information array that specifies respective offsets of locations of the key-value pairs in the single data block relative to a reference location of the single data block;

receiving a data read request for a data read, the data read request comprising a key associated with targ

Assignees

• Dell Products Lp

Inventors

• Shang Xiao Le
• Wang Xia
• Huang Xiangdong
• Sun Wesley Wei
• Wu Young Yangchun
• Li Xin

Classifications

• H04L41/145

  involving simulating, designing, planning or modelling of a network · CPC title

• G06F16/24552

  Database cache management · CPC title

• G06F16/23

  Updating · CPC title

• G06F16/9027 Primary

  Trees · CPC title

• G06F16/2246 Primary

  Trees, e.g. B+trees · CPC title