Comment puis-je générer une arborescence à partir d'une table dans une base de données?

Question

J'essaie de générer une structure arborescente à partir d'une table dans une base de données. La table est stockée à plat, avec chaque enregistrement ayant un parent_id ou 0. Le but ultime est d'avoir une boîte de sélection générée, et un tableau de noeuds.

Le code que j'ai à ce jour est:

function init($table, $parent_id = 0) 
{ 

    $sql = "SELECT id, {$this->parent_id_field}, {$this->name_field} FROM $table WHERE {$this->parent_id_field}=$parent_id ORDER BY display_order"; 

    $result = mysql_query($sql); 

    $this->get_tree($result, 0); 

    print_r($this->nodes); 
    print_r($this->select); 
    exit; 
} 

function get_tree($query, $depth = 0, $parent_obj = null) 
{ 
    while($row = mysql_fetch_object($query)) 
    { 
     /* Get node */ 
     $this->nodes[$row->parent_category_id][$row->id] = $row; 

     /* Get select item */ 
     $text = ""; 
     if($row->parent_category_id != 0) { 
      $text .= " "; 
     } 
     $text .= "$row->name"; 
     $this->select[$row->id] = $text; 

     echo "$depth $text\n"; 

     $sql = "SELECT id, parent_category_id, name FROM product_categories WHERE parent_category_id=".$row->id." ORDER BY display_order"; 

     $nextQuery = mysql_query($sql); 
     $rows = mysql_num_rows($nextQuery); 

     if($rows > 0) { 
      $this->get_tree($nextQuery, ++$depth, $row); 
     }    
    } 
} 

Il est presque travail, mais pas tout à fait. Quelqu'un peut-il m'aider à le finir?

Answer 1

Je pense qu'il est cette ligne ici:

if($row->parent_category_id != 0) { 
    $text .= " "; 
} 

devrait être:

while ($depth-- > 0) { 
    $text .= " "; 
} 

Vous n'indentation une fois, non le nombre de fois qu'il devrait être indenté.

Et cette ligne:

$this->get_tree($nextQuery, ++$depth, $row); 

devrait être:

$this->get_tree($nextQuery, $depth + 1, $row); 

Notez que vous devriez probablement suivre les conseils dans l'autre réponse que, et saisir toute la table à la fois, puis processus tout d'un coup, car en général vous voulez minimiser les allers-retours à la base de données (il y a quelques cas d'utilisation où la façon dont vous le faites est plus optimale, comme si vous avez un très grand arbre, et que vous choisissez un petit partie de celui-ci, mais je doute que ce soit le cas ici)

Answer 2

$this->nodes[$row->parent_category_id][$row->id] = $row; 

Cette ligne est en train de détruire votre commande ORDER BY display_order. Changez-le en

$this->nodes[$row->parent_category_id][] = $row; 

Mon prochain numéro est la partie $ row-> parent_category_id de cela. Ne devrait-il pas simplement être $ row-> parent_id?

EDIT: Oh, je n'ai pas lu votre source assez attentivement. Débarrassez-vous de la clause WHERE. Lire toute la table à la fois. Vous devez post-traiter l'arbre une deuxième fois. D'abord, vous lisez la base de données dans une liste de tableaux. Ensuite, vous traitez le tableau de manière récursive pour faire votre sortie.

Votre tableau doit ressembler à ceci:

Array(0 => Array(1 => $obj, 5 => $obj), 
     1 => Array(2 => $obj), 
     2 => Array(3 => $obj, 4 => $obj), 
     5 => Array(6 => $obj)); 

function display_tree() { 
     // all the stuff above 
     output_tree($this->nodes[0], 0); // pass all the parent_id = 0 arrays. 
} 

function output_tree($nodes, $depth = 0) { 
    foreach($nodes as $k => $v) { 
     echo str_repeat(' ', $depth*2) . $v->print_me(); 
     // print my sub trees 
     output_tree($this->nodes[$k], $depth + 1); 
    } 
} 

output: 
object 1 
    object 2 
    object 3 
    object 4 
object 5 
    object 6 

Answer 3

Vous ne devriez certainement pas continuer votre chemin actuel. La méthode récursive que vous essayez d'utiliser va presque certainement tuer votre performance si votre arbre devient même légèrement plus grand. Vous devriez probablement regarder une structure de jeu imbriquée au lieu d'une liste d'adjacence si vous prévoyez de lire l'arbre fréquemment.

Avec un ensemble imbriqué, vous pouvez facilement récupérer l'arborescence entière imbriquée correctement avec une seule requête.

Veuillez consulter ces questions pour une discussion sur les arbres.

Is it possible to query a tree structure table in MySQL in a single query, to any depth?

Implementing a hierarchical data structure in a database

What is the most efficient/elegant way to parse a flat table into a tree?