相邻模型+嵌套集模型

我之所以选择它，是因为我可以很容易地将新项目插入到树中（您只需要分支的id就可以向树中插入新项目），并且可以很快地查询它。

+-------------+----------------------+--------+-----+-----+
| category_id | name                 | parent | lft | rgt |
+-------------+----------------------+--------+-----+-----+
|           1 | ELECTRONICS          |   NULL |   1 |  20 |
|           2 | TELEVISIONS          |      1 |   2 |   9 |
|           3 | TUBE                 |      2 |   3 |   4 |
|           4 | LCD                  |      2 |   5 |   6 |
|           5 | PLASMA               |      2 |   7 |   8 |
|           6 | PORTABLE ELECTRONICS |      1 |  10 |  19 |
|           7 | MP3 PLAYERS          |      6 |  11 |  14 |
|           8 | FLASH                |      7 |  12 |  13 |
|           9 | CD PLAYERS           |      6 |  15 |  16 |
|          10 | 2 WAY RADIOS         |      6 |  17 |  18 |
+-------------+----------------------+--------+-----+-----+

每次需要任何父级的所有子级时，只需查询父列。如果需要任何父项的所有后代，请查询其lft介于父项的lft和rgt之间的项。如果需要任何节点到树根的所有父节点，可以查询lft低于节点lft且rgt大于节点rgt的项，并按父节点排序。

我需要使访问和查询树的速度比插入更快，这就是为什么我选择这个

唯一的问题是在插入新项目时修复左右列。我为它创建了一个存储过程，并在每次插入新项目时调用它，这在我的情况下很少见，但它确实很快。我从Joe Celko的书中得到了这个想法，存储过程以及我是如何想到它的，这在DBA SE中进行了解释https://dba.stackexchange.com/q/89051/41481

该设计尚未提及：

多个沿袭列

虽然它有局限性，但如果你能忍受的话，它非常简单和高效。特征：

列：每个沿袭级别一个，指的是根目录下的所有父级，低于当前项级别的级别设置为0（或NULL）层次结构的深度有固定的限制廉价的祖先、后代、水平廉价插入、删除、移动树叶昂贵的插入、删除和移动内部节点

下面是一个示例-鸟类的分类树，因此层次结构是类/目/科/属/种-种是最低级别，1行=1个分类单元（在叶节点的情况下对应于种）：

CREATE TABLE `taxons` (
  `TaxonId` smallint(6) NOT NULL default '0',
  `ClassId` smallint(6) default NULL,
  `OrderId` smallint(6) default NULL,
  `FamilyId` smallint(6) default NULL,
  `GenusId` smallint(6) default NULL,
  `Name` varchar(150) NOT NULL default ''
);

以及数据示例：

+---------+---------+---------+----------+---------+-------------------------------+
| TaxonId | ClassId | OrderId | FamilyId | GenusId | Name                          |
+---------+---------+---------+----------+---------+-------------------------------+
|     254 |       0 |       0 |        0 |       0 | Aves                          |
|     255 |     254 |       0 |        0 |       0 | Gaviiformes                   |
|     256 |     254 |     255 |        0 |       0 | Gaviidae                      |
|     257 |     254 |     255 |      256 |       0 | Gavia                         |
|     258 |     254 |     255 |      256 |     257 | Gavia stellata                |
|     259 |     254 |     255 |      256 |     257 | Gavia arctica                 |
|     260 |     254 |     255 |      256 |     257 | Gavia immer                   |
|     261 |     254 |     255 |      256 |     257 | Gavia adamsii                 |
|     262 |     254 |       0 |        0 |       0 | Podicipediformes              |
|     263 |     254 |     262 |        0 |       0 | Podicipedidae                 |
|     264 |     254 |     262 |      263 |       0 | Tachybaptus                   |

这是很好的，因为这样您可以以非常简单的方式完成所有需要的操作，只要内部类别不改变其在树中的级别。

这真是一个方桩、圆洞的问题。

如果关系数据库和SQL是您拥有或愿意使用的唯一工具，那么到目前为止发布的答案就足够了。然而，为什么不使用一个用于处理分层数据的工具呢？图形数据库是复杂分层数据的理想选择。

与图形数据库解决方案可以轻松解决相同问题相比，关系模型的效率低下以及将图形/分层模型映射到关系模型上的任何代码/查询解决方案的复杂性都是不值得的。

将BOM表视为常见的分层数据结构。

class Component extends Vertex {
    long assetId;
    long partNumber;
    long material;
    long amount;
};

class PartOf extends Edge {
};

class AdjacentTo extends Edge {
};

两个子程序集之间的最短路径：简单的图遍历算法。可接受的路径可以根据标准进行限定。

相似性：两个组件之间的相似程度是多少？对两个子树执行遍历，计算两个子树的交集和并集。相似百分比是交集除以并集。

传递闭包：遍历子树并总结感兴趣的字段，例如“一个子组件中有多少铝？”

是的，您可以使用SQL和关系数据库来解决这个问题。然而，如果你愿意使用适合工作的工具，还有更好的方法。

如果数据库支持数组，还可以将沿袭列或物化路径实现为父ID的数组。

特别是在Postgres中，您可以使用set运算符来查询层次结构，并使用GIN索引获得优异的性能。这使得在单个查询中查找父项、子项和深度变得非常简单。更新也很容易管理。

如果你好奇的话，我有一篇关于将数组用于实体化路径的完整文章。

我最喜欢的答案是这篇文章的第一句话所暗示的。使用“相邻列表”维护层次结构，并使用“嵌套集”查询层次结构。

到目前为止的问题是，从邻接列表到嵌套集的转换方法非常缓慢，因为大多数人使用称为“推堆栈”的极端RBAR方法进行转换，并且被认为是达到邻接列表维护简单和嵌套集性能卓越的涅盘所需的昂贵方法。因此，大多数人最终不得不满足于其中一个或另一个，尤其是如果节点数量超过，比如说，糟糕的100000个左右。使用push stack方法可能需要一整天的时间来完成MLM认为是一个小的百万节点层次结构的转换。

我想，我可以想出一种方法，以看似不可能的速度将相邻列表转换为嵌套集，从而给Celko带来一些竞争。下面是我的i5笔记本电脑上push堆栈方法的性能。

Duration for     1,000 Nodes = 00:00:00:870 
Duration for    10,000 Nodes = 00:01:01:783 (70 times slower instead of just 10)
Duration for   100,000 Nodes = 00:49:59:730 (3,446 times slower instead of just 100) 
Duration for 1,000,000 Nodes = 'Didn't even try this'

这里是新方法的持续时间（括号中有push堆栈方法）。

Duration for     1,000 Nodes = 00:00:00:053 (compared to 00:00:00:870)
Duration for    10,000 Nodes = 00:00:00:323 (compared to 00:01:01:783)
Duration for   100,000 Nodes = 00:00:03:867 (compared to 00:49:59:730)
Duration for 1,000,000 Nodes = 00:00:54:283 (compared to something like 2 days!!!)

是的，没错。在不到一分钟内转换了100万个节点，在4秒内转换了10万个节点。

您可以阅读新方法并从以下URL获取代码副本。http://www.sqlservercentral.com/articles/Hierarchy/94040/

我还使用类似的方法开发了一个“预聚合”层次结构。传销商和制作材料清单的人对这篇文章特别感兴趣。http://www.sqlservercentral.com/articles/T-SQL/94570/

如果你真的停下来看看这两篇文章，请跳到“加入讨论”链接，让我知道你的想法。

这是对你的问题的部分回答，但我希望仍然有用。

Microsoft SQL Server 2008实现了两个对管理分层数据非常有用的功能：

HierarchyId数据类型。公共表表达式，使用with关键字。

看看MSDN上Kent Tegels的“使用SQL Server 2008建立数据层次结构模型”。另请参阅我自己的问题：SQL Server 2008中的递归同表查询