在数据库中实现分层数据结构

我知道有两种方法：邻接列表和嵌套树。 据说由于许多查询，邻接列表在遍历中可能会变得很慢。 但我不知道这个现实的数字。 我正在制作的网站将有200页的区域。 是否遍历生成（例如）一个站点地图需要超过约0.3秒？

在LAMP堆栈上运行MySQL（innoDB）。

由于更简单的设计，如果可能的话，我宁愿实现邻接关系。

谢谢。

---

有更多的选择，而不仅仅是你提到的两个。 有：

邻接列表（几乎所有人使用的“parent_id”）

嵌套集

路径枚举

闭包表（又名邻接关系）

请参阅我的回答：“将一张平板分析成树的最有效/最优雅的方式是什么？”

或者几本书：

Joe Celko的“Trees and Hierarchies in SQL for Smarties”。

Vadim Tropashko的“SQL设计模式”。

---

文章管理MySQL中的分层数据详细介绍了这一点。

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

---

解析邻接列表的天真方法需要大量查询，而对于大型列表而言，可能需要大量时间才能构建内存。 作为参考，我指的天真方法可以概括为：选择所有没有父项的项目，然后对每个项目递归地获取它的子项。 这种方法需要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.
?>

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

吉姆

链接地址: http://www.djcxy.com/p/35033.html

上一篇: Implementing a hierarchical data structure in a database

下一篇: How to define a TVirtualStringTree with dynamic data structure