Techniques for traversal and storage of directory entries of a storage volume

摘要

Techniques for adding a directory entry to an existing directory data structure maintained by a storage system for storing a plurality of directory entries are provided. A first storage index block is used for storing a pointer to a first hash value from among a plurality of hash values. A second storage index block is allocated when the first storage index block has reached a threshold level for storing pointers to hash values for the plurality of directory entries. A group of pointers including a pointer to a second hash value from among the plurality of hash values is selected. The group of pointers is stored in the second storage index block with a pointer to a third hash value from among the plurality of hash values such that the directory entry can be searched using the plurality of hash values.

主权项

1. A machine implemented method, comprising:
receiving a request to add a new directory entry to an indexed look up tree; determining hash values for the new directory entry; identifying a first pointer in a first storage index block based, at least in part, on a first of the hash values, wherein the first pointer references a first chain of directory entries; determining that the first chain of directory entries has reached a first threshold level for storing directory entries; selecting the first chain of directory entries and a second chain of directory entries, wherein the second chain of directory entries is referenced by a second pointer in the first storage index block; identifying a second storage index block based, at least in part, on a count of pointers from one or more storage index blocks that reference the second storage index block, wherein the second storage index block is a pre-existing storage index block; storing one or more pointers to directory entries of the first chain of directory entries and one or more pointers to directory entries of the second chain of directory entries in the second storage index block; and updating the first pointer and the second pointer to reference the second storage index block.