算法：分层数据——这个方法叫什么？

Question

我知道用于描述关系数据库中分层数据的几种模型：

self-reference parent（每条记录都有一个外键指向同一个table的主键，不知道这个叫什么）
邻接列表
嵌套集

我想到还有另一种描述层次结构的方法，它与这些模型有一组不同的缺点（一件事的高度冗余）——那就是保持影子 table其中树中每个节点的所有祖先以及该节点与其祖先相隔的世代数，例如

 node         ancestor          generations
 ----         --------          -----------
 leaf         parent            1
 leaf         grandparent       2
 leaf         great-grandparent 3
 leaf         root              4
 parent       grandparent       1
 parent       great-grandparent 2
 parent       root              3
 grandparent  great-grandparent 1
 grandparent  root              2
 great-grandparent  root        1

描述层次结构....

 root
  |
  +- great-grandparent
      |
      +- grandparent
          |
          +- parent
              |
              +- leaf

我真的怀疑我是否发明了一些新东西 - 但由于搜索引擎返回的噪音，我很难在网上找到对此的描述。

这个有名字了吗？

Answer 1

This presentation (starting page 40) by Bill Karwin 调用了一个与您描述为 闭包 table 非常相似的结构。您的结构中的 generations 列也被引入为 length。

Whosebug 实际上有一个 tag 这个数据结构。标签信息页面中最重要的参考链接之一引用了此答案中链接的演示文稿。

我不确定将此模式称为闭包是否有特定的技术原因 table。 Wikipedia article on transitive closures 可能会有所启发：

In mathematics, the transitive closure of a binary relation R on a set X is the smallest relation on X that contains R and is transitive.

For example, if X is a set of airports and xRy means "there is a direct flight from airport x to airport y" (for x and y in X), then the transitive closure of R on X is the relation R+ such that x R+ y means "it is possible to fly from x to y in one or more flights". Informally, the transitive closure gives you the set of all places you can get to from any starting place.

算法：分层数据——这个方法叫什么？

Algorthims: hierarchical data - what is this method called?

algorithm

relational-database