模拟文件系统应该使用哪种数据结构？

Question

标题可能有点奇怪，但这可能是因为我甚至不知道我是否在问正确的问题。

因此，我试图构建的基本上是一个“面包屑式”的分类系统（类似于文件目录），其中每个节点都有一个父节点（除了根节点），并且每个节点可以包含数据或另一个节点。这将用于组织数据库中的电子邮件地址。我现在有一个系统，您可以创建一个“组”并将电子邮件地址添加到该组中，但很好将其添加到组织系统中。

这（在我的脑海中）是以树形格式呈现的，但我不知道是哪种树。

我遇到的问题是使用MySQL构建它。在内存中遍历树很容易，但在数据库上，它有点棘手。

树的图像：http://j.imagehost.org/0917/asdf.png 从企业中选择*：Tim的五金店，7-11，Kwik-E-Mart，Cub Foods，Bob的杂货店，CONGLOM-O

从杂货店中选择*：Cub Foods，Bob的杂货店，CONGLOM-O

从大型杂货店中选择*：CONGLOM-O

从教堂中选择*：圣彼得教堂，圣约翰教堂

我认为这应该足够的信息，以便我准确地描述我的目标。

- MALON

---

你确定你只需要一棵树吗？似乎有些节点可以出现在多个分支中（这也是我设想的分类方式——一个对象可能有多个标签）。例如，如果你在“企业”类别下有另一个类别叫“大企业”，那么CONGLOM-O也可能出现在那里，对吧？ - Tom H

Answer 1

好的，有几种模式可以使用。哪一种是正确的取决于您的需求。

您需要选择一个节点及其所有子节点吗？如果是这样，那么嵌套集模型（向下滚动到标题）可能更适合您。表格应如下所示：

| Name     | Left | Right |
| Emails   | 1    | 12    |
| Business | 2    | 7     |
| Tim's    | 3    | 4     |
| 7-11     | 5    | 6     |
| Churches | 8    | 11    |
| St. Pete | 9    | 10    |

那么，要查找节点下面的任何内容，只需执行以下操作：

SELECT name FROM nodes WHERE Left > *yourleftnode* AND Right < *yourrightnode*

要查找节点上方的所有内容：

SELECT name FROM nodes WHERE Left < *yourleftnode* AND Right > *yourrightnode*

如果您只想查询特定级别，您可以使用邻接列表模型（向下滚动到标题）：

| Id | Name     | Parent_Id |
| 1  | Email    | null      |
| 2  | Business | 1         |
| 3  | Tim's    | 2         |

为了使所有内容在同一级别上，只需执行以下操作：

SELECT name FROM nodes WHERE parent_id = *yourparentnode*

当然，没有任何阻止您采用混合方法来查询您需要的查询。

| Id | Name     | Parent_Id | Left | Right | Path             |
| 1  | Email    | null      | 1    | 6     | /                |
| 2  | Business | 1         | 2    | 5     | /Email/          |
| 3  | Tim's    | 2         | 3    | 4     | /Email/Business/ |

实际上，这只是关于您的需求问题...

- ircmaxell

---

是的！嵌套集模型正是我正在寻找的！谢谢你！ - MALON

Answer 2

最简单的方法是这样的：

Group
  - GroupID (PK)
  - ParentGroupID
  - GroupName

People
  - PersonID (PK)
  - EmailAddress
  - FirstName
  - LastName

GroupMembership
  - GroupID (PK)
  - PersonID (PK)

这样可以建立一个结构，使您可以拥有具有父组的组和可以成为组成员（或多个组）的人。如果一个人只能是一个组的成员，则删除 GroupMembership 表，并将 GroupID 放在 People 表上。

对这个结构进行复杂查询可能会变得困难。还有其他不太直观的建模方式，使查询更容易（但通常使更新更困难）。如果组的数量很少，处理针对此的查询最简单的方法通常是将整个组树加载到内存中，缓存它，并使用它来构建您的查询。

- Eric Petroelje

Answer 3

每当我看到关于建模树和层次结构的问题时，我的建议是获取Joe Celko关于此主题的书。他提出了在关系型数据库中建模它们的各种方法，其中一些相当有想象力，并且他为每个模式给出了优缺点。

- Tom H

Answer 4

创建一个对象 Group，该对象具有名称、许多电子邮件地址和一个可为空的父对象。

- mcandre