Sortowanie drzewa ze zmaterializowaną ścieżką?

Question

Mam strukturę drzewa w tabeli i używa zmaterializowanych ścieżek, aby umożliwić mi szybkie odnalezienie dzieci. Jednak muszę również sortować wyniki z dokładnością do pierwszej, tak jak można by oczekiwać w przypadku odpowiedzi na wątkowe forum.

id | parent_id | matpath |   created   
----+-----------+---------+---------------------------- 
    2 |   1 | 1  | 2010-05-08 15:18:37.987544 
    3 |   1 | 1  | 2010-05-08 17:38:14.125377 
    4 |   1 | 1  | 2010-05-08 17:38:57.26743 
    5 |   1 | 1  | 2010-05-08 17:43:28.211708 
    7 |   1 | 1  | 2010-05-08 18:18:11.849735 
    6 |   2 | 1.2  | 2010-05-08 17:50:43.288759 
    9 |   5 | 1.5  | 2010-05-09 14:02:43.818646 
    8 |   6 | 1.2.6 | 2010-05-09 14:01:17.632695 

więc ostateczne wyniki powinny rzeczywiście być sortowane tak:

id | parent_id | matpath |   created 
----+-----------+---------+---------------------------- 
    2 |   1 | 1  | 2010-05-08 15:18:37.987544 
    6 |   2 | 1.2  | 2010-05-08 17:50:43.288759 
    8 |   6 | 1.2.6 | 2010-05-09 14:01:17.632695 
    3 |   1 | 1  | 2010-05-08 17:38:14.125377 
    4 |   1 | 1  | 2010-05-08 17:38:57.26743 
    5 |   1 | 1  | 2010-05-08 17:43:28.211708 
    9 |   5 | 1.5  | 2010-05-09 14:02:43.818646 
    7 |   1 | 1  | 2010-05-08 18:18:11.849735 

Jak będę pracować, że obecnie? Czy mogę to zrobić w prostym SQL (to jest PostgreSQL 8.4), czy też należy dodać dodatkowe informacje do tej tabeli?

Aktualizacja: próbujesz lepiej wyjaśnić kryteria sortowania.

Wyobraź sobie, że id "1" to główny wpis na forum, a wszystko z "matpath" zaczynającym się od "1" jest dzieckiem tego wpisu. Tak więc ids od 2 do 5 to bezpośrednie odpowiedzi do 1 i uzyskanie ścieżek matematycznych z "1". Jednak id 6 jest odpowiedzią 2, a nie bezpośrednio na 1, więc otrzymuje matpath równy 1.2. Oznacza to, że za pomocą gwintowanego forum z prawidłowego zagnieżdżenia, ze wszystkimi identyfikatorami przedstawionych w tabelach, struktura forum będzie wyglądać tak, stąd wymóg zamawiającego:

* id 1 (root post) 
    * id 2 
     * id 6 
      * id 8 
    * id 3 
    * id 4 
    * id 5 
     * id 9 
    * id 7 

Answer 1

ja zazwyczaj utworzyć dodatkowy columnn do tego, nazywane coś w rodzaju SortPath. Zawierałaby dane, które trzeba sortować, łączone razem. Ta kolumna będzie typu varchar i zostanie posortowana jako ciąg znaków. Coś takiego:

id | parent_id | matpath |   created   |     sortpath 
---+-----------+---------+-----------------------------+-------------------------------------------------------------------------------------- 
2 |   1 | 1  | 2010-05-08 15:18:37.987544 | 2010-05-08 15:18:37.987544-2 
6 |   2 | 1.2  | 2010-05-08 17:50:43.288759 | 2010-05-08 15:18:37.987544-2.2010-05-08 17:50:43.288759-6 
8 |   6 | 1.2.6 | 2010-05-09 14:01:17.632695 | 2010-05-08 15:18:37.987544-2.2010-05-08 17:50:43.288759-6.2010-05-09 14:01:17.632695-8 
3 |   1 | 1  | 2010-05-08 17:38:14.125377 | 2010-05-08 17:38:14.125377-3 
4 |   1 | 1  | 2010-05-08 17:38:57.26743 | 2010-05-08 17:38:57.267430-4 
5 |   1 | 1  | 2010-05-08 17:43:28.211708 | 2010-05-08 17:43:28.211708-5 
9 |   5 | 1.5  | 2010-05-09 14:02:43.818646 | 2010-05-08 17:43:28.211708-5.2010-05-09 14:02:43.818646-9 
7 |   1 | 1  | 2010-05-08 18:18:11.849735 | 2010-05-08 18:18:11.849735-7 

Kilka rzeczy, aby pamiętać tutaj:

• sortpath będą klasyfikowane jako ciąg, więc ważne jest, wszystkie terminy mają taką samą długość dla jej prawidłowego sortowania. Np. Obserwuj, jak 2010-05-08 17:38:57.26743 ma dodane dodatkowe zero w kolumnie sortpath.
• Dołączyłem PK każdego węzła do końca jego daty. Jest tak, że jeśli masz dwa wiersze z dokładnie tą samą datą, zawsze zostaną one zwrócone w tej samej kolejności z powodu dodatkowych danych, które dodajemy.
• Dla mnie dane wyglądają asymetrycznie tak, jak je napisałem, ponieważ pokazujemy datę bieżącego węzła w sortpath, ale nie jest to w matpath. Wolałbym to zobaczyć w obu.
• Możesz również wstawić datę pierwszego identyfikatora węzła na początku każdego sortcolumn. Jest tak, że jeśli kiedykolwiek będziesz chciał zapytać o więcej niż jedno forum na raz (prawdopodobnie nie), to nadal będzie ono poprawnie sortowane.

Answer 2

Wierzę, że twoja zmaterializowana ścieżka nie jest właściwa.

Co logika nie można dostać się do sortowania rzeczy jak to

1 
1.2 
1 
1.5 

Dlaczego jest drugim 1 nie razem z pierwszym?

Jeśli miał

1 
1.2 
2 
2.5 

To byłoby trywialne.

EDYCJA: Spojrzałem na twój przykład i nie przechowujesz zmaterializowanej ścieżki rzędu, ale przechowujesz zmaterializowaną ścieżkę wiersza rodzica. Oto jak powinna wyglądać zmaterializowana ścieżka w rzędzie. Sortowanie bezpośrednio na matpath będzie działać, jeśli nie będzie miał więcej niż 9 oddziałów jeśli została zapisana jako:

id | parent_id | matpath |   created 
----+-----------+-----------+---------------------------- 
    2 |   1 | 1.2  | 2010-05-08 15:18:37.987544 
    6 |   2 | 1.2.6  | 2010-05-08 17:50:43.288759 
    8 |   6 | 1.2.6.8 | 2010-05-09 14:01:17.632695 
    3 |   1 | 1.3  | 2010-05-08 17:38:14.125377 
    4 |   1 | 1.4  | 2010-05-08 17:38:57.26743 
    5 |   1 | 1.5  | 2010-05-08 17:43:28.211708 
    9 |   5 | 1.5.9  | 2010-05-09 14:02:43.818646 
    7 |   1 | 1.7  | 2010-05-08 18:18:11.849735 

inaczej (> 9) trzeba by włączyć matpath w coś jak

001.002.006 
001.002.006.008 

która obsłużyłaby do 999 oddziałów.

Uwaga

• nawet podejście z 4 stałymi cyfr, takich jak 0001.0002.0006 nie daje pole, które jest krótsze niż w przyjętym odpowiedź
• można zanalizować matpath wartość sortowania produkują na bieżąco z funkcji użytkownika
• można bezpośrednio matpath zapisane w tym formacie (ma inne właściwości ładne, zbyt)

Answer 3

nie mogę myśleć o prosty sposób zrób to w prostym SQL. Zamiast ścieżki matpath użyję tutaj node_path. NODE_PATH jest matpath || „” || id

id | parent_id | node_path |   created   
----+-----------+---------+---------------------------- 
    2 |   1 | 1.2  | 2010-05-08 15:18:37.987544 
    3 |   1 | 1.3  | 2010-05-08 17:38:14.125377 
    4 |   1 | 1.4  | 2010-05-08 17:38:57.26743 
    5 |   1 | 1.5  | 2010-05-08 17:43:28.211708 
    7 |   1 | 1.7  | 2010-05-08 18:18:11.849735 
    6 |   2 | 1.2.6  | 2010-05-08 17:50:43.288759 
    9 |   5 | 1.5.9  | 2010-05-09 14:02:43.818646 
    8 |   6 | 1.2.6.8 | 2010-05-09 14:01:17.632695 

Teraz chcesz zamówić drzewo na podstawie NODE_PATH z pola sortowania zdefiniowanego przez liczbę razy uruchomionych sortowania.

Będzie działać niestandardowa funkcja rekursywna w plpgsql sorting na split_part (node_path, '.', Recursion_depth). Będziesz musiał sprawdzić wartości NULL z split_part (i zignorować je).

Answer 4

Nie jestem pewien, czy rozumiem, dlaczego przyjęte rozwiązanie ma jakikolwiek sens. Działa, ale jest jeszcze mniej znormalizowany i mniej wydajny (więcej miejsca na dysku, więcej indeksów itp.) Niż rozwiązanie @ Unreason (aby po prostu umieścić identyfikator w zmaterializowanej ścieżce).

Cały scenariusz, który twarze PO zdaje się wynikać z faktu, że, jak słusznie zauważa @Unason, implementacja zmaterializowanej ścieżki (MP) jest niepoprawna. OP dostarczył MP do rodzica, a nie do bieżącego węzła. W przyjętym rozwiązaniu kolumna SortPath koryguje to, dostarczając zmaterializowaną ścieżkę do bieżącego węzła (tym razem używając dat - dlaczego? - zamiast klucza podstawowego).

Dla porównania należy rozważyć następujące excerpt:

Materialized Path

W tym podejściu każdy rekord przechowuje całą ścieżkę do katalogu głównego. W naszym poprzednim przykładzie: załóżmy, że KING jest węzłem głównym. Następnie rekord z ename = 'SCOTT' jest połączony z katalogiem głównym za pomocą ścieżki SCOTT-> JONES-> KING. Współczesne bazy danych pozwalają reprezentować listę węzłów jako pojedynczej wartości, ale odkąd powstała zmaterializowana ścieżka została wynaleziona na długo przedtem, konwencja utknęła w prostej postaci ciąg węzłów połączonych z jakimś separatorem; najczęściej '.' lub "/".

Answer 5

Podczas gdy odpowiedź @ Unreason na temat wypełnienia działa, chciałbym zaoferować inne rozwiązanie, które moim zdaniem jest moim własnym wynalazkiem dla tego problemu.

Szukasz funkcji tworzenia bytestream, f(x)=b_1b_2..b_i (przepraszam nie MatJax na SO) gdzie b_i jest bajtem. Wiemy, że dwa bytestream porównuje to samo co pierwszy różny bajt. Chcemy takiej funkcji, która jest f(x)<f(y) iff x<y.

Wyściółka o tej samej długości z 0 zdecydowanie pozwala uzyskać ten cel. Biorąc dwie liczby, spójrz na pierwszy niezerowy bajt i tam jesteś.

Steven Wittens (acko.net) wprowadził inną sztuczkę do jądra Drupala jakieś osiem lat temu: wpisz liczbę cyfr przed ciągiem jako inną cyfrę. Tak więc liczba 97685 staje się znakami 5 9 7 6 8 5. To też działa: najpierw spójrz na bajt długości, jeśli nie są one takie same, to większy z pewnością będzie większy. Poza tym wiesz, że te dwie liczby są równej długości. Użył także liczb bazowych 36 z cyframi 0-9a-z, podobnie jak w przypadku heksadecymalnie dla każdej litery. To kodowanie wymaga dwóch bajtów dla pierwszych 36 węzłów, trzech dla następnych 1260 ...

Należy zauważyć, że ani dopełnianie, ani to sprytne kodowanie o zmiennej długości nie wymaga separatorów dla zmaterializowanej ścieżki, chociaż dla czytelności często są one uwzględniane.

numconv obsługuje kodowanie base85, ale wymaga sortowania z uwzględnieniem wielkości liter. Jest 94 znaków ASCII, jeśli usuniesz małe litery, ale nadal masz base68.

Ale jeśli używasz pola "binarnego", możesz zrobić base256: zamiast sprytnego kodowania po prostu wpisz liczbę jako serię bajtów, a następnie przedrostuj całość długością bajtów jako pojedynczym bajtem. Umożliwi to zakodowanie dowolnego drzewa mniejszego niż 2^2048 lub więcej. Dla pierwszych 256 węzłów używasz dwóch bajtów, dla następnej 65280 patrzysz na trzy bajty. To już jest dość wydajne.

Nominuję funkcję utf8encode(x). Rozważ to! Musisz zejść do bitsortingu zamiast bajtów, ale to nie zmienia wyniku: znajdź skrajny lewy bit od zera. Jeśli drugi ciąg ma 1, to będzie dłuższy kodowanie UTF-8, więc na pewno jest większy. Jeśli mają one pierwsze zero w tym samym miejscu, mamy te same ciągi bitów o długości, które są dla nas dobre.

To miło, ale co z separatorami. Algorytm UTF-8, gdy patrzy się na niego jako czysto algorytm tworzący strumienie bitowe, może obsłużyć liczby 31-bitowe - więc będzie działać dla drzew zawierających mniej niż dwa miliardy węzłów. Twoja zmaterializowana ścieżka będzie strumieniem bitów z kodowanych w UTF-8 liczb, które dobrze się porównują: Odrzuć lewostronne identyczne kodowane znaki UTF-8 i wróciliśmy do poprzedniego akapitu. co było do okazania

Ponieważ nie potrzebujemy separatorów ani bajtów prefiksów, możemy zakodować pierwsze 128 węzłów w jeden bajt, następnie następny 1920 w dwa bajty i maksymalnie 65535, trzy bajty. Dla czterech bajtów, base256 wygra. W przypadku naprawdę dużych drzew można traktować UTF-8 jako koder 0-2147483647 w strumieniu bajtów. Możesz więc użyć go jako kodowania base2147483647: D

Podsumowując: UTF-8 jest najlepszy dla małych drzewek i nie jest dużo gorszy niż podstawa256 poniżej dwóch miliardów węzłów. Poza tym aż 2^2048 lub tak przedrostek o długości -256 wygrywa. Poza tą podstawową bazą 2147483647 wygrywa i nie ma niczego poza tym.