Bulk-load for B-trees

Patent metadata

Field	Value
Publication number	US-11048678-B2
Application number	US-201916353535-A
Country	US
Kind code	B2
Filing date	Mar 14, 2019
Priority date	Mar 14, 2019
Publication date	Jun 29, 2021
Grant date	Jun 29, 2021

Abstract

Embodiments described herein are related to bulk loading data into a B-tree. Embodiments include generating a first leaf node of a B-tree by allocating a first page for the first leaf node from a leaf page queue comprising a first plurality of sequential pages; and writing one or more tuples to the first page allocated for the first leaf node. Embodiments further include generating an parent node for the first leaf node and a second leaf node of the B-tree by allocating a third page for the parent node from an parent page queue comprising a second plurality of sequential pages, the parent node comprising a first indication of the first leaf node and a second indication of the second leaf node, the first indication and the second indication stored in the third page allocated for the parent.

First claim

What is claimed is:

1. A method for bulk load for a B-tree, comprising:
receiving a stream of sorted tuples;
generating a first leaf node of the B-tree by allocating a first page for the first leaf node from a leaf page queue comprising a first plurality of sequential pages;
writing one or more tuples of the stream of sorted tuples sequentially to the first page allocated for the first leaf node;
determining that the first leaf node is full;
generating a second leaf node of the B-tree by allocating a second page for the second leaf node from the leaf page queue, wherein the second page is sequential with the first page;
writing one or more additional tuples of the stream of sorted tuples sequentially to the second page allocated for the second leaf node;
generating a parent node for the first leaf node and the second leaf node of the B-tree by allocating a third page for the parent node from a parent page queue comprising a second plurality of sequential pages, the parent node comprising a first indication of the first leaf node and a second indication of the second leaf node, the first indication and the second indication stored sequentially in the third page allocated for the parent node;
generating a third leaf node by allocating a fourth page for the third leaf node from the leaf page queue, wherein the fourth page is sequential to the second page;
writing one or more further additional tuples of the stream of sorted tuples sequentially to the fourth page allocated for the third leaf node;
storing sequentially a third indication in the third page for the parent node;
obtaining the first indication from the parent node; and
reading the one or more tuples and the one or more additional tuples from the first leaf node and the second leaf node by sequentially accessing, in a single read operation based on the first indication, the first page and the second page.

2. The method of claim 1 , further comprising:
determining that the parent node is full; and
generating a second parent node by allocating a fifth page for the second parent node from the parent page queue sequential to the third page, the second parent node comprising a new indication of a newly generated leaf node.

3. The method of claim 2 , further comprising:
generating a third parent node by allocating a sixth page for the third parent node from a second parent page queue comprising a third plurality of sequential pages, the third parent node comprising a fourth indication of the parent node and a fifth indication of the second parent node, the fourth indication and the fifth indication stored sequentially in the sixth page allocated for the third parent node.

4. The method of claim 1 , further comprising:
balancing the B-tree to meet a minimum fullness when a right-most leaf node does not have a sufficient number of tuples; and
balancing the B-tree comprises redistributing one or more tuples among leaves of the B-tree so that the leaves of the B-tree meet the minimum fullness.

5. The method of claim 1 , further comprising:
obtaining a plurality of indications from a plurality of parent nodes; and
reading a plurality of tuples from each leaf node of a plurality of leaf nodes corresponding to the plurality of indications by sequentially accessing, in a single read operation based on the first indication, a plurality of pages corresponding to the plurality of leaf nodes.

6. A system for bulk load for a B-tree, comprising:
a processor; and
non-transitory computer-readable storage medium embodying computer program instructions for bulk loading for a B-tree, the computer program instructions implementing a method, the method comprising:
receiving a stream of sorted tuples;
generating a first leaf node of the B-tree by allocating a first page for the first leaf node from a leaf page queue comprising a first plurality of sequential pages;
writing one or more tuples of the stream of sorted tuples sequentially to the first page allocated for the first leaf node;
determining that the first leaf node is full;
generating a second leaf node of the B-tree by allocating a second page for the second leaf node from the leaf page queue, wherein the second page is sequential with the first page;
writing one or more additional tuples of the stream of sorted tuples sequentially to the second page allocated for the second leaf node;
generating a parent node for the first leaf node and the second leaf node of the B-tree by allocating a third page for the parent node from a parent page queue comprising a second plurality of sequential pages, the parent node comprising a first indication of the first leaf node and a second indication of the second leaf node, the first indication and the second indication stored sequentially in the third page allocated for the parent node;
generating a third leaf node by allocating a fourth page for the third leaf node from the leaf page queue, wherein the fourth page is sequential to the second page;
writing one or more further additional tuples of the stream of sorted tuples sequentially to the fourth page allocated for the third leaf node;
storing sequentially a third indication in the third page for the parent node;
obtaining the first indication from the parent node; and
reading the one or more tuples and the one or more additional tuples from the first leaf node and the second leaf node by sequentially accessing, in a single read operation based on the first indication, the first page and the second page.

7. The system of claim 6 , wherein the method further comprises:
determining that the parent node is full; and
generating a second parent node by allocating a fifth page for the second parent node from the parent page queue sequential to the third page, the second parent node comprising a new indication of a newly generated leaf node.

8. The system of claim 7 , wherein the method further comprises:
generating a third parent node by allocating a sixth page for the third parent node from a second parent page queue comprising a third plurality of sequential pages, the third parent node comprising a fourth indication of the parent node and a fifth indication of the second parent node, the fourth indication and the fifth indication stored sequentially in the sixth page allocated for the third parent node.

9. The system of claim 6 , wherein the method further comprises:
balancing the B-tree to meet a minimum fullness when a right-most leaf node does not have a sufficient number of tuples; and
balancing the B-tree comprises redistributing one or more tuples among leaves of the B-tree so that the leaves of the B-tree meet the minimum fullness.

10. The system of claim 6 , wherein the method further comprises:
obtaining a plurality of indications from a plurality of parent nodes; and
reading a plurality of tuples from each leaf node of a plurality of leaf nodes corresponding to the plurality of indications by sequentially accessing, in a single read operation based on the first indication, a plurality of pages corresponding to the plurality of leaf nodes.

11. A non-transitory computer-readable storage medium embodying computer program instructions for bulk loading for a B-tree, the computer program instructions, when executed by at least one processor, implementing a method, the method comprising:
receiving a stream of sorted tuples;
generating a first leaf node of the B-tree by allocating a first page for the first leaf node from a leaf page queue comprising a first plurality of sequential pages;
writing one or more tuples of the stream of sorted tuples sequentially to the first page allocated for the first leaf node;
determining that the first leaf node is full;

Assignees

• Vmware Inc

Inventors

• Gupta Abhishek
• Johnson Robert T
• Spillane Richard P
• Rangaswamy Sandeep
• Guerra Delgado Jorge
• Premachandran Srinath
• Chowksey Kapil

Classifications

• G06F16/24568

  Data stream processing; Continuous queries · CPC title

• G06F16/2246 Primary

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

• G06F7/08 Primary

  Sorting, i.e. grouping record carriers in numerical or other ordered sequence according to the classification of at least some of the information they carry (by merging two or more sets of carriers in ordered sequence G06F7/16) · CPC title