需要找到下一个节点插入二叉树，资源和性能占用较少

Question

数据库树架构

节点ID	节点位置	nodeparentid
1	左	空
2	左	1
3	对	1
4	左	2
5	对	2
6	左	3
7	对	3
8	左	4
9	对	4

当用户提交树形表单时，此表会继续增加。

已经创建了一个函数，通过 BFS 方法通过给定节点值查找下一个父节点，现在面临性能问题， 当搜索 1 时有 200k 行，它需要更多的资源和性能，因为它检查每个节点，因此优化代码从单个查询中获取所有行并从值执行逻辑，这将减少数据库交互，但现在当更多时所有行都存储在内存中用户为每个用户找到下一个nodeparentid，所有行都存储在内存中，因此导致问题需要优化代码

当前执行时间为80秒。

我尝试使用下面的代码片段来查找给定节点的下一个父节点

public function getNodeInsertPostionByParentId($parentIds)
{
    $parent = array('status' => false);
    $results = array();

    // Fetch all data from tree
    $qry = "SELECT nodeid, nodeposition, nodeparentid FROM tree ORDER BY nodeposition";
    $stmt = $this->mysqli->prepare($qry);
    $stmt->execute();
    $stmt->bind_result($nodeid, $nodeposition, $nodeparentid);

    // Create a map to store children for each parent
    $childrenMap = array();

    // Process query results
    while ($stmt->fetch()) {
        $childrenMap[$nodeparentid][] = array('id' => $nodeid, 'position' => $nodeposition);
    }

    // Use BFS to process each parent ID
    $queue = $parentIds;

    while (!empty($queue)) {
        $currentParent = array_shift($queue);

        // Process the current parent
        $children = isset($childrenMap[$currentParent]) ? $childrenMap[$currentParent] : array();
        $count = count($children);

        if ($count == 2) {
            // Two children, recursively check each child
            foreach ($children as $child) {
                $queue[] = $child['id'];
            }
           
        } elseif ($count == 1) {
            // One child, set position to 'Right' or 'Left' based on the child's ID
            $parent['status'] = true;
            $parent['parentId'] = $currentParent;
            $parent['node'] = 'Right';
            break;
        } elseif ($count == 0) {
            // No children, set position to 'Right' or 'Left' based on the current parent's ID
            $parent['status'] = true;
            $parent['parentId'] = $currentParent;
            $parent['node'] = 'Left';
            break;
        }
    }

    // Return the processed results
    return $parent;
}

$yourInstance = new YourClassName();
echo '<pre>';
print_r($yourInstance->getNodeInsertPostionByParentId(array('1')));

通过什么方式我们可以用更少的资源来减少执行时间。

以上数据的树状视图

             1 
         /        \
        2          3 
      /    \      / \
     4      5    6  7 
    / \    / \
   8   9  10

• 如果搜索 1 以获得下一个节点，则插入 5 右边作为输出
• 如果搜索 6 以获得下一个节点，则插入 6 left 作为输出
• 如果搜索 3 以获得下一个节点，则插入 6 left 作为输出
• 如果搜索 2 以获得下一个节点，则插入 5 右边作为输出

任何建议或代码都会有帮助

Answer 1

如果要为一个节点获取一个父节点，则可以通过在表中每一行包含parentid 来实现。每次获取将花费几毫秒。

如果您获取给定节点的祖先，即使重复应用上述获取也将花费不到 1 秒的时间。如果 CTE 可用，速度甚至会更快。注意：这不需要二叉树。

如果您正在修改树（添加/删除/重新排列节点），那么存储所有数据并获取整个集合的效率非常低。

如果你正在“玩”二叉树，为什么要反复重新加载它？

如果您发现“左-右”或“红-黑”树，请不要使用数据库；修改数据时效率极低。

优先级队列非常高效，但前提是它完全位于 RAM 中；存储在磁盘上效率很低。