php - 一棵大树上的二叉树高度性能

Question

我将二叉树存储在 mysql 数据库的表中。该表包含列 id、parent 和其他不重要的列。这些列是不言自明的。

我设法得到了树的高度:

    $depth = 0;
    /* @var $db PDO */
    $stmt = $db->prepare( "SELECT id FROM wp_members WHERE parent = :parent AND matrix_id = :matrix_id" );

    $q = new SplQueue();
    $q->push( array( 0, 0 ) );

    while (!$q->isEmpty()) {
        $cur = $q->pop();

        $stmt->bindParam( ':parent', $cur[0] );
        $stmt->bindParam( ':matrix_id', $matrix_id );

        $stmt->execute();

        $ids = $stmt->fetchAll();

        if ($cur[1] > $depth) $depth++;

        if (count($ids) > 0) $q->add( 0, array( $ids[0]['id'], $cur[1] + 1));
        if (count($ids) > 1) $q->add( 0, array( $ids[1]['id'], $cur[1] + 1));
    }

    return $depth;

PS: matrix_id => 让我们调用tree id

它返回正确的树的高度，但问题是数据库有超过 18k 的节点，这需要很多时间才能获得树的高度。

我想知道我能做些什么来解决这种情况？获取树的高度需要 60 多秒。

Answer 1

我使用了@M0rtiis 提出的解决方案:

ALTER TABLE `wp_members` ADD `depth` INT UNSIGNED NOT NULL AFTER `parent`;

我写了一个脚本来遍历存储关卡的树。

然后我简单的:

$sql = $wpdb->prepare( "SELECT MAX(depth) FROM wp_members WHERE matrix_id = '%d'", $matrix_id );
$height = $wpdb->get_var( $sql );

return $height === NULL ? 0 : $height;

得到树的高度;)

PS:我选择@M0rtiis 解决方案是因为它看起来很简单，而在其他功能中我需要通过指定级别获取所有节点。