Apple Inc.

Christopher R McFall

Gursharan S Sidhu

Bill M Bruffey

Patrick W Dirks

A hierarchical filing system provides a cataloging of data stored in various locations within a memory device. An upside-down tree type structure provides a downwardly expanding cataloging structure wherein directories provide for further branchings. A branching from a directory is terminated when a file is reached. Each directory is assigned a unique directory identifier value. Then, each file or directory is coupled with the directory identifier value of its parent to provide the interconnection necessary to form the cataloging structure. The complete cataloging structure is organized in the leaf nodes of a B-Tree structure and distributed in an ascending order of the key values to provide a systematic search for a given key. Each file is capable of storing a predetermined number of location description information when data is segmented into non-contiguous segments in memory. A file extents record is used to maintain record of the further segmentation. File location information is kept in the form of file extents descriptors in the leaf nodes of the separate File Extents B-Tree. This extents information is sorted in an ascending order based on a key comprised of a unique file number of a file relative starting block location of the file extent.

Growing community of inventors

Palo Alto, CA, United States of America

Christopher R McFall