Binary tree height performance on a big tree

Question

I'm storing a binary tree on a table in mysql database. The table have the columns id, parent, and others that isn't important. The columns is self explanatory.

I managed to get height of the tree:

    $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 => let's call tree id

It returns the height of the tree correct, but the problem is that database has more than 18k of nodes, and this takes a lot of time just to get tree height.

What I want to know is what I can do do solve this situation ? it takes more than 60secs to get height of the tree.

i believe for this purpose you should store `depth` in your table for all the rows. after that just SELECT MAX(`depth`) for needed tree. or even make separate table (`tree_id`, `depth`) — M0rtiis, Aug 17 '15 at 03:48
where `depth` is parent.`depth` + 1. you can apply this logic in app or using a trigger on insert — M0rtiis, Aug 17 '15 at 03:56
You can find the depth using sql query, see http://stackoverflow.com/questions/16513418/how-to-do-the-recursive-select-query-in-mysql — Taher Rahgooy, Aug 17 '15 at 03:59

score 0 · Accepted Answer · answered Aug 17 '15 at 15:49

I've used the solution proposed by @M0rtiis:

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

and i wrote a script to travel the tree storing the level.

after that i simple:

$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;

and got the height of the tree ;)

PS: I choose @M0rtiis solution because it looks so simple, and in other function I need get all nodes by specified the level.

Binary tree height performance on a big tree

1 Answers1