层次结构 - 概述 [英] Hierachical structures - an overview

问题描述

我有一个应用程序，我需要一个层次结构。据我所知，似乎有3种方式实现这个目的：


1.邻接列表。

优点 - 直观且相对简单

缺点 - 不容易通过标准SQL访问，需要重复查询

爬行或向下爬行结构。我会用Jet或MS SQL

服务器这样做，所以Oracle的Connect by已经出来了。


2.嵌套设置a la Joe Celko的BOM。

优点 - 通过标准SQL轻松访问结构


3.物化路径。

优点 - 通过standSQL轻松访问结构，层次很明显

并存储在一个字段中。

缺点 - 没有？ ''path''字段中的值不是_似乎是原子的，

这可能是一个值得商榷的问题。


1a。邻接列表+按照：
http：// fungus .teststation.com / ~jon / t ... eeHandling.htm

对此不确定。它声称向上提供了道路。它看起来像是b $ b只给了祖先，这不是一回事。


其他什么技巧？


其他任何优点和缺点？


你的，麦克麦克斯维尔

解决方案

Mike MacSween < MI ****************** @ btinternet.com>写在

新闻：3f *********************** @ news.aaisp.net.uk：
< blockquote class =post_quotes>我有一个应用程序我需要一个层次结构。据我所知，似乎有3种实现方式：

1.邻接列表。
优点 - 直观且相对简单
Cons - 不容易通过标准SQL访问，需要重复查询以爬行或向下爬行结构。我会在Jet或MS或SQL Server中执行此操作，因此Oracle的Connect by已经完成。

2.嵌套设置la Joe Celko的BOM。
优点 - 通过标准SQL轻松访问结构
缺点 - 当结构频繁变化时昂贵/复杂。

3.物化路径。
优点 - 易于使用通过standSQL访问结构，层次很明显并存储在一个字段中。
缺点 - 没有？ 路径字段中的值不会显示为原子，这可能是一个值得商榷的问题。

1a。邻接列表+按照：
http：// fungus .teststation.com / ~jon / t ... eeHandling.htm
对此不确定。它声称向上提供了道路。看起来它只是给了祖先，这不是一回事。

任何其他技巧？

任何其他优点和缺点？

你的，Mike MacSween

Google搜索Hierarchical Databases带来几千个b $ b（3860）个引用。前20个有点相似，但几乎没有任何帮助（对我而言）确定。通常它们被描述为

，如树，或目录结构，或信息管理

系统。过去的。一个指出了一个常见的问题：一个孩子比一个父母有更多的b $ b。


我认为你已经在另一个线程中描述了你的需求。但是

或许，在这一个中，你可以描述一个特定的问题或情况

有效处理需要特定的设计考虑。


我会觉得这很有帮助。


-

Lyle

（电子邮件参考 http://ffdba.com/contacts.htm ）

" Mike MacSween" < MI ****************** @ btinternet.com>在消息中写道

news：3f *********************** @ news.aaisp.net.uk ..。

我有一个应用程序，我需要一个层次结构。据我所知，似乎有3种方式实现这个
：

所有我能说的是不要让因素与高压力企业

等级
系统阻止你使用一种简单的方法，当应用于桌面应用程序时，它可以正常工作。可能有一个点递归

方法显然很慢，但是你会达到那个点吗？

" Mike MacSween" < MI ****************** @ btinternet.com>在消息新闻中写道：< 3f *********************** @ news.aaisp.net.uk> ...

我有一个应用程序，我需要一个层次结构。据我所知，似乎有3种方法可以实现这一点：


[...]

1a。邻接列表+按照：
http：// fungus .teststation.com / ~jon / t ... eeHandling.htm
对此不确定。它声称向上提供了道路。看起来它只是给了祖先，这不是一回事。


这有什么不同？你是否意味着与路径相比，

祖先的集合是无序的？在这种情况下，路径是从祖先集合中轻松创建的

。


也可以创建子树的总排序和

由此做，例如顺序遍历。然而，对于相对较小的子树，这变得不切实际，因为总排序是
prox O（n ^ 2）（其中n是
子树）


其他任何技术？

递归SQL。它由至少两个数据库支持，DB2（WITH）

和Oracle（CONNECT BY）。


+你不必改变数据的方式代表

（假设adj。，list）


- 性能（我已经尝试过很少的声明，但是这个

是我到目前为止的印象）


另外，IMO语法/语义有点奇怪（与其他

语言相比，我已经遇到了）


[...]


亲切的问候

/ Lennart

I have an app I need a hierachical structure for. There seem to be 3 ways of
implementing this, as far as I can see:

1. Adjacency list.
Pros - intuitive and relatively simple
Cons - not easily accesible via standard SQL, needs recusive queries to
crawl up or down the structure. I''ll be doing this in Jet or perhaps MS SQL
Server, so Oracle''s Connect by is out.

2. Nested Sets a la Joe Celko''s BOM.
Pros - easy to access the structure via standard SQL
Cons - expensive/complex when the structure changes frequently.

3. Materialised Paths.
Pros - easy to access the structure via standSQL, the hierachy is obvious
and stored in a single field.
Cons - None? The value in the ''path'' field doesn''t _appear_ to be atomic,
that might well be a debatable point.

1a. Adjacency list + as per:
http://fungus.teststation.com/~jon/t...eeHandling.htm
Not sure about this. It claims to give the path upwards. It looks like it
merely gives the ancestors, which isn''t the same thing.

Any other techniques?

Any other pros and cons?

Yours, Mike MacSween

解决方案

"Mike MacSween" <mi******************@btinternet.com> wrote in
news:3f***********************@news.aaisp.net.uk:

I have an app I need a hierachical structure for. There seem to be 3
ways of implementing this, as far as I can see:

1. Adjacency list.
Pros - intuitive and relatively simple
Cons - not easily accesible via standard SQL, needs recusive queries to
crawl up or down the structure. I''ll be doing this in Jet or perhaps MS
SQL Server, so Oracle''s Connect by is out.

2. Nested Sets a la Joe Celko''s BOM.
Pros - easy to access the structure via standard SQL
Cons - expensive/complex when the structure changes frequently.

3. Materialised Paths.
Pros - easy to access the structure via standSQL, the hierachy is
obvious and stored in a single field.
Cons - None? The value in the ''path'' field doesn''t _appear_ to be
atomic, that might well be a debatable point.

1a. Adjacency list + as per:
http://fungus.teststation.com/~jon/t...eeHandling.htm
Not sure about this. It claims to give the path upwards. It looks like
it merely gives the ancestors, which isn''t the same thing.

Any other techniques?

Any other pros and cons?

Yours, Mike MacSween

A Google Search for "Hierarchical Databases" brings up several thousand
(3860) references. The first twenty are somewhat similar, but scarcely
definitive in any helpful (to me) way. Generally they are described as
being like trees, or directory structures, or "Information Management
Systems" of the past. One points out a common problem: a child with more
than one parent.

I think you have been descriptive of your needs in another thread. But
perhaps, in this one, you could delineate a particular problem or situation
dealing effectively with which requires specific design consideration.

I would find this helpful.

--
Lyle
(for e-mail refer to http://ffdba.com/contacts.htm)

"Mike MacSween" <mi******************@btinternet.com> wrote in message
news:3f***********************@news.aaisp.net.uk.. .

I have an app I need a hierachical structure for. There seem to be 3 ways of implementing this, as far as I can see:

All I can say is don''t let factors associated with high stress enterprise
level
systems dissuade you from using a simple method that works just fine when
applied to a desktop application. There may be a point where recursive
methods are noticeably slow, but will you ever reach that point?

"Mike MacSween" <mi******************@btinternet.com> wrote in message news:<3f***********************@news.aaisp.net.uk> ...

I have an app I need a hierachical structure for. There seem to be 3 ways of
implementing this, as far as I can see:

[...]

1a. Adjacency list + as per:
http://fungus.teststation.com/~jon/t...eeHandling.htm
Not sure about this. It claims to give the path upwards. It looks like it
merely gives the ancestors, which isn''t the same thing.

In what way does this differ? Are you meaning that the set of
ancestors is unordered, compared to the path? In that case the path is
easy to create from the ancestor set.

It is also possible to create a total ordering of a subtree and
thereby do, for example an inorder traversal. However, this becomes
impractical for relatively small subtrees since the total ordering is
prox O(n^2) (where n is the cardinality of the ancestor relation for
the subtree)

Any other techniques?

Recursive SQL. It is supported by atleast two databases, DB2 (WITH)
and Oracle (CONNECT BY).

+ You dont have to change anything in the way data is represented
(assuming adj. ,list)

- Performance (I have tried it far to little to claim this, but this
is my impression so far)

Also, IMO the syntax/semantics is a bit weird (compared to other
languages, I''ve encountered)

[...]

Kind regards
/Lennart

这篇关于层次结构 - 概述的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！