sql - 在关系数据库中存储分层数据有哪些选项?





database hierarchical-data (7)


邻接模型+嵌套集模型

我为此付出了努力,因为我可以很容易地将新项目插入树中(您只需要一个分支的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列。
  • 如果您需要任何父母的所有后代,则查询其父母之间的lftrgt之间的lft项目。
  • 如果需要任何节点的所有父节点直到树的根节点,则查询比节点的lftrgtlft并且大于节点的rgt并按parent节点进行排序的项目。

我需要比插入更快地访问和查询树,这就是我选择它的原因

唯一的问题是在插入新项目时修复right列。 那么我为它创建了一个存储过程,并在每次插入一个在我的例子中很少见的新项目时调用它,但它非常快。 我从Joe Celko的书中获得了这个想法,以及存储过程以及我如何使用它的原因在DBA SE中解释https://dba.stackexchange.com/q/89051/41481

良好的概述

一般而言,您正在快速读取时间(例如,嵌套集)或快速写入时间(邻接列表)之间做出决定。 通常情况下,您最终会得到最适合您需求的选项组合。 以下内容提供了一些深入的解读:

选项

我知道的和一般特征:

  1. 邻接表
    • 列:ID,ParentID
    • 易于实施。
    • 便宜的节点移动,插入和删除。
    • 昂贵的找到关卡(可以存储为计算列),祖先和后代(桥表结合等级列可以解决),路径(Lineage Column可以解决)。
    • 在支持它们遍历的那些数据库中使用公用表表达式
  2. 嵌套集合 (又名修改先序树遍历)
    • Joe Celko在众多文章中以及他的书中的Trees and Hierarchies in SQL for Smarties中得到了推广
    • 列:左,右
    • 便宜的水平,血统,后代
    • 易失性编码 - 移动,插入,删除更昂贵。
    • 需要特定的排序顺序(例如创建)。 因此,以不同顺序排序所有后代需要额外的工作。
  3. 嵌套间隔
    • 像嵌套集合,但与真正/浮点/小数,使编码不挥发(便宜的移动/插入/删除)
    • 必须处理真实/浮点/小数表示问题
    • 一个更复杂的矩阵编码变体增加了祖先编码的好处,就像物化路径的“自由”
  4. 桥接表 (又名Closure Table :关于如何使用触发器维护这种方法的一些好主意)
    • 专栏:祖先,后代
    • 与它描述的表格分开。
    • 可以在一个以上的层次结构中包含一些节点。
    • 廉价的祖先和后代(尽管不是以什么顺序)
    • 对于层次结构的完整知识需要与另一个选项相结合。
  5. 平的表
    • 邻接列表的修改,为每条记录添加级别和排名(例如排序)列。
    • 昂贵的移动和删除
    • 廉价的祖先和后代
    • 好用:线程讨论 - 论坛/博客评论
  6. 沿袭列 (又名物化路径 ,路径枚举)
    • 专栏:谱系(例如/父母/孩子/孙子/等等)
    • 限制层次结构的深度。
    • 后代便宜(例如LEFT(lineage, #) = '/enumerated/path'
    • 祖先棘手(数据库特定查询)
  7. 多谱系列
    • 列:每个血统级别的一个,指的是所有的父母直到根,从该项目的级别下降的级别都设置为NULL
    • 限制层次结构的深度
    • 廉价的祖先,后代,水平
    • 廉价的插入,删除,移动的叶子
    • 昂贵的插入,删除,移动内部节点

数据库特定注释

MySQL的

神谕

PostgreSQL的

SQL Server

  • 总结
  • 2008提供HierarchyId数据类型似乎有助于使用Lineage Column方法并扩展可表示的深度。



我正在使用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;
$$;

闭包表用3列定义 - ANCESTOR_ID,DESCENDANT_ID,深度。 有可能(甚至建议)为ANCESTOR和DESCENDANT存储具有相同值的记录,深度值为零。 这将简化对层次结构进行检索的查询。 他们确实很简单:

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



这是你的问题的一个非常部分的答案,但我希望仍然有用。

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

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




如果您的数据库支持数组,则还可以将父系列或物化路径实现为父数据标识的数组。

特别是使用Postgres,您可以使用集合运算符来查询层次结构,并使用GIN索引获得出色的性能。 这使得在单个查询中找到父母,孩子和深度非常简单。 更新也相当易于管理。

如果你好奇,我已经写了一些使用物理路径的数组




我最喜欢的答案是这个主题中的第一句话提示。 使用邻接列表来维护层次结构并使用嵌套集来查询层次结构。

迄今为止的问题是,从Adjacecy List到Nested Sets的覆盖方法一直非常缓慢,因为大多数人使用称为“Push Stack”的极端RBAR方法进行转换,并且被认为是成本昂贵的方式通过邻接列表以及Nested Sets的卓越性能来达到Nirvana的简单维护。 结果,大多数人最终不得不为其中一个或另一个而定居,特别是如果不止有100,000个左右的节点等等。 使用推式堆栈方法可能需要一整天时间才能对MLM人员认为是小型百万节点层次结构进行转换。

我想我会给Celko一点点竞争力,想出一种将邻接列表转换成嵌套集合的方法,其速度看起来不可能。 以下是我的i5笔记本电脑上的push stack方法的性能。

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万个节点,在4秒内转换100,000个节点。

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

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

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




此设计尚未提及:

多谱系列

虽然它有局限性,但如果你能承受它,它非常简单而且非常高效。 特征:

  • 列:每个血统级别的一个,指的是所有的父母直到根,当前项目的水平以下的级别被设置为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                   |

这非常棒,因为只要内部类别不改变它们在树中的级别,就可以非常简单的方式完成所有需要的操作。




您可以轻松地将经纬度十进制数存储在无符号整数字段中,而不是将它们拆分为整数和小数部分,并按照以下某些建议使用以下转换算法单独存储:

作为一个存储的mysql函数:

CREATE DEFINER=`r`@`l` FUNCTION `PositionSmallToFloat`(s INT) 
RETURNS decimal(10,7)
DETERMINISTIC
RETURN if( ((s > 0) && (s >> 31)) , (-(0x7FFFFFFF - 
(s & 0x7FFFFFFF))) / 600000, s / 600000)

然后回来

CREATE DEFINER=`r`@`l` FUNCTION `PositionFloatToSmall`(s DECIMAL(10,7)) 
RETURNS int(10)
DETERMINISTIC
RETURN s * 600000

这需要存储在一个unsigned int(10)中 ,这在mysql中以及在无类型的sqlite中都可以工作。

通过经验,我发现这种方法非常快速,如果你只需要存储坐标并检索那些数据就可以了。

在PHP这2个功能看起来像

function LatitudeSmallToFloat($LatitudeSmall){
   if(($LatitudeSmall>0)&&($LatitudeSmall>>31)) 
     $LatitudeSmall=-(0x7FFFFFFF-($LatitudeSmall&0x7FFFFFFF))-1;
   return (float)$LatitudeSmall/(float)600000;
}

又回来了:

function LatitudeFloatToSmall($LatitudeFloat){
   $Latitude=round((float)$LatitudeFloat*(float)600000);
   if($Latitude<0) $Latitude+=0xFFFFFFFF;
   return $Latitude;
}

这也有一些额外的好处,例如用整数创建例如memcached唯一键。 (例如:缓存地理编码结果)。 希望这会增加讨论的价值。

另一个应用程序可能是当你没有GIS扩展,并且只想保留几百万个经纬度对时,你可以在mysql的这些字段上使用分区,以从它们是整数的事实中受益:

Create Table: CREATE TABLE `Locations` (
  `lat` int(10) unsigned NOT NULL,
  `lon` int(10) unsigned NOT NULL,
  `location` text,
  PRIMARY KEY (`lat`,`lon`) USING BTREE,
  KEY `index_location` (`locationText`(30))
) ENGINE=InnoDB DEFAULT CHARSET=utf8
/*!50100 PARTITION BY KEY ()
PARTITIONS 100 */




sql database hierarchical-data