Method and system for renaming consecutive keys in a B-tree

• US 7,483,906 B2
• Filed: 04/14/2004
• Issued: 01/27/2009
• Est. Priority Date: 04/14/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: MacCormick, John Philip
• Primary Examiner(s): Breene; John E
• Assistant Examiner(s): MYINT, DENNIS Y
• Application Number:
  US10/823,870
• Publication Number:
  US 20050234951A1
• Time in Patent Office: 1,749 Days
• Field of Search: 707/3, 707/100, 707/200, 707/101, 707/104.1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

An efficient method for renaming consecutive keys in a B-tree representing a hierarchical namespace, such as a file system, has an estimated time efficiency of O(logN), where N is the number of nodes in the B-tree. All the consecutive keys to be renamed are first excised from the original B-tree to form a trimmed B-tree, and the excised nodes are stored in a separate temporary extracted B-tree. The nodes in extracted B-tree are then renamed, and the renamed extracted B-tree is inserted into the trimmed B-tree to form a final B-tree that contains the renamed keys.

Claims

1. A method of renaming a range of consecutive keys in an original B-tree having a plurality of keys stored therein, comprising:

excising the range of consecutive keys from the original B-tree, the original B-tree representing a file system, wherein renaming an element of the file system requires the changing of the values of the range of consecutive keys, the excision of the range of consecutive keys converting the original B-tree into a trimmed tree;

balancing the trimmed tree;

storing the range of consecutive keys excised from the original B-tree to form an extracted tree;

renaming the keys of the extracted tree to form a modified extracted tree;

inserting the modified extracted tree into the balanced trimmed tree to form a final B-tree; and

balancing the final B-tree,

wherein the original B-tree represents a hierarchical namespace of a file system of a computing device, and the range of consecutive keys belong to a directory of the file system such that the directory is represented as the B-tree, and wherein the changing of the values of the range of consecutive keys is in connection with the directory being renamed,

wherein each key in the original B-tree contains a pathname for a file or directory of the file system prior to the renaming of the directory,

wherein the excised range of consecutive keys satisfy a range query “

Y/”

≦

v≦

“

Y/∞

”

, wherein “

Y”

represents the element of the file system to be renamed, “

v”

represents keys in the B-tree, and “

∞

”

represents a special character defined to be greater than all characters in a set of alphanumeric symbols used for creating the plurality of keys, and

wherein the excising further comprises finding a root node of the extracted tree by traversing the original B-tree and stopping at a node in the original B-tree that has one or more keys that satisfy the range query, moving down from the node along two separate paths including a first path that follows “

Y/” and

a second path that follows “

Y/∞

”

, and continuing until reaching a leaf node along each of the two paths.

2. A method as in claim 1, wherein the step of changing includes changing a prefix field of a root node of the extracted tree.

3. A method as in claim 1, wherein the step of inserting the modified extracted tree into the trimmed tree involves a strict insertion.

4. A computer-readable storage medium having computer-executable instructions for performing steps for renaming a range of consecutive keys in an original B-tree having a plurality of keys stored therein, comprising:

excising the range of consecutive keys from the original B-tree, the original B-tree representing a file system, wherein renaming an element of the file system requires the changing of the values of the range of consecutive keys, the excision of the range of consecutive keys converting the original B-tree into a trimmed tree;

balancing the trimmed tree;

storing the range of consecutive keys excised from the original B-tree to form an extracted tree;

renaming the keys of the extracted tree to form a modified extracted tree;

inserting the modified extracted tree into the balanced trimmed tree to form a final B-tree; and

balancing the final B-tree,

wherein the original B-tree represents a hierarchical namespace of a file system of a computing device, and the range of consecutive keys belong to a directory of the file system such that the directory is represented as the B-tree, and wherein the changing of the values of the range of consecutive keys is in connection with the directory being renamed,

wherein each key in the original B-tree contains a pathname for a file or directory of the file system prior to the renaming of the directory,

wherein the excised range of consecutive keys satisfy a range query “

Y/”

≦

v≦

“

Y/∞

”

, wherein “

Y”

represents the element of the file system to be renamed, “

v”

represents the keys in the B-tree, and “

∞

”

represents a special character defined to be greater than all characters in a set of alphanumeric symbols used for creating the plurality of keys, and

wherein the excising further comprises finding a root node of the extracted tree by traversing the original B-tree and stopping at a node in the original B-tree that has one or more keys that satisfy the range query, moving down from the node along two separate paths including a first path that follows “

Y/” and

a second path that follows “

Y/∞

”

, and continuing until reaching a leaf node along each of the two paths.

5. A computer-readable storage medium as in claim 4, wherein the step of changing includes changing a prefix field of a root node of the extracted tree.

6. A computer-readable storage medium as in claim 4, wherein the step of inserting the modified extracted tree into the trimmed tree involves a strict insertion.

7. A method of modifying a B-tree, wherein the B-tree represents a file system of a computing device, wherein renaming an element of the file system requires the changing of the values of the range of consecutive keys, each key in the B-tree contains a pathname for a file or directory of the file system, the method comprising:

excising keys of a directory of the file system being renamed from the B-tree, the directory being represented as the B-tree, the excision of the keys of the directory converting the B-tree into a trimmed tree;

balancing the trimmed tree;

storing the keys of the directory excised from the B-tree in an extracted tree;

changing the values of the keys of the extracted tree to reflect a new name of the directory;

inserting the extracted tree with changed values of the keys into the balanced trimmed tree to form a final B-tree; and

balancing the final B-tree,

wherein the excised keys of the directory satisfy a range query “

Y/”

≦

v≦

“

Y/∞

”

, wherein “

Y”

represents the element of the file system to be renamed, “

v”

represents the keys in the B-tree, and “

∞

”

represents a special character defined to be greater than all characters in a set of alphanumeric symbols used for creating the plurality of keys, and

wherein the excising further comprises finding a root node of the extracted tree by traversing the original B-tree and stopping at a node in the original B-tree that has one or more keys that satisfy the range query, moving down from the node along two separate paths including a first path that follows “

Y/” and

a second path that follows “

Y/∞

”

, and continuing until reaching a leaf node along each of the two paths.

8. A method as in claim 7, wherein the step of changing the values of the keys of the extracted tree includes changing a prefix field of a root node of the extracted tree.

9. A computer-readable storage medium having computer-executable instructions for performing steps for modifying a B-tree, wherein the B-tree represents a file system of a computing device, wherein renaming an element of the file system requires the changing of the values of the range of consecutive keys, each key in the B-tree contains a pathname for a file or directory of the file system, the method comprising:

excising keys of a directory of the file system being renamed from the B-tree, the directory being represented as the B-tree, the excision of the keys of the directory converting the B-tree into a trimmed tree;

balancing the trimmed tree;

storing the keys of the directory excised from the B-tree in an extracted tree;

changing the values of the keys of the extracted tree to reflect a new name of the directory;

inserting the extracted tree with changed values of the keys into the balanced trimmed tree to form a final B-tree; and

balancing the final B-tree,

wherein the excised keys of the directory satisfy a range query “

Y/”

≦

v≦

“

Y/∞

”

, wherein “

Y”

represents the element of the file system to be renamed, “

v”

represents the keys in the B-tree, and “

∞

”

represents a special character defined to be greater than all characters in a set of alphanumeric symbols used for creating the plurality of keys, and

wherein the excising further comprises finding a root node of the extracted tree by traversing the original B-tree and stopping at a node in the original B-tree that has one or more keys that satisfy the range query, moving down from the node along two separate paths including a first path that follows “

Y/” and

a second path that follows “

Y/∞

”

, and continuing until reaching a leaf node along each of the two paths.

10. A computer-readable storage medium as in claim 9, wherein the step of changing the values of the keys of the extracted tree includes changing a prefix field of a root node of the extracted tree.