在关系数据库中存储层次数据的选项是什么？

Question

continue

Answer 1

我最喜欢的答案是该线程中的第一句话是什么。使用邻接列表来维护层次结构并使用嵌套集来查询层次结构。

到目前为止，问题一直是，从邻接列表到嵌套集的封面方法一直很慢，因为大多数人都使用被称为“ push stack”的极端RBAR方法来进行转换，并且被认为是昂贵的方式通过邻接列表和嵌套集的出色表现，达到维护简单性的必要性。结果，大多数人最终不得不安顿下一个或另一个人，尤其是如果有一个糟糕的节点左右。使用推动堆栈方法可能需要一整天的时间来进行有关MLM'S认为是小型节点层次结构的转换。

我以为我会通过提出一种将邻接列表转换为嵌套集的方法，以似乎是不可能的。这是我的i5笔记本电脑上推动堆栈方法的性能。

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'

这是新方法的持续时间（使用括号中的推动堆栈方法）。

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万个节点在不到一分钟的时间内转换了100,000个节点，在4秒钟内。

您可以阅读有关新方法的信息，并在以下URL中获取代码的副本。
http://www.sqlservercentral.com/articles/articles/hierarchy/hierarchy/94040/

使用类似方法汇总的“层次结构。 MLM'ER和制作材料清单的人将对本文特别感兴趣。

http://www.sqlservercentral.com/articles/articles/t-sql/94570/ 停下来看看这两篇文章，跳入“加入讨论”链接，让我知道您的想法。

Answer 2

我选择的邻接模型 +嵌套集型模型

是因为我可以轻松地将新项目插入树（您只需要一个分支的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 |
+-------------+----------------------+--------+-----+-----+

• 每次您需要任何父母的孩子时，您只需查询 parent 列即可。
• 如果您需要所有父母的所有后代，则您查询对 lft> lft 和 rgt of parent的项目的 lft 。
• 如果您需要所有节点的所有父母，请询问其 lft 的项目，低于节点的 lft 和 rgt 大于节点的 rgt ，然后按 parent 对。

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

唯一的问题是修复左和 right 列插入新项目时。好吧，我为此创建了一个存储过程，并每次插入一个新项目时都会称其为罕见，但这确实很快。
我从乔·塞尔科（Joe Celko）的书以及存储程序以及如何提出的想法中得到了这个想法。
https://dba.stackexchange.com/q/q/q/89051/41481

尽管此解决方案可以快速搜索来定位后代，由于其在这些操作中的性能缓慢而需要频繁插入或删除的大型数据集并不理想。因此，它最适合不经常造成的桌子。

Answer 3

该设计尚未提及：

多个谱系列

尽管有限制，如果您可以忍受，它非常简单，非常非常简单，非常非常非常高效的。功能：

• 列：每个谱系级别一个，指的是所有父母，直到根部，低于当前项目的级别的级别设置为0（或null），
• 对层次结构的深度如何为
• 便宜的祖先有固定的限制，后代，水平
• 廉价插入，删除，叶子的移动
• 昂贵的插入物，删除，内部节点的移动

在这里遵循一个例子 - 鸟类的分类树，因此层次结构是类/订单/订单/家庭/族/属/物种 - 物种是最低水平 单元（在叶子节点的情况下对应于物种）

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 ''
);

，1行= 1分类

+---------+---------+---------+----------+---------+-------------------------------+
| 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                   |

。类别不会改变树上的水平。

Answer 4

这是您问题的部分答案，但我希望仍然有用。

Microsoft SQL Server 2008实现了两个对于管理层次数据极为有用的功能：

• 数据类型。
• 通用表表达式，使用带有关键字。

看看 kent tegels在MSDN上的开始。另请参阅我自己的问题： sql Server 2008中的递归same-table查询

Answer 5

如果您的数据库支持数组，则您还可以将谱系列或物有的路径作为父ID数组来实现。

特别是在Postgres中，您可以使用集合操作员查询层次结构，并通过杜松子酒指数获得出色的性能。这使得在一个查询中找到父母，孩子和深度相当微不足道。更新也非常易于管理。

我有完整的文字使用“ nofollow noreferrer”>用于实现路径的阵列如果您很好奇。

Answer 6

这确实是一个方形的圆孔问题。

如果关系数据库和SQL是您唯一或愿意使用的锤子，那么到目前为止发布的答案是足够的。但是，为什么不使用旨在处理层次数据的工具呢？ Graph Database 是复杂的层次数据的理想选择。

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

将材料清单视为常见的分层数据结构。

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

class PartOf extends Edge {
};

class AdjacentTo extends Edge {
};

两个子组件之间的最短路径：简单的图形遍历算法。可接受的路径可以根据标准获得资格。

相似性：两个组件之间的相似程度是多少？在计算两个子树的交点和结合的两个子树上进行遍历。相似的百分比是交叉路口除以联盟。

传递闭合：走下子树并总结了感兴趣的领域，例如“子组装中有多少铝？”

是的，您可以使用SQL和关系数据库解决问题。但是，如果您愿意使用合适的工具来工作，可以采用更好的方法。

Answer 7

我正在为层次结构使用PostgreSQL带有封闭表。
我为整个数据库都有一个通用存储的过程：

CREATE FUNCTION nomen_tree() RETURNS trigger
    LANGUAGE plpgsql
    AS $_$
DECLARE
  old_parent INTEGER;
  new_parent INTEGER;
  id_nom INTEGER;
  txt_name TEXT;
BEGIN
-- TG_ARGV[0] = name of table with entities with PARENT-CHILD relationships (TBL_ORIG)
-- TG_ARGV[1] = name of helper table with ANCESTOR, CHILD, DEPTH information (TBL_TREE)
-- TG_ARGV[2] = name of the field in TBL_ORIG which is used for the PARENT-CHILD relationship (FLD_PARENT)
    IF TG_OP = 'INSERT' THEN
    EXECUTE 'INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) 
        SELECT $1.id,$1.id,0 UNION ALL
      SELECT $1.id,ancestor_id,depth+1 FROM ' || TG_ARGV[1] || ' WHERE child_id=$1.' || TG_ARGV[2] USING NEW;
    ELSE                                                           
    -- EXECUTE does not support conditional statements inside
    EXECUTE 'SELECT $1.' || TG_ARGV[2] || ',$2.' || TG_ARGV[2] INTO old_parent,new_parent USING OLD,NEW;
    IF COALESCE(old_parent,0) <> COALESCE(new_parent,0) THEN
      EXECUTE '
      -- prevent cycles in the tree
      UPDATE ' || TG_ARGV[0] || ' SET ' || TG_ARGV[2] || ' = $1.' || TG_ARGV[2]
        || ' WHERE id=$2.' || TG_ARGV[2] || ' AND EXISTS(SELECT 1 FROM '
        || TG_ARGV[1] || ' WHERE child_id=$2.' || TG_ARGV[2] || ' AND ancestor_id=$2.id);
      -- first remove edges between all old parents of node and its descendants
      DELETE FROM ' || TG_ARGV[1] || ' WHERE child_id IN
        (SELECT child_id FROM ' || TG_ARGV[1] || ' WHERE ancestor_id = $1.id)
        AND ancestor_id IN
        (SELECT ancestor_id FROM ' || TG_ARGV[1] || ' WHERE child_id = $1.id AND ancestor_id <> $1.id);
      -- then add edges for all new parents ...
      INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) 
        SELECT child_id,ancestor_id,d_c+d_a FROM
        (SELECT child_id,depth AS d_c FROM ' || TG_ARGV[1] || ' WHERE ancestor_id=$2.id) AS child
        CROSS JOIN
        (SELECT ancestor_id,depth+1 AS d_a FROM ' || TG_ARGV[1] || ' WHERE child_id=$2.' 
        || TG_ARGV[2] || ') AS parent;' USING OLD, NEW;
    END IF;
  END IF;
  RETURN NULL;
END;
$_$;

然后，对于每个具有层次结构的表，我创建了一个触发器，

CREATE TRIGGER nomenclature_tree_tr AFTER INSERT OR UPDATE ON nomenclature FOR EACH ROW EXECUTE PROCEDURE nomen_tree('my_db.nomenclature', 'my_db.nom_helper', 'parent_id');

用于从现有层次结构中填充封闭

CREATE FUNCTION rebuild_tree(tbl_base text, tbl_closure text, fld_parent text) RETURNS void
    LANGUAGE plpgsql
    AS $
BEGIN
    EXECUTE 'TRUNCATE ' || tbl_closure || ';
    INSERT INTO ' || tbl_closure || ' (child_id,ancestor_id,depth) 
        WITH RECURSIVE tree AS
      (
        SELECT id AS child_id,id AS ancestor_id,0 AS depth FROM ' || tbl_base || '
        UNION ALL 
        SELECT t.id,ancestor_id,depth+1 FROM ' || tbl_base || ' AS t
        JOIN tree ON child_id = ' || fld_parent || '
      )
      SELECT * FROM tree;';
END;
$;

表， 深度。有可能（甚至我建议）存储具有相同价值的祖先和后代的记录，而深度为零的值。这将简化检索层次结构的查询。它们确实非常简单：

-- get all descendants
SELECT tbl_orig.*,depth FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth <> 0;
-- get only direct descendants
SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth = 1;
-- get all ancestors
SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON ancestor_id = tbl_orig.id WHERE descendant_id = XXX AND depth <> 0;
-- find the deepest level of children
SELECT MAX(depth) FROM tbl_closure WHERE ancestor_id = XXX;

Answer 8

MySQL现在支持JSON数据类型：

https> https：//dev.mysql。 com/doc/refman/8.0/en/json.html