您可以使用hashmap模拟任何其他数据结构，因此这并不是一个可怕的限制。从上到下扫描，为数据库的每一行创建hashmap，为每一列创建一个条目。将这些hashmap添加到“master”hashmap中，并以id为键。如果任何节点都有一个尚未见过的“父”节点，请在主hashmap中为它创建一个占位符条目，并在看到实际节点时填充它。

要将其打印出来，只需对数据进行简单的深度优先遍历，并在此过程中跟踪缩进级别。您可以通过为每一行保留一个“子”条目，并在扫描数据时填充它来简化这一点。

至于是否有“更好”的方法在数据库中存储树，这取决于您将如何使用数据。我曾经见过一些系统，它们具有已知的最大深度，但却为层次结构中的每个级别使用不同的表。如果树中的级别并不完全相同(顶级类别与叶类别不同)，那么这就很有意义了。

要扩展Bill的SQL解决方案，基本上可以使用平面数组来实现相同的功能。此外，如果你的字符串都有相同的长度，你的最大子代数是已知的(比如在一个二叉树中)，你可以使用一个单一的字符串(字符数组)。如果你有任意数量的孩子，事情就会变得复杂一些……我必须检查我的旧笔记，看看能做些什么。

然后，牺牲一点内存，特别是如果你的树是稀疏的和/或不平衡的，你可以，通过一些索引数学，通过存储你的树随机访问所有的字符串，宽度优先在数组中，就像这样(对于二叉树):

String[] nodeArray = [L0root, L1child1, L1child2, L2Child1, L2Child2, L2Child3, L2Child4] ...

你知道弦的长度，你知道 我现在在工作，所以不能花太多时间在上面，但有兴趣，我可以获取一些代码来做到这一点。 我们过去用它来搜索由DNA密码子组成的二叉树，一个构建树的过程，然后我们将其平铺以搜索文本模式，当找到时，尽管索引数学(从上面反向)，我们将节点找回…非常快速和有效，我们的树很少有空节点，但我们可以在一瞬间搜索千兆字节的数据。

这写得很快，既不漂亮也不高效(加上它自动装箱很多，在int和Integer之间转换很烦人!)，但它是有效的。

这可能打破了规则，因为我创建自己的对象，但嘿，我这样做是为了从实际工作中转移注意力:)

这还假定在开始构建Nodes之前，resultSet/table已完全读入某种结构，如果您有数十万行，这不是最佳解决方案。

public class Node {

    private Node parent = null;

    private List<Node> children;

    private String name;

    private int id = -1;

    public Node(Node parent, int id, String name) {
        this.parent = parent;
        this.children = new ArrayList<Node>();
        this.name = name;
        this.id = id;
    }

    public int getId() {
        return this.id;
    }

    public String getName() {
        return this.name;
    }

    public void addChild(Node child) {
        children.add(child);
    }

    public List<Node> getChildren() {
        return children;
    }

    public boolean isRoot() {
        return (this.parent == null);
    }

    @Override
    public String toString() {
        return "id=" + id + ", name=" + name + ", parent=" + parent;
    }
}

public class NodeBuilder {

    public static Node build(List<Map<String, String>> input) {

        // maps id of a node to it's Node object
        Map<Integer, Node> nodeMap = new HashMap<Integer, Node>();

        // maps id of a node to the id of it's parent
        Map<Integer, Integer> childParentMap = new HashMap<Integer, Integer>();

        // create special 'root' Node with id=0
        Node root = new Node(null, 0, "root");
        nodeMap.put(root.getId(), root);

        // iterate thru the input
        for (Map<String, String> map : input) {

            // expect each Map to have keys for "id", "name", "parent" ... a
            // real implementation would read from a SQL object or resultset
            int id = Integer.parseInt(map.get("id"));
            String name = map.get("name");
            int parent = Integer.parseInt(map.get("parent"));

            Node node = new Node(null, id, name);
            nodeMap.put(id, node);

            childParentMap.put(id, parent);
        }

        // now that each Node is created, setup the child-parent relationships
        for (Map.Entry<Integer, Integer> entry : childParentMap.entrySet()) {
            int nodeId = entry.getKey();
            int parentId = entry.getValue();

            Node child = nodeMap.get(nodeId);
            Node parent = nodeMap.get(parentId);
            parent.addChild(child);
        }

        return root;
    }
}

public class NodePrinter {

    static void printRootNode(Node root) {
        printNodes(root, 0);
    }

    static void printNodes(Node node, int indentLevel) {

        printNode(node, indentLevel);
        // recurse
        for (Node child : node.getChildren()) {
            printNodes(child, indentLevel + 1);
        }
    }

    static void printNode(Node node, int indentLevel) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < indentLevel; i++) {
            sb.append("\t");
        }
        sb.append(node);

        System.out.println(sb.toString());
    }

    public static void main(String[] args) {

        // setup dummy data
        List<Map<String, String>> resultSet = new ArrayList<Map<String, String>>();
        resultSet.add(newMap("1", "Node 1", "0"));
        resultSet.add(newMap("2", "Node 1.1", "1"));
        resultSet.add(newMap("3", "Node 2", "0"));
        resultSet.add(newMap("4", "Node 1.1.1", "2"));
        resultSet.add(newMap("5", "Node 2.1", "3"));
        resultSet.add(newMap("6", "Node 1.2", "1"));

        Node root = NodeBuilder.build(resultSet);
        printRootNode(root);

    }

    //convenience method for creating our dummy data
    private static Map<String, String> newMap(String id, String name, String parentId) {
        Map<String, String> row = new HashMap<String, String>();
        row.put("id", id);
        row.put("name", name);
        row.put("parent", parentId);
        return row;
    }
}

如果您使用嵌套集(有时称为Modified preorder Tree Traversal)，您可以通过一个查询以树顺序提取整个树结构或其中的任何子树，但插入的代价更大，因为您需要管理通过树结构描述有序路径的列。

对于django-mptt，我使用了这样的结构:

id  parent_id  tree_id  level  lft  rght
--  ---------  -------  -----  ---  ----
 1       null        1      0    1    14
 2          1        1      1    2     7
 3          2        1      2    3     4
 4          2        1      2    5     6
 5          1        1      1    8    13
 6          5        1      2    9    10
 7          5        1      2    11   12

它描述了一个像这样的树(id代表每一项):

 1
 +-- 2
 |   +-- 3
 |   +-- 4
 |
 +-- 5
     +-- 6
     +-- 7

或者，作为一个嵌套的集合图，这使得left和right值的工作方式更加明显:

 __________________________________________________________________________
|  Root 1                                                                  |
|   ________________________________    ________________________________   |
|  |  Child 1.1                     |  |  Child 1.2                     |  |
|  |   ___________    ___________   |  |   ___________    ___________   |  |
|  |  |  C 1.1.1  |  |  C 1.1.2  |  |  |  |  C 1.2.1  |  |  C 1.2.2  |  |  |
1  2  3___________4  5___________6  7  8  9___________10 11__________12 13 14
|  |________________________________|  |________________________________|  |
|__________________________________________________________________________|

如您所见，要获得给定节点的整个子树，按照树的顺序，您只需选择在其left和right值之间具有left和right值的所有行。检索给定节点的祖先树也很简单。

The level column is a bit of denormalisation for convenience more than anything and the tree_id column allows you to restart the lft and rght numbering for each top-level node, which reduces the number of columns affected by inserts, moves and deletions, as the lft and rght columns have to be adjusted accordingly when these operations take place in order to create or close gaps. I made some development notes at the time when I was trying to wrap my head around the queries required for each operation.

为了实际使用这些数据来显示树，我创建了一个tree_item_iterator实用函数，对于每个节点，它应该为您提供足够的信息来生成您想要的任何类型的显示。

更多关于MPTT的信息:

SQL中的树 在数据库中存储分层数据 在MySQL中管理分层数据

考虑使用像neo4j这样的nosql工具来处理层次结构。 例如，像linkedin这样的网络应用程序使用couchbase(另一个nosql解决方案)

但是nosql只能用于数据集市级别的查询，而不能用于存储/维护事务

基于邻接表示的动态路径枚举的预序截线

嵌套集来自:

Konchog https://stackoverflow.com/a/42781302/895245 约翰尼·布坎南https://stackoverflow.com/a/194031/895245

是我见过的唯一有效的遍历方式，但代价是更新速度较慢。这可能是大多数人想要预订的。

来自https://stackoverflow.com/a/192462/895245的闭包表很有趣，但我不知道如何强制提前:MySQL闭包表分层数据库-如何以正确的顺序拉出信息

主要是为了好玩，这里有一个递归计算1.3.2.5的方法。前缀，并在最后根据它们进行排序，仅基于父ID/子索引表示。

好处:

更新只需要更新每个兄弟节点的索引

缺点:

N ^2内存使用量对于超深树来说是最坏的情况。这可能是相当严重的，这就是为什么我说这种方法可能主要只是为了好玩。但也许在某些超高更新的情况下，有人会想要使用它?谁知道 递归查询，所以读的效率比嵌套集要低

创建并填充表:

CREATE TABLE "ParentIndexTree" (
  "id" INTEGER PRIMARY KEY,
  "parentId" INTEGER,
  "childIndex" INTEGER NOT NULL,
  "value" INTEGER NOT NULL,
  "name" TEXT NOT NULL,
  FOREIGN KEY ("parentId") REFERENCES "ParentIndexTree"(id)
)
;
INSERT INTO "ParentIndexTree" VALUES
  (0, NULL, 0, 1, 'one'  ),
  (1, 0,    0, 2, 'two'  ),
  (2, 0,    1, 3, 'three'),
  (3, 1,    0, 4, 'four' ),
  (4, 1,    1, 5, 'five' )
;

代表树:

    1
   / \
  2   3
 / \
4   5

然后，对于像PostgreSQL这样的数组DBMS (https://www.postgresql.org/docs/14/arrays.html):

WITH RECURSIVE "TreeSearch" (
  "id",
  "parentId",
  "childIndex",
  "value",
  "name",
  "prefix"
) AS (
  SELECT
    "id",
    "parentId",
    "childIndex",
    "value",
    "name",
    array[0]
  FROM "ParentIndexTree"
  WHERE "parentId" IS NULL

  UNION ALL

  SELECT
    "child"."id",
    "child"."parentId",
    "child"."childIndex",
    "child"."value",
    "child"."name",
    array_append("parent"."prefix", "child"."childIndex")
  FROM "ParentIndexTree" AS "child"
  JOIN "TreeSearch" AS "parent"
    ON "child"."parentId" = "parent"."id"
)
SELECT * FROM "TreeSearch"
ORDER BY "prefix"
;

这将创建动态的表单前缀:

1 -> 0
2 -> 0, 0
3 -> 0, 1
4 -> 0, 0, 0
5 -> 0, 0, 1

然后PostgreSQL按字母顺序排序:

1 -> 0
2 -> 0, 0
4 -> 0, 0, 0
5 -> 0, 0, 1
3 -> 0, 1

这就是我们想要的预购结果。

对于像SQLite这样没有数组的DBMS，可以通过使用固定宽度的整数字符串来编码前缀。二进制是理想的，但我不知道怎么做，所以十六进制可以工作。当然，这意味着你必须选择一个最大深度，以适应所选字节的数量，例如下面我选择6，允许每个节点最多16^6个子节点。

WITH RECURSIVE "TreeSearch" (
  "id",
  "parentId",
  "childIndex",
  "value",
  "name",
  "prefix"
) AS (
  SELECT
    "id",
    "parentId",
    "childIndex",
    "value",
    "name",
    '000000'
  FROM "ParentIndexTree"
  WHERE "parentId" IS NULL

  UNION ALL

  SELECT
    "child"."id",
    "child"."parentId",
    "child"."childIndex",
    "child"."value",
    "child"."name",
    "parent"."prefix" || printf('%06x', "child"."childIndex")
  FROM "ParentIndexTree" AS "child"
  JOIN "TreeSearch" AS "parent"
    ON "child"."parentId" = "parent"."id"
)
SELECT * FROM "TreeSearch"
ORDER BY "prefix"
;

一些嵌套的集合注释

在看了其他嵌套的答案后，这里有几个点让我有点困惑。

Jonny Buchanan展示了他的嵌套设置:

__________________________________________________________________________
|  Root 1                                                                  |
|   ________________________________    ________________________________   |
|  |  Child 1.1                     |  |  Child 1.2                     |  |
|  |   ___________    ___________   |  |   ___________    ___________   |  |
|  |  |  C 1.1.1  |  |  C 1.1.2  |  |  |  |  C 1.2.1  |  |  C 1.2.2  |  |  |
1  2  3___________4  5___________6  7  8  9___________10 11__________12 13 14
|  |________________________________|  |________________________________|  |
|__________________________________________________________________________|

这让我想知道为什么不使用更简单的外观:

__________________________________________________________________________
|  Root 1                                                                 |
|   ________________________________    _______________________________   |
|  |  Child 1.1                     |  |  Child 1.2                    |  |
|  |   ___________    ___________   |  |   ___________   ___________   |  |
|  |  |  C 1.1.1  |  |  C 1.1.2  |  |  |  |  C 1.2.1  | |  C 1.2.2  |  |  |
1  2  3___________|  4___________|  |  5  6___________| 7___________|  |  | 
|  |________________________________|  |_______________________________|  |
|_________________________________________________________________________|

每个端点都没有额外的数字。

但当我真正尝试实现它时，我注意到很难/不可能实现这样的更新查询，除非我有Konchog所使用的父级信息。问题是，当树被移动时，在某种情况下很难/不可能区分兄弟姐妹和父母，我需要这来决定是否要在缩小差距时减少右手边。

左/大小vs左/右:你可以在数据库中以任何一种方式存储它，但我认为左/右可以更有效，因为你可以用多列索引(左，右)索引DB，然后可以用来加速祖先查询，这是类型:

left < curLeft AND right > curLeft

在Ubuntu 22.04, PostgreSQL 14.5, SQLite 3.34.0上测试。