高效的数据结构实现假文件系统

Question

我想要实现一个数据结构，它将保存目录的路径，某种程度上是假的文件系统。

输入：-我有一个包含路径的文本配置文件，如下所示

..。

C:/temp1

C:/temp1/indeTemp1

C:/temp2 2/

..。

我可能会在数据结构中存储大量的路径，并且我正在寻找极低的重试时间。

以下是我认为在这种情况下可能有用的数据结构：

B树

B+树

小波树

特瑞

和B-Trie

我不知道在这种情况下什么数据结构最有用。

我不熟悉be，也不知道互联网上有多少资源可以帮助我实现和理解一个，但我认为这可能是一个很好的实现选择，因为它将具有b树和trie的优点，如果我错了，请纠正我。

我想知道在实现这个问题时，什么是好的数据结构，如果您可以重定向一些资源来帮助我开始，那就太好了！

而且，出于好奇，将来如果我想把建议的数据结构扩展到成熟的文件系统，那么建议的数据结构是否足够好扩展呢？

每一个答案都很感激。

Answer 1

快速短答案

首先选择一个普通的树结构，然后再寻找类似的优化版本

长无聊扩展答案

首先使用规则的树结构。

我看到您似乎试图在每个节点元素中存储整个路径，这也是您的结构可能需要不必要的优化的原因之一。

注意:下面的示例是伪代码。这些都不是特定的编程语言，已完成的例子。

而不是拥有这样的东西：

public struct NodeStruct
{
  public string FullPath;
  public *NodeStruct Container;
  public List<*NodeStruct> Items;
}

int main()
{
  int ErrorCode = 0;

  *NodeStruct MyFileSystem =
    new nodeStruct;
  MyFileSystem->FullPath = "FileSystem";
  MyFileSystem->Container = null;

  *NodeStruct CDrive =         
    new nodeStruct;
  CDrive->FullPath = "C:\";
  CDrive->Container = MyFileSystem;

  *NodeStruct DDrive =         
    new nodeStruct;
  DDrive->FullPath = "D:\";
  DDrive->Container = MyFileSystem;

  *NodeStruct SomeFolder = null;
  *NodeStruct SomeFile = null;

  SomeFolder =
    new nodeStruct;
  SomeFolder->FullPath = "C:\Program Files";
  SomeFolder->Container = CFolder;

  SomeFolder =
    new nodeStruct;
  SomeFolder->FullPath = "C:\My Documents";
  SomeFolder->Container = CFolder;

  SomeFile =
    new nodeStruct;
  MyFileSystem->FullPath = "C:\My Documents\Homework1.doc";
  MyFileSystem->Container = SomeFolder;

  free MyFileSystem;

  return ErrorCode;
} // int main(...)

你可能想要这样的东西：

public struct NodeStruct
{
  string Identifier;

  public *NodeStruct Container;
  public List<*NodeStruct> Items;
}

string GetFullPath(*NodeStruct AFileSystemItem)
{
  string ErrorCode = "";

  // code to "traverse" a tree item or tree node
  // and get the full path

  return ErrorCode;
} // string GetFullPath(...)


int main()
{
  int ErrorCode = 0;

  *NodeStruct MyFileSystem =
    new nodeStruct;
  MyFileSystem->FullPath = "FileSystem";
  MyFileSystem->Container = null;

  *NodeStruct CDrive =         
    new nodeStruct;
  CDrive->FullPath = "C:";
  CDrive->Container = MyFileSystem;

  *NodeStruct DDrive =         
    new nodeStruct;
  DDrive->FullPath = "D:";
  DDrive->Container = MyFileSystem;

  *NodeStruct SomeFolder = null;
  *NodeStruct SomeFile = null;

  SomeFolder =
    new nodeStruct;
  SomeFolder->FullPath = "Program Files";
  SomeFolder->Container = CFolder;

  SomeFolder =
    new nodeStruct;
  SomeFolder->FullPath = "My Documents";
  SomeFolder->Container = CFolder;

  SomeFile =
    new nodeStruct;
  MyFileSystem->FullPath = "Homework1.doc";
  MyFileSystem->Container = SomeFolder;

  string AFullPath = GetFullPath(SomeFile);

  // "AFullPath" should have the "C:\My Documents\Homework1.doc" value

  free MyFileSystem;

  return ErrorCode;
} // int main(...)

您没有在问题中指定特定的编程语言。如果您使用的都不是命令式、程序性、功能性或面向对象的P.L.，这可能会帮助您建立一个库。

干杯。