0

我知道并在过去使用过两种基本树结构的方法：邻接列表和嵌套集。我了解这些方法的几个优点和缺点 - 例如，邻接列表更新速度快但查询速度慢，嵌套集则相反（更新速度慢，查询速度快）。

但是，我需要能够存储更复杂的树状结构。描述这一点的最好方法是使用人类家庭关系。我的第一个想法是每个元素都可以有一个“祖先”树和一个“后代”树。但是，这种方法会有很大的冗余，因为使用下面的示例，Cameron 和 Kelly 都将共享 Bob 的所有祖先树（并且更新将更加耗时，因为对树的插入实际上必须插入多棵树）。我的第二个想法是包含树引用。例如，假设 Alice 有她自己的祖先树。来自 Cameron 的祖先树的 (4,5) 元素和来自 Kelly 的祖先树的 (2,3) 元素都将简单地引用 Alice 的祖先树。第二种方法需要更少的数据存储，将体验更快的更新（仅更新单个树而不是多个树）并且将保留查询大型树结构的速度优势（尽管查询这种自引用嵌套集的 SQL比较复杂）。然而，第二种方法的一个缺点是数据变得“碎片化”（很像硬盘驱动器上的 inode）。

 A = Alice                                  
 B = Bob                                    
 C = Cameron                                
 J = John                                   
 K = Kelly                                  

+------------------------------------------+

  +-----------+            +-------------+  
  |(2) Bob (3)|            |(4) Alice (5)|  
  +-----+-----+            +------+------+  
        |                         |         
        |                         |         
        |                         |         
        |                         |         
        |    +---------------+    |         
        +----+(1) Cameron (6)+----+         
             +---------------+              

  +-------------+            +------------+ 
  |(2) Alice (3)|            |(4) John (5)| 
  +-----+-------+            +-------+----+ 
        |                            |      
        |                            |      
        |                            |      
        |                            |      
        |      +-------------+       |      
        +------+(1) Kelly (6)+-------+      
               +-------------+              

+------------------------------------------+

           +-------------+                  
           |(1) Alice (6)+----------+       
           +-+-----------+          |       
             |                      |       
             |                      |       
             |                      |       
   +---------+-----+        +-------+-----+ 
   |(2) Cameron (3)|        |(4) Kelly (5)| 
   +---------------+        +-------------+

对于第二种方法，我正在可视化多个嵌套集合，它们彼此堆叠在一起，某些节点沿着 z 索引“画一条线”到另一个平面上的节点。

请注意，以上只是一个示例——我实际上并不是在存储人际关系，而是在存储复杂的树状数据。存储如此复杂的层次结构的原因有很多，所以我会让你尽情想象！

问题：在 SQL 数据库中存储复杂的自引用树结构的性能方面（更新和选择）最有效的方式是什么？我特别指的是 PostgreSQL，但如果你有替代品（甚至是 SQL 本身），我也愿意听到。

4

1 回答 1

0

在 Oracle 中，这可以通过使用start with .. connect by. 也称为分层查询。

例如：

select * 
 from <table_name> 
 start with <parent_column_name> is null
 connect by prior <child_column_name> = <parent_column_name>;
于 2014-06-26T06:49:45.807 回答