Patent ID: 9053140
Filing Date: 2015-06-09
Classification: G06F

Abstract:
1. A method for identifying a closest common ancestor for two leaf nodes, the method comprising: storing a B+tree data structure having a plurality of interior nodes and a plurality of leaf nodes, where each interior node has a plurality of entries, where each entry has a corresponding key and links the interior node to a child node, where the plurality of entries are sorted based on the corresponding entry key, where each leaf node has one or more records; obtaining a search key for traversing the B+tree; identifying a first interior node based on the search key; identifying a first entry of the first interior node based on the search key; determining that the first entry has a previous adjacent entry and a next adjacent entry in the first interior node; based on the determination, identifying the first interior node as an estimated closest common ancestor of a leaf node corresponding to the search key.