Opportunistic tile-pulling, vacancy-filling method and apparatus for file-structure reorganization

A method for rearranging storage locations of data stored in a re-organizable storage space of a data storage means, where the storage means has addressable storage sub-areas each for storing a predefined maximum amount of data, where said sub-areas are logically linked to one another to thereby define a logical organization for the data contained in said storage sub-areas, said method comprising the steps of:

• (a) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas;
• (b) providing as a recorded definition of a goal state, pre-recorded indications of goal resting positions for each tile in the storage space of the re-organizable storage means;
• (c) identifying an already-existing vacancy space within the re-organizable storage space;
• and
• (d) moving into the identified vacancy space the data of one or more source tiles that have that identified vacancy space defined by the recorded goal state as the goal resting position for the moved one or more source tiles.

A method for defragmenting file data stored in a re-organizable storage space, where the storage space has addressable storage sub-areas each for storing a predefined maximum amount of data, where said sub-areas are logically linked to one another to thereby define a logical organization for the data contained in each said file, and where parts of the data of each file are defined as being logically adjacent to one another, said method comprising the steps of:

• (a) identifying one or more files or groups of files that are to be defragmented, the identified files or file groups residing in the re-organizable storage space;
• (b) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas;
• (c) recording as a definition of a goal state, indications of goal resting positions for each tile in the re-organizable storage space, where said goal state places logically adjacent tiles of each file in access-wise closer adjacency relative to one another than such tiles are in their original state;
• and
• (d) moving said tiles each from a current position to the corresponding goal resting position defined by the goal state, where a majority of said tile moves are performed just once for each of the moved tiles.

A method for fragmenting file data stored in a re-organizable storage space, where the storage space has addressable storage sub-areas each for storing a predefined maximum amount of data, where said sub-areas are logically linked to one another to thereby define a logical organization for the data contained in each said file, and where parts of the data of each file are defined as being logically adjacent to one another, said method comprising the steps of:

• (a) identifying one or more files or groups of files that are to be fragmented, the identified files or file groups residing in the re-organizable storage space;
• (b) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas;
• (c) recording as a definition of a goal state, indications of goal resting positions for each tile in the re-organizable storage space, where said goal state places logically adjacent tiles of each file in access-wise non-adjacency relative to one another;
• and
• (d) moving said tiles each from a current position to the corresponding goal resting position defined by the goal state.

A method for increasing fragmentation of file data stored in a re-organizable storage space, where the storage space has addressable storage sub-areas each for storing a predefined maximum amount of data, where said sub-areas are logically linked to one another to thereby define a logical organization for the data contained in each said file, and where parts of the data of each file are defined as being logically adjacent to one another, said method comprising the steps of:

• (a) identifying one or more files or groups of files whose degree of fragmentation is to be increased, the identified files or file groups residing in the re-organizable storage space;
• (b) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas;
• (c) recording as a definition of an original tile state, indications of original resting positions for each tile in the re-organizable storage space;
• (d) providing as a definition of a recorded goal state, pre-recorded indications of goal resting positions for each tile in the re-organizable storage space, where for each identified file whose degree of fragmentation is to be increased, said goal state places one or more of plural and respective source tiles that are access-wise adjacent to one another in the original tile state to one or more destination tiles that are each access-wise non-adjacent with respect to either one of the source tiles or another, logically-adjacent destination tile;
• and
• (e) moving said tiles each from a current position to the corresponding goal resting position defined by the goal state.

A method for interleave-wise fragmenting file data of two or more files, where said file data is stored in a re-organizable storage space, where the storage space has addressable storage sub-areas each for storing a predefined maximum amount of data, where said sub-areas are logically linked to one another to thereby define a logical organization for the data contained in each said file, where parts of the data of each file are defined as being logically adjacent to one another within the file, and where respective first, second and third parts that respectively belong to at least two different ones of said files are to be interleave-wise accessed one after the other by a predefined program, said method comprising the steps of:

• (a) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas;
• (b) providing as a recorded definition of a goal state, pre-recorded indications of goal resting positions for each tile in the re-organizable storage space, where said goal state places the respective first through third parts in interleaved access-wise adjacency to one another;
• and
• (c) moving said tiles each from a current position to the corresponding goal resting position defined by the goal state.

A method for rearranging storage locations of data stored in a re-organizable storage space of a data storage means, where the storage means has addressable storage sub-areas each for storing a predefined maximum amount of data, said method comprising the steps of:

• (a) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas;
• (b) identifying as a goal state, pre-recorded indications of goal resting positions for each tile in the re-organizable storage space;
• and
• (c) in accordance with the goal state, opportunistically moving tiles that are not in their goal resting positions to such goal resting positions when such goal resting positions are vacant.

An instructing apparatus for instructing a target data processing system to re-organize storage locations for data stored in a re-organizable storage space, where the storage space has addressable storage sub-areas each for storing a predefined maximum amount of data, said instructing apparatus providing instructions for causing said target data processing system to perform the steps of:

• (a) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas;
• (b) identifying as a goal state, pre-recorded indications of goal resting positions for each tile in the re-organizable storage space;
• and
• (c) in accordance with the identified goal state, opportunistically moving tiles that are not in their goal resting positions to such goal resting positions when such goal resting positions are vacant.

A machine system for carrying out data structure reorganization comprising:

• (a) a primary storage for storing a plurality of files in a file storage space in accordance with a first file storage organization, where the first file storage organization may be represented as a first mapping of tiles of data each in a corresponding tile space of the file storage space;
• and
• (b) file storage reorganizing means, operatively coupled to the primary storage, for reorganizing the storage organization of the primary storage such that one or more of the files are stored after the reorganization in the primary storage in accordance with a pre-defined second file storage organization that is different from said first file storage organization, where the pre-defined second file storage organization may be represented as a second mapping of the tiles of data each in a corresponding tile space;
• and where the file storage reorganizing means includes:
• (b.1) vacancy locating means for searching through the file storage space of the primary storage looking for a to-be-filled vacant space that is to be ultimately occupied according to the second mapping by a corresponding tile of data;
• and
• (b.2) tile moving means, operatively coupled to the vacancy locating means, for moving, in response to the finding of said to-be-filled vacant space, the corresponding tile of data from its currently occupied storage space to the found vacant space.

An instructing apparatus for instructing a target data processing system to re-organize storage locations for data stored in a re-organizable storage means,

• where the storage means has addressable storage sub-areas each for storing a predefined maximum amount of data, and
• where the storage means includes a directory structure for defining files of the storage means each as data contained in a respective directory-specified organization of said storage sub-areas and for further defining vacancy spaces each as provided by a respective directory-specified organization of said storage sub-areas,
• said instructing apparatus providing instructions for causing said target data processing system to perform the steps of:
• (a) subdividing the data of the re-organizable storage means into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas;
• (b) recognizing as a definition of a goal state, pre-recorded indications of goal locations for tiles in the re-organizable storage space;
• (c) identifying an already-existing vacancy space within the re-organizable storage means;
• and
• (d) opportunistically pulling into the identified vacancy space the data of one or more source tiles that have that identified vacancy space defined by the recognized goal state as the goal location for the moved one or more source tiles.