US 2019/0294716 A1Published application

Reduced bandwidth queries in b e-trees using approximate membership query data structures

AssigneeVMware, Inc.

InventorsAbhishek GUPTA, Rob T. JOHNSON, Srinath PREMACHANDRAN, Richard P. SPILLANE, Sandeep RANGASWAMY, Jorge GUERRA DELGADO, Kapil CHOWKSEY, Wenguang WANG

Life of this patent

Estimating the term…

patentgrep

Loading patent…

Abstract

Exemplary methods, apparatuses, and systems include a file system process reading a first node in a tree data structure from a first memory. The first node includes a first approximate membership query data structure (“AMQ”), a first plurality of child pointers, a first plurality of pivot values, and a first buffer. The file system process determines that the first plurality of child pointers exceeds a maximum size. Using a pivot value in the first plurality of pivot values, the file system process splits the first node into a second node and a third node. The file system process uses the pivot value to split the first buffer into a second buffer and a third buffer. Using the pivot value and the first AMQ, the file system process generates a second AMQ and a third AMQ.

Claims20

Dependent claims

A computer-implemented method, comprising:

reading a first node in a tree data structure from a first memory, the first node including a first approximate membership query data structure (“AMQ”), a first plurality of child pointers, a first plurality of pivot values, and a first buffer, wherein the first AMQ includes approximate membership of the first buffer;
determining that a quantity of child pointers in the first plurality of child pointers exceeds a maximum number of child pointers;
splitting, using a pivot value in the first plurality of pivot values the first node into a second node and a third node, wherein a first portion of the first plurality of child pointers are included in the second node and a second portion of the first plurality of child pointers are included in the third node;
splitting, using the pivot value, the first buffer into a second buffer and a third buffer, wherein the second node includes the second buffer and the third node includes the third buffer;
and
generating, using the pivot value and the first AMQ, a second AMQ and a third AMQ, wherein the second AMQ includes approximate membership of the second buffer and the third AMQ includes approximate membership of the third buffer and wherein the second node includes the second AMQ and the third node includes the third AMQ.

3 more elements

A non-transitory computer-readable medium storing instructions, which when executed by a processing device, cause the processing device to perform a method comprising:

reading a first node in a tree data structure from a first memory, the first node including a first approximate membership query data structure (“AMQ”), a first plurality of child pointers, a first plurality of pivot values, and a first buffer, wherein the first AMQ includes approximate membership of the first buffer;
determining that a quantity of child pointers in the first plurality of child pointers exceeds a maximum number of child pointers;
splitting, using a pivot value in the first plurality of pivot values, the first node into a second node and a third node, wherein a first portion of the first plurality of child pointers are included in the second node and a second portion of the first plurality of child pointers are included in the third node;
splitting, using the pivot value, the first buffer into a second buffer and a third buffer, wherein the second node includes the second buffer and the third node includes the third buffer;
and
generating, using the pivot value and the first AMQ, a second AMQ and a third AMQ, wherein the second AMQ includes approximate membership of the second buffer and the third AMQ includes approximate membership of the third buffer and wherein the second node includes the second AMQ and the third node includes the third AMQ.

3 more elements

An apparatus comprising:

a processing device;
and
a memory coupled to the processing device, the memory storing instructions which, when executed by the processing device, cause the apparatus to:
read a first node in a tree data structure from a first memory, the first node including a first approximate membership query data structure (“AMQ”), a first plurality of child pointers, a first plurality of pivot values, and a first buffer, wherein the first AMQ includes approximate membership of the first buffer;
determine that a quantity of child pointers in the first plurality of child pointers exceeds a maximum number of child pointers;
split, using a pivot value in the first plurality of pivot values, the first node into a second node and a third node, wherein a first portion of the first plurality of child pointers are included in the second node and a second portion of the first plurality of child pointers are included in the third node;
split, using the pivot value, the first buffer into a second buffer and a third buffer, wherein the second node includes the second buffer and the third node includes the third buffer;
and
generate, using the pivot value and the first AMQ, a second AMQ and a third AMQ, wherein the second AMQ includes approximate membership of the second buffer and the third AMQ includes approximate membership of the third buffer and wherein the second node includes the second AMQ and the third node includes the third AMQ.

6 more elements

Dependencies are inferred from the claim text.