12

我知道有两种方法：邻接表和嵌套树。据说由于大量查询，邻接表在遍历时会变得很慢。但我不知道任何现实的数字。我正在制作的网站将有 200 页左右。生成（例如）站点地图的遍历是否会花费超过 0.3 秒的时间？

在带有 LAMP 堆栈的 MySQL (innoDB) 上运行。

如果可能的话，我更喜欢实现邻接，因为设计更简单。

谢谢。

4

6 回答 6

16

除了你提到的两个，还有更多的选择。有：

  • 邻接表（几乎每个人都使用的“parent_id”）
  • 嵌套集
  • 路径枚举
  • 闭包表（又名邻接关系）

请参阅我对“将平面表解析为树的最有效/优雅的方法是什么？ ” 的回答。

或者几本书：

于 2009-02-13T04:33:39.313 回答
4

在 MySQL 中管理分层数据一文对此进行了详细介绍。

我会推荐“嵌套集”技术，因为它允许您在一个查询中获取整棵树（及其子树）。基本上读取很便宜，但写入很昂贵，因为必须重新平衡整个树。但如果你有 99% 的阅读量，那么它是完全合理的。

于 2009-02-13T04:02:09.620 回答
3

解析邻接列表的简单方法需要大量查询，并且对于大型列表可能需要大量时间来构建内存。作为参考，我所指的幼稚方法可以概括为：选择所有没有父项的项目，然后为每个项目递归地获取它的子项。这种方法需要 n+1 个数据库查询。

我使用以下方法来构建具有 1 个查询的邻接列表。从数据库中选择所有项目。将所有项目传输到由其键索引的数组中。遍历数组并将父对象的引用分配给它的每个子对象。再次遍历数组并移除所有子对象，只留下根级对象。

由于您提到了 LAMP 堆栈，因此执行此操作的 PHP 代码大致如下：

<?php
// Assumes $src is the array if items from the database.
$tmp = array();

// Traverse the array and index it by id, ensuing each item has an empty array of children.
foreach ($src as $item) {
  $item['children'] = array();
  $tmp[$item['id']] = $item;
}

// Now traverse the array a second time and link children to their parents.
foreach ($tmp as $id => $item) {
  if ($item['parent_id'] != 0 || $item['parent_id'] !== NULL) {
    $tmp[$item['parent_id']]['children'][$id] = &$tmp[$id];
  }
}

// Finally create an array with just root level items.
$tree = array();
foreach ($tmp as $id => $item) {
  if ($item['parent_id'] == 0 || $item['parent_id'] === NULL) {
    $tree[$id] = $item;
  }
}

// $tree now contains our adjacency list in tree form.
?>

请注意，此代码旨在说明从单个数据库查询构建邻接列表的技术。它可能会针对更少的内存消耗等进行优化。它还没有经过测试。

吉姆，

于 2009-02-13T05:04:05.150 回答
2

这里有几个问题可能会对您有所帮助：

SQL 如何存储和导航层次结构

哪个是我导航的最佳数据库架构

于 2009-02-13T03:54:33.663 回答
2

我认为另一种方法称为“嵌套集”，而不是“嵌套树”。

无论如何，站点地图的一个好处是您可能知道它的最大深度。我认为邻接模型的问题在于相应的 SQL 一次只在一个级别上工作，所以如果你有“n”个级别，那么你需要一个循环“n”个 SQL 语句......但我认为（I' m不确定）如果您提前知道最大'n'，那么您可以编写相应的固定数量的多级SQL。

0.3 秒对我来说听起来像是一个很长的时间来计算 200 页，所以这可能没关系。

站点地图也不会经常更新；因此，即使从 SQL 中检索确实需要很长时间，您也可以将检索/计算的树缓存在 RAM 中。

或者，不用担心构建树的 SQL，您可以尽可能简单地存储它（作为邻接列表），从数据库中检索它作为一组简单的行，然后在 RAM 中构建树（使用循环您的高级编程语言）而不是在 SQL 中使用循环来使用 SQL 语句构建树。

于 2009-02-13T03:56:59.243 回答
2

为了完整起见：Oracle 有START_WITHandCONNECT_BY运算符：请参阅此Hierarchical Queries文档。

于 2009-02-13T04:19:03.480 回答