Partial compression of tree-based index structure

Patent metadata

Field	Value
Publication number	US-11714795-B2
Application number	US-202117483287-A
Country	US
Kind code	B2
Filing date	Sep 23, 2021
Priority date	Sep 23, 2021
Publication date	Aug 1, 2023
Grant date	Aug 1, 2023

Abstract

A system includes storage of data into a target memory location allocated to a target leaf node of a tree-based index structure, the target leaf node being a child node of a parent node of the tree-based index structure, where the tree-based index structure comprises one or more other leaf nodes which are child nodes of the parent node, and each of the target leaf node and the one or more other leaf nodes is associated with a plurality of allocated memory locations, incremental identification of all unused allocated memory locations between a first allocated memory location of a left-most one of the target leaf node and the one or more other leaf nodes and a last used allocated memory location of a right-most one of the target leaf node and the one or more other leaf nodes, and movement of data stored in the target leaf node and the one or more other leaf nodes into the identified unused allocated memory locations.

First claim

What is claimed is:

1. A system comprising:
at least one processing unit; and
a non-transitory computer-readable medium storing program code that, when executed by the at least one processing unit, causes the at least one processing unit to perform operations comprising:
storing data into a target memory location allocated to a target leaf node of a tree-based index structure, the target leaf node being a child node of a parent node of the tree-based index structure, where the tree-based index structure comprises one or more other leaf nodes which are child nodes of the parent node, and each of the target leaf node and the one or more other leaf nodes is associated with a plurality of allocated memory locations;
identifying all unused allocated memory locations between a first allocated memory location of a left-most one of the target leaf node and the one or more other leaf nodes and a last used allocated memory location of a right-most one of the target leaf node and the one or more other leaf nodes; and
moving data stored in the target leaf node and the one or more other leaf nodes into the identified unused allocated memory locations, the moving the data comprising moving a first data item from a first position of the target leaf node or the one or more other leaf nodes into a first identified unused allocated memory location and moving a second data item from a second position of the target leaf node or the one or more other leaf nodes into the first position.

2. A system according to claim 1 , where in the program code, when executed by the at least one processing unit, causes the at least one processing unit to perform operations comprising:
updating data stored in the parent node based on the moved data.

3. A system according to claim 1 , wherein the program code, when executed by the at least one processing unit, causes the at least one processing unit to perform operations comprising:
identifying one of the target leaf node and the one or more other leaf nodes which includes no used memory locations; and
de-allocating the memory locations of the identified leaf node.

4. A system according to claim 3 , wherein the program code, when executed by the at least one processing unit, causes the at least one processing unit to perform operations comprising:
updating data stored in the parent node based on the moved data and the de-allocated memory locations.

5. A system according to claim 1 , wherein allocated memory locations associated with the target leaf node and the one or more other leaf nodes are contiguous.

6. A system according to claim 1 , wherein the program code, when executed by the at least one processing unit, causes the at least one processing unit to perform operations comprising:
in response to storing the data into the target memory location, determining whether to move the data.

7. A computer-implemented method, comprising:
storing data into a target memory location allocated to a target leaf node of a tree-based index structure, the target leaf node being a child node of a parent node of the tree-based index structure, where the tree-based index structure comprises one or more other leaf nodes which are child nodes of the parent node, and each of the target leaf node and the one or more other leaf nodes is associated with a plurality of allocated memory locations;
identifying all unused allocated memory locations between a first allocated memory location of a left-most one of the target leaf node and the one or more other leaf nodes and a last used allocated memory location of a right-most one of the target leaf node and the one or more other leaf nodes; and
moving data stored in the target leaf node and the one or more other leaf nodes into the identified unused allocated memory locations, the moving the data comprising moving a first data item from a first position of the target leaf node or the one or more other leaf nodes into a first identified unused allocated memory location and moving a second data item from a second position of the target leaf node or the one or more other leaf nodes into the first position.

8. A method according to claim 7 , further comprising:
updating data stored in the parent node based on the moved data.

9. A method according to claim 7 , further comprising:
identifying one of the target leaf node and the one or more other leaf nodes which includes no used memory locations; and
de-allocating the memory locations of the identified leaf node.

10. A method according to claim 9 , further comprising:
updating data stored in the parent node based on the moved data and the de-allocated memory locations.

11. A method according to claim 7 , wherein allocated memory locations associated with the target leaf node and the one or more other leaf nodes are contiguous.

12. A method according to claim 7 , further comprising:
in response to storing the data into the target memory location, determining whether to move the data.

13. A non-transitory computer-readable medium storing program code that, when executed by at least one processing unit, causes the at least one processing unit to perform operations comprising:
storing data into a target memory location allocated to a target leaf node of a tree-based index structure, the target leaf node being a child node of a parent node of the tree-based index structure, where the tree-based index structure comprises one or more other leaf nodes which are child nodes of the parent node, and each of the target leaf node and the one or more other leaf nodes is associated with a plurality of allocated memory locations;
identifying all unused allocated memory locations between a first allocated memory location of a left-most one of the target leaf node and the one or more other leaf nodes and a last used allocated memory location of a right-most one of the target leaf node and the one or more other leaf nodes; and
moving data stored in the target leaf node and the one or more other leaf nodes into the identified unused allocated memory locations, the moving the data comprising moving a first data item from a first position of the target leaf node or the one or more other leaf nodes into a first identified unused allocated memory location and moving a second data item from a second position of the target leaf node or the one or more other leaf nodes into the first position.

14. A medium according to claim 13 , wherein the program code, when executed by the at least one processing unit, causes the at least one processing unit to perform operations comprising:
updating data stored in the parent node based on the moved data.

15. A medium according to claim 13 , wherein the program code, when executed by the at least one processing unit, causes the at least one processing unit to perform operations comprising:
identifying one of the target leaf node and the one or more other leaf nodes which includes no used memory locations; and
de-allocating the memory locations of the identified leaf node.

16. A medium according to claim 15 , wherein the program code, when executed by the at least one processing unit, causes the at least one processing unit to perform operations comprising:
updating data stored in the parent node based on the moved data and the de-allocated memory locations.

17. A medium according to claim 13 , wherein allocated memory locations associated with the target leaf node and the one or more other leaf nodes are contiguous.

18. A medium according to claim 13 , wherein the program code, when executed by the at least one processing unit, caus

Assignees

• Sap Se

Inventors

• Legler Thomas

Classifications

• G06F16/2246 Primary

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

• G06F12/0238

  Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory · CPC title

• G06F16/2282

  Tablespace storage structures; Management thereof · CPC title

• G06F16/901 Primary

  Indexing; Data structures therefor; Storage structures (for retrieval from the web G06F16/951) · CPC title

• G06F16/9027

  Trees · CPC title