Estimating a number of entries in a dispersed hierarchical index

1. A method of estimating a number of entries in a dispersed hierarchical index of a dispersed storage network comprising:

determining a number of walks to perform on the dispersed hierarchical index of the dispersed storage network to produce a determination, where the dispersed hierarchical index includes a root node, a plurality of index nodes and a plurality of leaf nodes, where the root node indexes the plurality of index nodes, and the plurality of index nodes index the plurality of leaf nodes;

conducting a plurality of walks based on the determination, where each respective walk of the plurality of walks starts at the root node and ends at a respective leaf node of the plurality of leaf nodes;

determining a respective number of walk entries associated with each respective walk of the plurality of walks; and

averaging the respective number of walk entries associated with each respective walk of the plurality of walks to produce an estimated total number of entries for the dispersed hierarchical index.

2. The method of claim 1 , wherein the plurality of walks are random walks.

3. The method of claim 1 , wherein the dispersed hierarchical index is use to locate a plurality of data objects stored as a plurality of sets of encoded data slices.

4. The method of claim 3 , wherein the plurality of sets of encoded data slices are associated with a dispersed storage network address.

5. The method of claim 4 , further comprising using the dispersed hierarchical index to locate the dispersed storage network address using keyword searching.

6. The method of claim 1 , wherein one or more of the root node, the plurality of index nodes and the plurality of leaf nodes comprise a plurality of entries of one or more of an associated index key range, node pointers, and pointers to data objects stored in the dispersed storage network.

7. The method of claim 6 , wherein one or more of the node pointers and pointers to data objects stored in the dispersed storage network include a virtual dispersed storage network address corresponding to one or more of a storage location of a node and a storage location of a data object.

8. The method of claim 1 , further comprising dispersed storage error encoding one or more of the root node, the plurality of index nodes, and the plurality of leaf nodes, to produce a set of index slices.

9. The method of claim 1 , wherein the dispersed hierarchical index includes dimensions associated with one or more index attributes, wherein the index attributes include one or more of a maximum number of levels, a minimum number of levels, a maximum number of child nodes in a parent-child node relationship, a minimum number of child nodes in the parent-child node relationship, a maximum number of sibling nodes at a common level, a minimum number of sibling nodes at a common level, a maximum number of entries in a node, and a minimum number of entries in the node.

10. A dispersed storage processing unit for estimating a number of entries in a dispersed hierarchical index of a dispersed storage network, the dispersed storage processing unit comprising:

a communications interface;

a memory; and

a computer processor;

where the memory includes instructions for causing the computer processor to:

determine a number of walks to perform on the dispersed hierarchical index of the dispersed storage network to produce a determination, where the dispersed hierarchical index includes a root node, a plurality of index nodes and a plurality of leaf nodes, where the root node indexes the plurality of index nodes, and the plurality of index nodes index the plurality of leaf nodes;

conduct a plurality of walks based on the determination, where each respective walk of the plurality of walks starts at the root node and ends at a respective leaf node of the plurality of leaf nodes;

determine a respective number of walk entries associated with each respective walk of the plurality of walks; and

average the respective number of walk entries associated with each respective walk of the plurality of walks to produce an estimated total number of entries for the dispersed hierarchical index.

11. The dispersed storage processing unit of claim 10 , wherein the plurality of walks are random walks.

12. The dispersed storage processing unit of claim 10 , wherein the dispersed hierarchical index is use to locate a plurality of data objects stored as a plurality of sets of encoded data slices.

13. The dispersed storage processing unit of claim 12 , wherein the plurality of sets of encoded data slices are associated with a dispersed storage network address.

14. The dispersed storage processing unit of claim 13 , wherein the memory further includes instructions for causing the processor to use the dispersed hierarchical index to locate the dispersed storage network address using keyword searching.

15. The dispersed storage processing unit of claim 10 , wherein one or more of the root node, the plurality of index nodes and the plurality of leaf nodes comprise a plurality of entries of one or more of an associated index key range, node pointers, and pointers to data objects stored in the dispersed storage network.

16. The dispersed storage processing unit of claim 15 , wherein one or more of the node pointers and pointers to data objects stored in the dispersed storage network include a virtual dispersed storage network address corresponding to one or more of a storage location of a node and a storage location of a data object.

17. The dispersed storage processing unit of claim 10 , wherein the memory further includes instructions for causing the processor to dispersed storage error encoding one or more of the root node, the plurality of index nodes, and the plurality of leaf nodes, to produce a set of index slices.

18. The dispersed storage processing unit of claim 10 , wherein the dispersed hierarchical index includes dimensions associated with one or more index attributes, wherein the index attributes include one or more of a maximum number of levels, a minimum number of levels, a maximum number of child nodes in a parent-child node relationship, a minimum number of child nodes in the parent-child node relationship, a maximum number of sibling nodes at a common level, a minimum number of sibling nodes at a common level, a maximum number of entries in a node, and a minimum number of entries in the node.

19. A dispersed storage network comprising:

a plurality of dispersed storage units storing encoded data slices of a set of encoded data slices;

a dispersed storage processing unit including:

a communications interface;

a memory; and

a computer processor;

where the memory includes instructions for causing the computer processor to:

determine a number of walks to perform on a dispersed hierarchical index of the dispersed storage network to produce a determination, where the dispersed hierarchical index includes a root node, a plurality of index nodes and a plurality of leaf nodes, where the root node indexes the plurality of index nodes, and the plurality of index nodes index the plurality of leaf nodes;

conduct a plurality of walks based on the determination, where each respective walk of the plurality of walks starts at the root node and ends at a respective leaf node of the plurality of leaf nodes;

determine a respective number of walk entries associated with each respective walk of the plurality of walks; and

average the respective number of walk entries associated with each respective walk of the plurality of walks to produce an estimated total number of entries for the dispersed hierarchical index.

20. The dispersed storage network of claim 19 , wherein the plurality of walks are random walks.