Przechowywanie listy do ponownego zamówienia w bazie danych

Pracuję nad systemem list życzeń, w którym użytkownicy mogą dodawać elementy do różnych list życzeń, i zamierzam umożliwić użytkownikom ponowne zamówienie elementów w późniejszym terminie. Nie jestem do końca pewien, jak najlepiej przechować to w bazie danych, jednocześnie zachowując szybkość i nie zmieniając się w bałagan (ta aplikacja będzie używana przez dość dużą bazę użytkowników, więc nie chcę, aby spadła do czyszczenia rzeczy).

Początkowo próbowałem positionkolumny, ale wydaje się, że byłoby dość nieefektywne zmienianie wartości pozycji każdego innego elementu podczas przenoszenia.

Widziałem ludzi używających odsyłaczy do odniesienia do poprzedniej (lub następnej) wartości, ale znowu wydaje się, że musiałbyś zaktualizować całą masę innych pozycji na liście.

Innym rozwiązaniem, które widziałem, jest używanie liczb dziesiętnych i po prostu umieszczanie przedmiotów w przerwach między nimi, co wydaje się najlepszym rozwiązaniem do tej pory, ale jestem pewien, że musi być lepszy sposób.

Powiedziałbym, że typowa lista zawierałaby do około 20 przedmiotów i prawdopodobnie ograniczę ją do 50. Zmiana kolejności będzie polegała na przeciąganiu i upuszczaniu i prawdopodobnie zostanie wykonana partiami, aby zapobiec warunkom wyścigowym i tym podobne z żądania ajax. Używam postgres (na heroku), jeśli to ma znaczenie.

Czy ktoś ma jakieś pomysły?

Pozdrawiam za wszelką pomoc!

Po pierwsze, nie próbuj robić niczego sprytnego z liczbami dziesiętnymi, ponieważ będą cię na złość. REALi DOUBLE PRECISIONsą niedokładne i mogą niepoprawnie przedstawiać to, co w nich wkładasz. NUMERICjest dokładne, ale właściwa sekwencja ruchów zabraknie ci precyzji, a twoja implementacja źle się zepsuje.

Ograniczenie ruchów do pojedynczych wzlotów i upadków sprawia, że ​​cała operacja jest bardzo łatwa. Aby uzyskać listę kolejno ponumerowanych elementów, możesz przesunąć element w górę, zmniejszając jego pozycję i zwiększając numer pozycji niezależnie od tego, co wymyślił poprzedni dekrement. (Innymi słowy, poz 5stanie 4i jaki był przedmiot 4staje się 5skutecznie swap jak kretyni opisano w swojej odpowiedzi.) Przesuwając go byłoby odwrotnie. Indeksuj swoją tabelę według tego, co jednoznacznie identyfikuje listę i pozycję, i możesz to zrobić za pomocą dwóch UPDATEsekund w transakcji, która będzie przebiegać bardzo szybko. Chyba że użytkownicy zmieniają swoje listy z nadludzkimi prędkościami, nie spowoduje to dużego obciążenia.

Ruchy metodą „przeciągnij i upuść” (np. Przesuń element, 6aby usiąść między elementami 9i 10) są nieco trudniejsze i muszą być wykonane inaczej w zależności od tego, czy nowa pozycja znajduje się powyżej czy poniżej starej. W powyższym przykładzie musisz otworzyć dziurę, zwiększając wszystkie pozycje większe niż 9, aktualizując pozycję przedmiotu 6, aby była nowa, 10a następnie zmniejszając pozycję wszystkiego większego niż, 6aby wypełnić puste miejsce. Przy takim samym indeksowaniu, jak opisałem wcześniej, będzie to szybkie. Możesz faktycznie sprawić, że pójdzie to trochę szybciej niż to opisałem, minimalizując liczbę wierszy, które dotyka transakcja, ale jest to mikrooptymalizacja, której nie potrzebujesz, dopóki nie udowodnisz, że istnieje wąskie gardło.

Tak czy inaczej, próba prześcignięcia bazy danych za pomocą domowego, zbyt sprytnego rozwiązania na pół nie zwykle kończy się sukcesem. Bazy danych warte swojej soli zostały starannie napisane, aby wykonywać te operacje bardzo, bardzo szybko przez ludzi, którzy są w tym bardzo, bardzo dobrzy.

Ta sama odpowiedź tutaj https://stackoverflow.com/a/49956113/10608

Rozwiązanie: zrób indexłańcuch (ponieważ w zasadzie łańcuchy mają nieskończoną „dowolną precyzję”). Lub jeśli używasz int, zwiększaj indexo 100 zamiast 1.

Problem z wydajnością jest następujący: między dwoma posortowanymi elementami nie ma „pośrednich” wartości.

item      index
-----------------
gizmo     1
              <<------ Oh no! no room between 1 and 2.
                       This requires incrementing _every_ item after it
gadget    2
gear      3
toolkit   4
box       5

Zamiast tego zrób tak (lepsze rozwiązanie poniżej):

item      index
-----------------
gizmo     100
              <<------ Sweet :). I can re-order 99 (!) items here
                       without having to change anything else
gadget    200
gear      300
toolkit   400
box       500

Jeszcze lepiej: oto jak Jira rozwiązuje ten problem. Ich „ranga” (tak zwany indeks) jest wartością ciągu, która pozwala tonie oddychać pomiędzy pozycjonowanymi pozycjami.

Oto prawdziwy przykład bazy danych Jira, z którą pracuję

   id    | jira_rank
---------+------------
 AP-2405 | 0|hzztxk:
 ES-213  | 0|hzztxs:
 AP-2660 | 0|hzztzc:
 AP-2688 | 0|hzztzk:
 AP-2643 | 0|hzztzs:
 AP-2208 | 0|hzztzw:
 AP-2700 | 0|hzztzy:
 AP-2702 | 0|hzztzz:
 AP-2411 | 0|hzztzz:i
 AP-2440 | 0|hzztzz:r

Zwróć uwagę na ten przykład hzztzz:i. Zaletą rangi sznurkowej jest to, że zabraknie miejsca między dwoma przedmiotami, nadal nie musisz zmieniać rangi niczego innego. Po prostu zacznij dodawać więcej znaków do ciągu, aby zawęzić fokus.

Widziałem ludzi używających odsyłaczy do odniesienia do poprzedniej (lub następnej) wartości, ale znowu wydaje się, że musiałbyś zaktualizować całą masę innych pozycji na liście.

Dlaczego? Załóżmy, że stosujesz podejście do tabeli z listami połączonymi z kolumnami (listID, itemID, nextItemID).

Wstawienie nowego elementu do listy kosztuje jedną wstawkę i jeden zmodyfikowany wiersz.

Zmiana położenia przedmiotu kosztuje trzy modyfikacje wiersza (przenoszony element, element przed nim i element przed nową lokalizacją).

Usunięcie elementu kosztuje jedno usunięcie i jeden zmodyfikowany wiersz.

Koszty te pozostają takie same, niezależnie od tego, czy lista zawiera 10 pozycji, czy 10 000 pozycji. We wszystkich trzech przypadkach modyfikacja jest mniejsza, jeśli wiersz docelowy jest pierwszym elementem listy. Jeśli częściej operujesz na ostatnim elemencie listy, może być korzystne zapisanie prevItemID zamiast następnego.

„ale wydaje się, że byłoby to dość nieefektywne”

Czy mierzyć to? Czy to tylko zgadywanie? Nie rób takich założeń bez żadnego dowodu.

„20 do 50 pozycji na liście”

Szczerze mówiąc, to nie jest „dużo przedmiotów”, dla mnie to brzmi bardzo mało.

Proponuję trzymać się zasady „kolumny pozycji” (jeśli jest to najprostsza implementacja dla Ciebie). W przypadku tak małych list nie zaczynaj niepotrzebnej optymalizacji przed wystąpieniem prawdziwych problemów z wydajnością

To jest naprawdę kwestia skali i przypadku użycia ..

Ile oczekujesz pozycji na liście? Jeśli miliony, myślę, że gong dziesiętna trasa jest oczywista.

Jeśli 6, to numeracja liczb całkowitych jest oczywistym wyborem. s Również pytania dotyczą tego, w jaki sposób listy zostały uporządkowane. Jeśli używasz strzałek w górę i w dół (poruszanie się w górę lub w dół o jedno miejsce na raz), i użyłbym liczb całkowitych, a następnie zamieniłem się z poprzednim (lub następnym) w ruchu.

Jak często dokonujesz zmian, jeśli użytkownik może wprowadzić 250 zmian, to zatwierdzaj naraz, niż mówię liczby całkowite z ponowną numeracją ...

tl; dr: Potrzebujesz więcej informacji.

Edycja: „Listy życzeń” brzmią jak wiele małych list (założenie, że to może być fałsz). Więc mówię Integer z numeracją. (Każda lista zawiera własną pozycję)

Jeśli celem jest zminimalizowanie liczby operacji bazy danych na operację zmiany kolejności:

Przy założeniu, że

• Wszystkie elementy zakupów można wyliczyć za pomocą 32-bitowych liczb całkowitych.
• Istnieje limit maksymalnego rozmiaru listy życzeń użytkownika. (Widziałem, że niektóre popularne witryny wykorzystują 20–40 pozycji jako limit)

Przechowuj posortowaną listę życzeń użytkownika jako spakowaną sekwencję liczb całkowitych (tablic liczb całkowitych) w jednej kolumnie. Za każdym razem, gdy lista życzeń jest zmieniana, cała tablica (pojedynczy wiersz; pojedyncza kolumna) jest aktualizowana - co należy wykonać za pomocą pojedynczej aktualizacji SQL.

https://www.postgresql.org/docs/current/static/arrays.html

Jeśli cel jest inny, trzymaj się podejścia „kolumna pozycji”.

Jeśli chodzi o „szybkość”, należy przeprowadzić analizę porównawczą podejścia do procedury składowanej. Chociaż wydawanie ponad 20 oddzielnych aktualizacji dla jednego losowego losowania listy życzeń może być powolne, może być szybki sposób przy użyciu procedury składowanej.

OK. Ostatnio mam do czynienia z tym trudnym problemem, a wszystkie odpowiedzi w tym poście zadały wiele inspiracji. Z mojego punktu widzenia każde rozwiązanie ma swoje zalety i wady.

• Jeśli positionpole musi być sekwencyjne bez luk, wtedy w zasadzie będziesz musiał ponownie uporządkować całą listę. Jest to operacja O (N). Zaletą jest to, że po stronie klienta nie potrzeba żadnej specjalnej logiki, aby uzyskać zamówienie.

• Jeśli chcemy uniknąć operacji O (N), ALE JESZCZE utrzymujemy dokładną sekwencję, jednym z podejść jest użycie „odniesienia do siebie w odniesieniu do poprzedniej (lub następnej) wartości”. To jest scenariusz z listą powiązaną z podręcznikiem. Z założenia NIE spowoduje to „wielu innych pozycji na liście”. Wymaga to jednak po stronie klienta (usługi sieciowej lub aplikacji mobilnej) wdrożenia logiki przejścia listy powiązanej w celu uzyskania kolejności.

• Niektóre warianty nie wykorzystują odniesienia, tj. Listy połączonej. Wybierają reprezentowanie całego porządku jako samodzielnego obiektu blob, takiego jak tablica JSON w ciągu [5,2,1,3,...]; taka kolejność będzie następnie przechowywana w oddzielnym miejscu. Takie podejście ma również efekt uboczny polegający na wymaganiu od strony klienta kodu utrzymania tego oddzielnego obiektu blob zamówienia.

• W wielu przypadkach tak naprawdę nie musimy przechowywać dokładnej kolejności, musimy jedynie utrzymać względną pozycję w każdym rejestrze. Dlatego możemy dopuścić luki między kolejnymi rekordami. Odmiany obejmują: (1) użycie liczb całkowitych z lukami, takimi jak 100, 200, 300 ... ale szybko zabraknie braków, a następnie będziesz potrzebować procesu odzyskiwania; (2) przy użyciu liczb dziesiętnych z naturalnymi lukami, ale musisz zdecydować, czy możesz żyć z ewentualnym ograniczeniem precyzji; (3) używając rangi opartej na łańcuchach, jak opisano w tej odpowiedzi, ale uważaj na trudne pułapki implementacyjne .

• Prawdziwa odpowiedź może brzmieć „to zależy”. Ponownie sprawdź wymagania biznesowe. Na przykład, jeśli jest to system z listą życzeń, osobiście chętnie skorzystałbym z systemu organizowanego przez zaledwie kilka rang jako „must have”, „good-to-have”, „może-later”, a następnie prezentowałem przedmioty bez szczególnych porządek wewnątrz każdej rangi. Jeśli jest to system dostarczania, możesz bardzo dobrze wykorzystać czas dostawy jako przybliżoną pozycję, która ma naturalną lukę (i naturalne zapobieganie konfliktom, ponieważ żadna dostawa nie nastąpiłaby w tym samym czasie). Twój przebieg może się różnić.

Użyj liczby zmiennoprzecinkowej dla kolumny pozycji.

Następnie możesz zmienić kolejność listy, zmieniając tylko kolumnę pozycji w wierszu „przeniesionym”.

Zasadniczo, jeśli użytkownik chce ustawić „czerwony” po „niebieskim”, ale przed „żółtym”

Musisz po prostu obliczyć

red.position = ((yellow.position - blue.position) / 2) + blue.position

Po kilku milionach zmian pozycji liczby zmiennoprzecinkowe mogą być tak małe, że nie ma „pomiędzy” - ale jest to tak samo prawdopodobne, jak zobaczenie jednorożca.

Możesz to zaimplementować za pomocą pola liczb całkowitych z początkową przerwą, powiedzmy 1000. Tak więc początkowe oreringowanie byłoby 1000-> niebieski, 2000-> Żółty, 3000-> Czerwony. Po „przesunięciu” koloru czerwonego po niebieskim miałbyś 1000-> niebieski, 1500-> czerwony, 2000-> żółty.

Problem polega na tym, że przy pozornie dużej początkowej luce wynoszącej 1000, zaledwie 10 ruchów doprowadzi cię do sytuacji takiej jak 1000-> niebieski, 1001-puce, 1004-> biege ...... gdzie nie będziesz już w stanie wstawić cokolwiek po „niebieskim” bez ponownego numerowania całej listy. Używając liczb zmiennoprzecinkowych, zawsze będzie punkt „w połowie” między dwiema pozycjami.