Bulk-load for B-trees

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;

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.

12. The non-transitory computer-readable storage medium of claim 11 , 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.

13. The non-transitory computer-readable storage medium of claim 12 , 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.

14. The non-transitory computer-readable storage medium of claim 11 , 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.