The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Aug. 17, 2021
Filed:
Jun. 05, 2018
Vmware, Inc., Palo Alto, CA (US);
Abhishek Gupta, Sunnyvale, CA (US);
Richard P. Spillane, Mountain View, CA (US);
Robert T. Johnson, Palo Alto, CA (US);
Wenguang Wang, Santa Clara, CA (US);
Kapil Chowksey, Cupertino, CA (US);
Jorge Guerra Delgado, Fremont, CA (US);
Sandeep Rangaswamy, Mountain View, CA (US);
Srinath Premachandran, Fremont, CA (US);
VMware, Inc., Palo Alto, CA (US);
Abstract
Embodiments herein are directed towards systems and methods for performing range lookups in B-trees. One example method involves receiving a request to return key-value pairs within a range of keys from the B-tree. The B-tree includes a plurality of nodes, each node being associated with a buffer that stores key-value pairs. The method further involves determining a fractional size of the range of keys. The method further involves, for each level of the B-tree, obtaining from within one or more buffers of one or more nodes of the level, a set of key-value pairs within the range of keys up to a size equal to the fractional size and transferring the set of key-value pairs to a result data structure. The method further involves sorting and merging all key-value pairs in the result data structure and returning the result data structure in response to the request.