VMware, Inc.
READ ITERATOR FOR PRE-FETCHING NODES OF A B-TREE INTO MEMORY

Abstract:

Embodiments described herein are related to a method of scanning a B-tree. For example, a method comprises receiving a scan request to scan a B-tree having a plurality of levels, each level comprising one or more nodes, wherein for each of one or more levels of the plurality of levels, nodes are grouped into groups, where nodes of any given group are stored across sequential disk blocks. The method further comprises generating a queue for each level of the B-tree. For each queue, the method further comprises loading into memory a next group of nodes based upon determining a storage location of a node of the next group of nodes.