US 2013/0232152 A1Published application

Listing data objects using a hierarchical dispersed storage index

AssigneeCleversafe, Inc.

InventorsGreg Dhuse, Wesley Leggette, Adam Michael Gray, Ilya Volvovski, Andrew Baptist

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method begins by a dispersed storage (DS) processing module receiving a request for a data index list that identifies data objects having one or more common attributes, searching a hierarchical ordered index structure to identify a data object level index node corresponding to a first data object boundary match, and determining whether the data object level index node corresponds to a second data object boundary match. When the data object level index node does not correspond to the second data object boundary match, the method continues with the DS processing module searching an adjacent data object level index node to determine whether the adjacent data object level index node corresponds to the second data object boundary match. When the adjacent data object level index node corresponds to the second data object boundary match, the method continues with the DS processing module generating the data index list.

Claims16

Dependent claims

A method for execution by a processing module of a computer, the method comprises:

receiving, via an interface of the computer, a request for a data index list that identifies data objects having one or more common attributes of an attribute category, wherein indexing of a plurality of data objects is organized in accordance with an ordering of attributes of the attribute category and wherein the plurality of data objects is stored in a dispersed storage network (DSN);
searching, by the processing module and based on the one or more common attributes, a hierarchical ordered index structure that maps the indexing of the plurality of data objects to identify a data object level index node of the hierarchical ordered index structure that includes a first boundary data object index key corresponding to a first data object boundary match of the one or more common attributes;
determining, by the processing module, whether the data object level index node includes a second boundary data object index key corresponding to a second data object boundary match of the one or more common attributes;
when the data object level index node does not include the second boundary data object index key, searching, by the processing module, an adjacent data object level index node of the hierarchical ordered index structure to determine whether the adjacent data object level index node includes the second boundary data object index key;
when the adjacent data object level index node includes the second boundary data object index key, generating, by the processing module, the data index list to include the first boundary data object index key, a first ordered set of data object index keys of the data object level index node, the second boundary data object index key, and a second ordered set of data object index keys of the adjacent data object level index node;
and
outputting, via the interface, the data index list.

4 more elements

A dispersed storage (DS) module of a computing device, the DS module comprises:

a first module, when operable within the computing device, causes the computing device to:
receive, via an interface of the computing device, a request for a data index list that identifies data objects having one or more common attributes of an attribute category, wherein indexing of a plurality of data objects is organized in accordance with an ordering of attributes of the attribute category and wherein the plurality of data objects is stored in a dispersed storage network (DSN);
a second module, when operable within the computing device, causes the computing device to:
search, based on the one or more common attributes, a hierarchical ordered index structure that maps the indexing of the plurality of data objects to identify a data object level index node of the hierarchical ordered index structure that includes a first boundary data object index key corresponding to a first data object boundary match of the one or more common attributes;
determine whether the data object level index node includes a second boundary data object index key corresponding to a second data object boundary match of the one or more common attributes;
and
when the data object level index node does not include the second boundary data object index key, search an adjacent data object level index node of the hierarchical ordered index structure to determine whether the adjacent data object level index node includes the second boundary data object index key;
and
a third module, when operable within the computing device, causes the computing device to:
when the adjacent data object level index node includes the second boundary data object index key, generate the data index list to include the first boundary data object index key, a first ordered set of data object index keys of the data object level index node, the second boundary data object index key, and a second ordered set of data object index keys of the adjacent data object level index node;
and
output, via the interface, the data index list.

9 more elements

Dependencies are inferred from the claim text.

Facts

Application: 13/775,491Filed 25 Feb 2013
Priority: 2 Mar 2012
Published: 5 Sep 2013
Term ends: Not estimatedThe source records don’t support an estimate.

Classification10 codes

G06F 16/2272
Indexing structures: management thereof
G06F 3/067
Adopting a particular infrastructure: distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
G06F 11/10
Error detection or correction by redundancy in data representation, e.g. by using checking codes: adding special bits or symbols to the coded…
G06F 16/2228
Indexing; Data structures therefor; Storage structures: indexing structures