Efficient B-Tree data serialization

Patent metadata

Field	Value
Publication number	US-10248676-B2
Application number	US-201615082785-A
Country	US
Kind code	B2
Filing date	Mar 28, 2016
Priority date	Jan 6, 2014
Publication date	Apr 2, 2019
Grant date	Apr 2, 2019

Abstract

B-Tree data is serialized to existing data for all types of workloads by converting a B-Tree data structure into a format capable of being stored and resurrected while containing all data stored in the B-Tree data structure and information relating to the B-Tree data structure. The serialized B-Tree data is divided into a plurality of sections. The serialized B-Tree data is stored into a plurality of buffers, where storing the B-Tree information section in a first binary buffer, the B-Tree key section in a second binary buffer, and the B-Tree data section in a third binary buffer. In the B-Tree data section, B-Tree data elements stored in the B-Tree data structure are saved, where a size of the B-Tree data section is equal to a total number of the B-Tree data elements in the B-Tree data structure multiplied by a size of each of the B-Tree data elements.

First claim

What is claimed is:

1. A method for efficient B-Tree data serialization using a processor device in a computing environment, comprising:
serializing B-Tree data to existing data for one of a plurality of workloads by converting a B-Tree data structure into a format capable of being stored and resurrected while containing all data stored in the B-Tree data structure and information relating to the B-Tree data structure; wherein the B-Tree data is serialized to replace logs associated with the existing data with the serialized B-Tree data to mitigate rebuilding of the B-Tree structure upon access of the existing data stored in the B-Tree data structure;
dividing the serialized B-Tree data into a plurality of sections, wherein the plurality of sections include each of a B-Tree information section, a B-Tree key section, and a B-Tree data section;
storing the serialized B-Tree data into a plurality of buffers, wherein the B-Tree information section is stored in a first binary buffer, the B-Tree key section is stored in a second binary buffer, and the B-Tree data section is stored in a third binary buffer;
saving, in the B-Tree data section, B-Tree data elements stored in the B-Tree data structure, wherein a size of the B-Tree data section is equal to a total number of the B-Tree data elements in the B-Tree data structure multiplied by a size of each of the B-Tree data elements; and
saving a plurality keys used in the B-Tree data structure in the B-Tree key section, wherein the plurality keys are ordered according to a tree scan order, and a size of the B-Tree key section is equal to a total number of keys saved in inner nodes plus a total number of keys saved in leaves multiplied by a size of one of the plurality of keys.

2. The method of claim 1 , further including saving a plurality of information describing the B-Tree data structure in the B-Tree information section, wherein the plurality of information includes at least sizes and amounts of elements in the B-Tree data structure.

3. The method of claim 1 , further using the B-Tree information section for calculating memory required for the B-Tree data structure when deserializing the serialized B-Tree data.

4. A system for efficient B-Tree data serialization using a processor device in a computing environment, the system comprising:
at least one processor device operable in the computing storage environment for controlling the B-Tree data serialization, wherein the at least one processor device:
serializes B-Tree data to existing data for one of a plurality of workloads by converting a B-Tree data structure into a format capable of being stored and resurrected while containing all data stored in the B-Tree data structure and information relating to the B-Tree data structure; wherein the B-Tree data is serialized to replace logs associated with the existing data with the serialized B-Tree data to mitigate rebuilding of the B-Tree structure upon access of the existing data stored in the B-Tree data structure,
divides the serialized B-Tree data into a plurality of sections, wherein the plurality of sections include each of a B-Tree information section, a B-Tree key section, and a B-Tree data section,
stores the serialized B-Tree data into a plurality of buffers, wherein the B-Tree information section is stored in a first binary buffer, the B-Tree key section is stored in a second binary buffer, and the B-Tree data section is stored in a third binary buffer,
saves, in the B-Tree data section, B-Tree data elements stored in the B-Tree data structure, wherein a size of the B-Tree data section is equal to a total number of the B-Tree data elements in the B-Tree data structure multiplied by a size of each of the B-Tree data elements, and
saves a plurality keys used in the B-Tree data structure in the B-Tree key section, wherein the plurality keys are ordered according to a tree scan order, and a size of the B-Tree key section is equal to a total number of keys saved in inner nodes plus a total number of keys saved in leaves multiplied by a size of one of the plurality of keys.

5. The system of claim 4 , wherein the at least one processor device saves a plurality of information describing the B-Tree data structure in the B-Tree information section, wherein the plurality of information includes at least sizes and amounts of elements in the B-Tree data structure.

6. The system of claim 4 , wherein the at least one processor device uses the B-Tree information section for calculating memory required for the B-Tree data structure when deserializing the serialized B-Tree data.

7. A computer program product for efficient B-Tree data serialization using a processor device using a processor device in a computing environment, the computer program product comprising a non-transitory computer-readable storage medium having computer-readable program code portions stored therein, the computer-readable program code portions comprising:
an executable portion that serializes B-Tree data to existing data for one of a plurality of workloads by converting a B-Tree data structure into a format capable of being stored and resurrected while containing all data stored in the B-Tree data structure and information relating to the B-Tree data structure; wherein the B-Tree data is serialized to replace logs associated with the existing data with the serialized B-Tree data to mitigate rebuilding of the B-Tree structure upon access of the existing data stored in the B-Tree data structure;
an executable portion that divides the serialized B-Tree data into a plurality of sections, wherein the plurality of sections include each of a B-Tree information section, a B-Tree key section, and a B-Tree data section;
an executable portion that stores the serialized B-Tree data into a plurality of buffers, wherein the B-Tree information section is stored in a first binary buffer, the B-Tree key section is stored in a second binary buffer, and the B-Tree data section is stored in a third binary buffer;
an executable portion that saves, in the B-Tree data section, B-Tree data elements stored in the B-Tree data structure, wherein a size of the B-Tree data section is equal to a total number of the B-Tree data elements in the B-Tree data structure multiplied by a size of each of the B-Tree data elements; and
an executable portion that saves a plurality keys used in the B-Tree data structure in the B-Tree key section, wherein the plurality keys are ordered according to a tree scan order, and a size of the B-Tree key section is equal to a total number of keys saved in inner nodes plus a total number of keys saved in leaves multiplied by a size of one of the plurality of keys.

8. The computer program product of claim 7 , further including an executable portion that saves a plurality of information describing the B-Tree data structure in the B-Tree information section, wherein the plurality of information includes at least sizes and amounts of elements in the B-Tree data structure.

9. The computer program product of claim 7 , further including an executable portion that uses the B-Tree information section for calculating memory required for the B-Tree data structure when deserializing the serialized B-Tree data.

Assignees

• IBM
• Int Business Machiens Corporation

Inventors

• Demidov Lilia
• Halowani Nir
• Kuttner Yifat
• Sasson Ben

Classifications

• G06F16/2272

  Management thereof · CPC title

• G06F16/2246 Primary

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

• G06F17/30327 Primary

  Physics · mapped topic

• G06F17/30336

  Physics · mapped topic