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

Question

我正在 mysql 数据库中的 table 上存储二叉树。 table 包含 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

它returns树的高度正确，但问题是数据库有超过 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的解决方案，因为它看起来很简单，而在其他功能中，我需要通过指定的级别获取所有节点。

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

Binary tree height performance on a big tree

php

mysql

tree

binary-tree