List:General Discussion« Previous MessageNext Message »
From:Peter Brawley Date:March 8 2006 4:56am
Subject:Re: optimization - directories and sub-directories (with descendants)
View as plain text  
Eli,

 >Example: I want to search on all the directories under 'd4' that 
contain the word "music".

 >I got several solutions, but not satisfying:
 >A) Loop from 'd4' to sub-dirs in first level, and use buffer list for 
next iterations
 >when going deeper into levels. [not good: there can be many sub-dirs 
with descendants,
 >and the loop will iter more; slow on searches].
 >B) Storing the directory tree structure in the form of 'root/d1/d4/d6' 
and etc.
 >[not good: personally I can't use it (specific implementation 
restriction)].
 >C) Descendants sub-dirs connections to sub-dirs on deeper levels, so 
searching will go
 >over the first level sub-dirs and the descendants sub-dirs. [not good: 
there can be many
 >sub-dirs and there would be many descendants sub-dirsl; duplicating 
descendants on references].

As you say, your A and C aren't maintainable. If a node can have more 
than one parent node (ie its indegree can > 1), it ain't  a tree, so 
tree methods won't work unmodified. It's possible, though, to adapt some 
tree traversal methods to a graph like yours; for an example see the 
parts explosion section in 
http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html.

PB

-----

Eli wrote:
> Hi,
>
> I have a table of directories. Each row represents a directory, which 
> holds his name and desc. Another table lists sub-directories from each 
> directory source to its sub-directories targets.
>
> dirs:
> +----------+--------------+------------+
> | dir_id   | dir_name     | dir_desc   |
> +----------+--------------+------------+
> |        0 |         root |   root dir |
> |       11 |           d1 |  dir no. 1 |
> |       12 |           d2 |  dir no. 2 |
> |       21 |           d3 |  dir no. 3 |
> |       22 |           d4 |  dir no. 4 |
> |       23 |           d5 |  dir no. 5 |
> |       31 |           d6 |  dir no. 6 |
> |       32 |           d7 |  dir no. 7 |
> |       41 |           d8 |  dir no. 8 |
> |       51 |           d9 |  dir no. 9 |
> |       52 |          d10 | dir no. 10 |
> |       61 |          d11 | dir no. 11 |
> +----------+--------------+------------+
> 12 rows in set (0.00 sec)
>
> subdirs:
> +------------+------------+
> | dir_source | dir_target |
> +------------+------------+
> |          0 |         11 |
> |          0 |         12 |
> |         11 |         21 |
> |         11 |         22 |
> |         11 |         23 |
> |         12 |         31 |
> |         22 |         31 |
> |         22 |         32 |
> |         23 |         52 |
> |         31 |         41 |
> |         41 |         51 |
> |         41 |         52 |
> |         52 |         61 |
> +------------+------------+
> 13 rows in set (0.00 sec)
>
> root (0)
>    +d1 (11)
>    |  +d3 (21)
>    |  +d4 (22)
>    |  |  +d6 (31)
>    |  |  |  +d8 (41)
>    |  |  |     +d9 (51)
>    |  |  |     +d10 (52)
>    |  |  |         +d11 (61)
>    |  |  +d7 (32)
>    |  +d5 (23)
>    |     +*d10* (52) -reference
>    +d2 (12)
>       +*d6* (31) -reference
>
> Note that a directory can be contained in several parent directories 
> (as long as it doesn't creates circles) - "references".
>
> Example: I want to search on all the directories under 'd4' that 
> contain the word "music".
>
> I got several solutions, but not satisfying:
> A) Loop from 'd4' to sub-dirs in first level, and use buffer list for 
> next iterations when going deeper into levels. [not good: there can be 
> many sub-dirs with descendants, and the loop will iter more; slow on 
> searches].
> B) Storing the directory tree structure in the form of 'root/d1/d4/d6' 
> and etc. [not good: personally I can't use it (specific implementation 
> restriction)].
> C) Descendants sub-dirs connections to sub-dirs on deeper levels, so 
> searching will go over the first level sub-dirs and the descendants 
> sub-dirs. [not good: there can be many sub-dirs and there would be 
> many descendants sub-dirsl; duplicating descendants on references].
>
> Do you have any other suggestions? What's the better way?
>
>
> -Thanks in advance... :-)
>


-- 
No virus found in this outgoing message.
Checked by AVG Free Edition.
Version: 7.1.375 / Virus Database: 268.2.0/275 - Release Date: 3/6/2006

Thread
optimization - directories and sub-directories (with descendants)Eli8 Mar
  • Re: optimization - directories and sub-directories (with descendants)Peter Brawley8 Mar