如何在关系数据库中存储 children 的链接树？

Question

我有一个带有 children（节点）的自定义 LinkedTree，并且节点具有邻接关系，即每个节点都与上一个和下一个节点链接。这个LinkedTree很重，很大，可能有几百万个节点。

这是一个代码示例：

package tree;

import java.io.Serializable;

public class LinkedTree<E> implements Serializable {

    private int size = 0;
    private Node<E> first;
    private Node<E> last;
    private LinkedTree<E> children;

    public LinkedTree() {
        children = new LinkedTree<>();
    }

    public LinkedTree(LinkedTree<E> children) {
        this.children = children;
    }

    public void add(E element) {

        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, element, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
    }

    public void remove(E element) {

        ...
    }

    public int size() {

         return size;
    }

    public static class Node<E> implements Serializable {

        E item;
        Node<E> next;
        Node<E> prev;

        public Node(Node<E> prev, E item, Node<E> next) {

            this.item = item;
            this.next = next;
            this.prev = prev;
        }

        public E item() {

            return item;
        }

        public boolean hasPrevious() {

            return prev != null;
        }

        public Node<E> previous() {

            return prev;
        }

        public Node<E> previous(int target) {

            Node<E> n = this;
            int i = target;
            while (i-- > 0 && n != null)
                n = n.prev;
            return n;
        }

        public boolean hasNext() {

            return next != null;
        }

        public Node<E> next() {

            return next;
        }

        public E nextItem() {

            return next.item;
        }

        public E nextItem(int target) {

            return next(target).item();
        }

        public Node<E> next(int target) {

            Node<E> n = this;
            int i = 0;
            while (i++ < target && n != null)
                n = n.next;
            return n;
        }

        @Override
        public int hashCode() {

            return item != null ? item.hashCode() : 0;
        }

        @Override
        public boolean equals(Object o) {

            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;

            Node<?> node = (Node<?>) o;

            return item != null ? item.equals(node.item) : node.item == null;
        }

        @Override
        public String toString() {

            return item.toString();
        }
    }
}

我想将它序列化并保存在文件中以使其持久化，但是加载和写入一些数据可能成本太高。所以我决定将它保存在 MySQL 中，这样我就可以从任何地方加载数据。我的意思是从这个层次结构的结尾、中间或开头。

我想行的关系应该同时是邻接关系和parent-child关系。但是我不知道该怎么做。

Answer 1

我会评论要求更多信息（特别是示例数据和层次结构规则）所以请原谅第一次剪辑过于笼统

我做出了以下假设：

您的结构深度超过三层 - 如果不是这种情况，那么我不会这样做，因为它不值得
您的负载很重，对树的某些部分的写入是并发的但不冲突，而写入冲突很少见或不存在
您不需要对树进行并行、部分和无共享或无锁访问来构建或处理它（在这种情况下，您需要发出 deletes 信号，这你可以通过指向你替换的节点来完成 ie. superseded)

我建议的数据模型类似于：

create table treemodel (
 `node` int not null 
 , `parent` int not null 
 , `principal` int not null 
 , `state` smallint unsigned not null 
 , ...
 , `supersedes` int    /*version instead of lossy update or delete*/
 , `supersededby` int
) engine = innodb;
alter table treemodel add primary key (`principal`, `node`) using btree;

树模型 table 只会保存结构标识符：我会在单独的 table 中保存节点数据，但我不会加入获取它，相反，我会执行第二个 select ... where node in (...) - 这基本上是说 'the structure of my data is independent of my data'
此模型旨在限制往返数据库的次数，可能看起来违反直觉，但允许您在单个数据库指令中读取或锁定树的部分没有加入
这会运行与您的数据模型相反，因为您不会为嵌套的子节点存储额外的 'principal' 节点 - 但如果您可以更改此结构，则您可以利用此建议来避免循环内的查询，即。多个 selects，或可重入查询或自/一元连接
...但是您的业务逻辑需要支持我所说的 'principal' 节点
将什么放入主节点取决于您的用例 - 我已经使用此模型来存储观察记录及其派生之间的因果关系，而不管下面的父子关系这一点 - 另一个示例可能是：1) 客户提出支持案例，或 2) 发送新消息，或 3) 创建新文件，...
将主体存储为树结构中的实际根节点（即节点 ID“1”或 'data directory' 或其他）是没有意义的 - 而不是你为了论证的缘故，将存储 'next level down'，即。 'user root directory' 或 'first level below user root directory' - 了解您的用例和业务规则会有所帮助
... 并且您的 java 代码将需要更新以查找或复制并存储此概念 - 它始终是任何 [=14 上的父节点的副本=] 在树的给定分支内 - 如果您正在移动分支并且您的逻辑需要更改此数字，则它是 update ... set principal=y where principal=x 和 update ... set parent=newid where node=current_principal
... 说了这么多，我不会更新行本身，只有 insert 更改和重新创建整个 ~~tree~~ 分支（它解释了 state 字段，即 CURRENT, DELETED, ... 删除分支的根节点仍然指向它当前的父节点，例如 for 'deleted items')
您仍然保留指向上一个和下一个相邻节点的指针 - 在最坏的情况下，将节点有序插入到树的分支中需要 select ... where principal=x for update，但是可能只有一个 select ... where (node=x or prev=x or next=x) for update

编辑：

主键/聚簇索引必须是唯一的 - 您也可以在 principal 上分区以确保快速并行访问
重新创建而不是更新分支

Answer 2

一年前我有同样的要求，然后我探索了很多选择。然后我决定使用图形数据库。试用图形数据库 Neo4j。

如何在关系数据库中存储 children 的链接树？

How to store Linked Tree with children in Relational Database?

java

mysql

database

tree

data-persistence