Cum sortați un arbore stocat utilizând modelul de set imbricat?

When I refer to nested set model I mean what is described here.

Trebuie să construiesc un nou sistem pentru stocarea "categoriilor" (nu mă pot gândi la un cuvânt mai bun pentru asta) într-o ierarhie definită de utilizator. Deoarece modelul de seturi imbricate este optimizat pentru citiri în loc de scrieri, am decis să folosesc acest lucru. Din păcate, în timpul cercetării și testarea seturilor imbricate, am intrat în problema modului în care afișăm arborele ierarhic cu noduri sortate. De exemplu, dacă am ierarhia:

root
    finances
        budgeting
            fy08
    projects
        research
        fabrication
        release
    trash

Vreau ca aceasta să fie sortată astfel încât să fie afișată ca:

root
    finances
        budgeting
            fy08
    projects
        fabrication
        release
        research
    trash

Observați că fabricarea apare înainte de cercetare.

Oricum, după o lungă căutare am văzut un răspuns, cum ar fi "păstrați arborele într-o matrice multidimensională și sortați-l" și "recăpătați copacul și serializați înapoi în modelul set de imbricate" (paraphrazing ...). Oricum, prima soluție este o risipă oribilă de RAM și CPU, care sunt ambele resurse foarte finite ... A doua soluție pare doar ca un cod dureros.

Indiferent, am reușit să-mi dau seama cum să (utilizând modelul de seturi imbricate):

  1. Porniți un nou arbore în SQL
  2. Introduceți un nod ca un copil al altui nod din arbore
  3. Introduceți un nod după un nod frate în copac
  4. Trageți tot arborele cu structura de ierarhie din SQL
  5. Trageți un subfaza dintr-un anumit nod (inclusiv rădăcina) în ierarhia cu sau fără o limită de adâncime
  6. Găsiți părintele oricărui nod din arbore

Așa că m-am gândit că # 5 și # 6 ar putea fi folosite pentru a face sortarea pe care am dorit-o și ar putea fi folosită și pentru a reconstrui arborele în ordine sortată.

Cu toate acestea, acum că m-am uitat la toate aceste lucruri am învățat să fac văd că # 3, # 5 și # 6 ar putea fi utilizate împreună pentru a efectua inserate sortate. Dacă aș fi sortat inserturi, acesta va fi întotdeauna sortat. Cu toate acestea, dacă schimba vreodată criteriile de sortare sau vreau o ordine de sortare diferită, mă întorc la pătrat.

Ar putea fi aceasta doar limitarea modelului de set imbricat? Folosirea sa inhibă sortarea de interogări a ieșirii?

17

8 răspunsuri

Am folosit foarte mult seturile Nested și am întâmpinat de multe ori aceeași problemă. Ceea ce fac și ceea ce aș recomanda este doar să nu sortați elementele din baza de date. În schimb, sortați-le în interfața cu utilizatorul. După ce ați tras toate nodurile din DB, probabil că trebuie să le convertiți într-o structură ierarhică de date, oricum. În structura respectivă, sortați toate matricele care conțin copiii nodului.

De exemplu, dacă interfața dvs. este o aplicație Flex și copiii unui nod sunt stocați într-o imagine ICollectionView, puteți utiliza proprietatea de sortare pentru a le afișa așa cum doriți.

Un alt exemplu, dacă interfața dvs. este o ieșire dintr-un script PHP, ați putea avea copiii fiecărui nod într-un matrice și să utilizați funcțiile de sortare din matricea PHP pentru a efectua sortarea.

Desigur, acest lucru funcționează numai dacă nu aveți nevoie de intrările actuale pentru a fi sortate, dar nu?

4
adăugat

Cred că aceasta este într-adevăr o limitare a modelului setat. Nu puteți sorta cu ușurință nodurile copil în nodul părinte respectiv, deoarece ordonarea setului de rezultate este esențială pentru reconstrucția structurii copacilor.

Cred că este probabil cea mai bună metodă de păstrare a arborelui sortat la introducerea, actualizarea sau ștergerea nodurilor. Acest lucru chiar face ca interogările să fie foarte rapide, ceea ce reprezintă unul dintre obiectivele principale ale acestei structuri de date. Dacă implementați procedurile memorate pentru toate operațiile, este foarte ușor de utilizat.

De asemenea, puteți inversa ordinea de sortare a unui arbore presorted. Trebuie să utilizați ORDER BY node.rgt DESC în loc de ORDER BY node.lft ASC .

Dacă într-adevăr trebuie să sprijiniți un alt criteriu de sortare, ați putea să-l implementați prin adăugarea unui al doilea indice lft și rgt la fiecare nod și păstrați acest sortat după celelalte criterii inserare/actualizare/ștergere.

4
adăugat

Tocmai am terminat de scris următoarele lucruri care lucrează pentru mine în sortarea unui întreg copac imbricat.

The sort (ideally) requires a view that lists the current level of each node in the tree and a procedure for swapping two nodes - both are included below, the sibling swap code comes from Joe Celkos ' Tree & Hierarchies' book which I strongly recommend to anyone using nested sets.

Tipul poate fi modificat în instrucțiunea "INSERT INTO @t", aici este un simplu sort alfanumeric pe "Nume"

Acest lucru poate fi o modalitate proastă de a face acest lucru, mai ales folosind cursorul pentru un set bazat pe cod, dar după cum spun că funcționează pentru mine, sper că ajută.

UPDATE:

Codul de mai jos prezintă acum versiunea fără a utiliza cusor. Văd despre îmbunătățiri de viteză de 10 ori

CREATE VIEW dbo.tree_view

AS

SELECT t2.NodeID,t2.lft,t2.rgt ,t2.Name, COUNT(t1.NodeID) AS level  
FROM dbo.tree t1,dbo.tree t2
WHERE t2.lft BETWEEN t1.lft AND t1.rgt
GROUP BY t2.NodeID,t2.lft,t2.rgt,t2.Name

GO

----------------------------------------------

  DECLARE @CurrentNodeID int
DECLARE @CurrentActualOrder int
DECLARE @CurrentRequiredOrder int
DECLARE @DestinationNodeID int
DECLARE @i0 int
DECLARE @i1 int
DECLARE @i2 int
DECLARE @i3 int

DECLARE @t TABLE (TopLft int,NodeID int NOT NULL,lft int NOT NULL,rgt int NOT NULL,Name varchar(50),RequiredOrder int NOT NULL,ActualOrder int NOT NULL)


INSERT INTO @t (toplft,NodeID,lft,rgt,Name,RequiredOrder,ActualOrder)
    SELECT tv2.lft,tv1.NodeID,tv1.lft,tv1.rgt,tv1.Name,ROW_NUMBER() OVER(PARTITION BY tv2.lft ORDER BY tv1.ColumnToSort),ROW_NUMBER() OVER(PARTITION BY tv2.lft ORDER BY tv1.lft ASC)
    FROM dbo.tree_view tv1 
    LEFT OUTER JOIN dbo.tree_view tv2 ON tv1.lft > tv2.lft and tv1.lft < tv2.rgt and tv1.level = tv2.level+1
    WHERE tv2.rgt > tv2.lft+1

    DELETE FROM @t where ActualOrder = RequiredOrder


WHILE EXISTS(SELECT * FROM @t WHERE ActualOrder <> RequiredOrder)
BEGIN


    SELECT Top 1 @CurrentNodeID = NodeID,@CurrentActualOrder = ActualOrder,@CurrentRequiredOrder = RequiredOrder
    FROM @t 
    WHERE ActualOrder <> RequiredOrder
    ORDER BY toplft,requiredorder

    SELECT @DestinationNodeID = NodeID
    FROM @t WHERE ActualOrder = @CurrentRequiredOrder AND TopLft = (SELECT TopLft FROM @t WHERE NodeID = @CurrentNodeID) 

    SELECT @i0 = CASE WHEN c.lft < d.lft THEN c.lft ELSE d.lft END,
            @i1 =  CASE WHEN c.lft < d.lft THEN c.rgt ELSE d.rgt END,
            @i2 =  CASE WHEN c.lft < d.lft THEN d.lft ELSE c.lft END,
            @i3 =  CASE WHEN c.lft < d.lft THEN d.rgt ELSE c.rgt END
    FROM dbo.tree c
    CROSS JOIN dbo.tree d
    WHERE c.NodeID = @CurrentNodeID AND d.NodeID = @DestinationNodeID

    UPDATE dbo.tree
    SET lft = CASE  WHEN lft BETWEEN @i0 AND @i1 THEN @i3 + lft - @i1
                    WHEN lft BETWEEN @i2 AND @i3 THEN @i0 + lft - @i2
            ELSE @i0 + @i3 + lft - @i1 - @i2
            END,
        rgt = CASE  WHEN rgt BETWEEN @i0 AND @i1 THEN @i3 + rgt - @i1
                    WHEN rgt BETWEEN @i2 AND @i3 THEN @i0 + rgt - @i2
            ELSE @i0 + @i3 + rgt - @i1 - @i2
            END
    WHERE lft BETWEEN @i0 AND @i3 
    AND @i0 < @i1
    AND @i1 < @i2
    AND @i2 < @i3

    UPDATE @t SET actualorder = @CurrentRequiredOrder where NodeID = @CurrentNodeID
    UPDATE @t SET actualorder = @CurrentActualOrder where NodeID = @DestinationNodeID

    DELETE FROM @t where ActualOrder = RequiredOrder

END
2
adăugat
Minunat, acesta este exact ceea ce am căutat. A rezolvat complet problema de sortare pe care o aveam cu ierarhia noastră imbricată.
adăugat autor Hamman359, sursa

Da, este o limitare a modelului setat imbricat, deoarece seturile imbricate reprezintă o reprezentare preordonată a unei ierarhii. Această precomandare este motivul pentru care este atât de rapid pentru citiri. Modelul de apropiere, descris, de asemenea, în pagina pe care vă conectați, vă oferă cea mai flexibilă sortare și filtrare, dar cu un impact semnificativ asupra performanței.

Abordarea mea preferată pentru inserții și mutări într-un set imbricat este de a trata ramura afectată ca și în modelul adjacency: Obțineți o listă cu noii frați; găsiți locul potrivit în lista pentru noul nod; și să construiască instrucțiunile de actualizare necesare (care sunt biții în care trebuie să fii atent). În ceea ce privește modificarea criteriilor dvs. de comandă: Este o sarcină unică, astfel încât să vă puteți permite să suflați unele RAM și CPU pe ea, răspunsul cel mai flexibil ar fi să rupă reprezentarea setului imbricat într-o reprezentare adjacency și să reconstrui setul imbricat de la adiacența bazată pe criterii noi.

1
adăugat

Sortarea Seturilor Nested nu are limite și nu este dificilă. Doar sortați după partea din stânga (ancora, orice) și sa terminat. Dacă aveți un nivel pentru fiecare nod, puteți, de asemenea, să scuturați indentarea corectă pe baza nivelului.

1
adăugat
Acesta este adevăratul punct pe care încerc să-l fac (și voi lua lovitura -1 pentru ao face ;-). Chiar și soluția fină a lui Justin folosește în continuare o buclă În timp care este încă un cursor fără cuvântul CURSOR în ea. Cheia pentru toate acestea este de a construi inițial seturile Nested în ordinea corectă. Am putea posta cateva link-uri despre cum sa facem asta in mod corespunzator si cu o viteza suficient de mare incat sa o poti face cu usurinta pe orice schimbare, dar probabil ca am sa fiu blasted doar pentru postarea unei adrese URL in loc de cod asa cum am facut deja. ;-)
adăugat autor Jeff Moden, sursa

Cred că, în cazul tău, unde nodurile pe care vrei să le schimbi nu au nici un descendent, poți pur și simplu să schimbi valorile lft și rgt în jur. Luați în considerare acest arbore:

   A
/  \
B     C
    /\
    D   E

Acest lucru se poate transforma în acest grup de seturi imbricate:

1 A 10 
2 B 3  
4 C 9
5 D 6
7 E 8

Acum considerați că doriți să schimbați D și E. Următoarele seturi imbricate sunt valide și D și E sunt schimbate:

1 A 10
2 B 3 
4 C 9 
7 D 8
5 E 6 

Swapping noduri care au subtrees nu poate fi făcut în acest fel, desigur, pentru că ar trebui să actualizeze lft copii și rgt valori, de asemenea.

0
adăugat

You can sort thier when you render. I explained rendering here How to render all records from a nested set into a real html tree

0
adăugat

See my simple solution from method of my class. $this->table->order is Nette framework code to get data from DB.

$tree = Array();
$parents = Array();
$nodes = $this->table->order('depth ASC, parent_id ASC, name ASC');
$i = 0;
$depth = 0;
$parent_id = 0;

foreach($nodes as $node) {
    if($depth < $node->depth || $parent_id < $node->parent_id) {
        $i = $parents["{$node->parent_id}"] + 1;
    }
    $tree[$i] = $node;
    $parents["{$node->id}"] = $i;
    $depth = $node->depth;
    $parent_id = $node->parent_id;
    $i += (($node->rgt - $node->lft - 1)/2) + 1;
}
ksort($tree);
0
adăugat