Arbitralnie porządkuje rekordy w tabeli

Częstą potrzebą korzystania z bazy danych jest uzyskiwanie dostępu do rekordów w kolejności. Na przykład, jeśli mam blog, chcę móc zmieniać kolejność moich postów na blogu w dowolnej kolejności. Wpisy te często mają wiele relacji, więc relacyjna baza danych wydaje się mieć sens.

Typowym rozwiązaniem, które widziałem, jest dodanie kolumny liczb całkowitych order:

CREATE TABLE AS your_table (id, title, sort_order)
AS VALUES
  (0, 'Lorem ipsum',   3),
  (1, 'Dolor sit',     2),
  (2, 'Amet, consect', 0),
  (3, 'Elit fusce',    1);

Następnie możemy posortować wiersze, orderaby uporządkować je we właściwej kolejności.

Jednak wydaje się to niezdarne:

• Jeśli chcę przenieść rekord 0 na początek, muszę zmienić kolejność każdego rekordu
• Jeśli chcę wstawić nowy rekord na środku, muszę zmienić kolejność każdego rekordu po nim
• Jeśli chcę usunąć rekord, muszę zmienić kolejność każdego rekordu po nim

Łatwo jest wyobrazić sobie takie sytuacje, jak:

• Dwie płyty mają to samo order
• orderPomiędzy rekordami występują luki

Może się to zdarzyć dość łatwo z wielu powodów.

Takie podejście przyjmują aplikacje takie jak Joomla:

Można argumentować, że tutaj interfejs jest zły i że zamiast ludzi bezpośrednio edytujących liczby, powinni używać strzałek lub przeciągania i upuszczania - i prawdopodobnie masz rację. Ale za kulisami dzieje się to samo.

Niektóre osoby zaproponowały użycie miejsca dziesiętnego do przechowywania zamówienia, dzięki czemu można użyć „2,5”, aby wstawić rekord między rekordami w kolejności 2 i 3. I choć to trochę pomaga, jest to prawdopodobnie jeszcze bardziej bałagan, ponieważ możesz skończyć z dziwne miejsca po przecinku (gdzie się zatrzymujesz? 2,75? 2,875? 2,8125?)

Czy istnieje lepszy sposób na przechowywanie zamówień w tabeli?

Jeśli chcę przenieść rekord 0 na początek, muszę zmienić kolejność każdego rekordu

Nie, jest prostszy sposób.

update your_table
set order = -1 
where id = 0;

Jeśli chcę wstawić nowy rekord na środku, muszę zmienić kolejność każdego rekordu po nim

To prawda, chyba że użyjesz typu danych, który obsługuje wartości „pomiędzy”. Typy zmiennoprzecinkowe i numeryczne pozwalają zaktualizować wartość, powiedzmy, do 2,5. Ale varchar (n) też działa. (Pomyśl „a”, „b”, „c”; następnie pomyśl „ba”, „bb”, „bc”.)

Jeśli chcę usunąć rekord, muszę zmienić kolejność każdego rekordu po nim

Nie, jest prostszy sposób. Po prostu usuń wiersz. Pozostałe wiersze nadal będą poprawnie sortowane.

Łatwo jest wyobrazić sobie takie sytuacje, jak:

Dwa rekordy mają tę samą kolejność

Unikalne ograniczenie może temu zapobiec.

Pomiędzy rekordami występują luki w kolejności

Luki nie mają wpływu na sposób sortowania wartości w kolumnie przez dbms.

Niektóre osoby zaproponowały użycie miejsca dziesiętnego do przechowywania zamówienia, dzięki czemu można użyć „2,5”, aby wstawić rekord między rekordami w kolejności 2 i 3. I choć to trochę pomaga, jest to prawdopodobnie jeszcze bardziej bałagan, ponieważ możesz skończyć z dziwne miejsca po przecinku (gdzie się zatrzymujesz? 2,75? 2,875? 2,8125?)

Nie przestajesz, dopóki nie musisz . W dbms nie ma problemu z sortowaniem wartości, które mają 2, 7 lub 15 miejsc po przecinku.

Myślę, że twoim prawdziwym problemem jest to, że chciałbyś widzieć wartości w posortowanej kolejności jako liczby całkowite. Możesz to zrobić.

create table your_table (
  id int primary key, 
  title varchar(13), 
  sort_order float
);

insert into your_table values
(0, 'Lorem ipsum', 2.0),
(1, 'Dolor sit', 1.5),
(2, 'Amet, consect', 0.0),
(3, 'Elit fusce', 1.0);

-- This windowing function will "transform" the floats into sorted integers.
select id, title,
       row_number() over (order by sort_order)
from your_table

To bardzo proste. Musisz mieć strukturę „dziury liczności”:

Musisz mieć 2 kolumny:

1. pk = 32bit integer
2. zamówienie = 64bit bigint( nie double )

Wstaw / aktualizuj

1. Wstawiając pierwszy nowy rekord, ustaw order = round(max_bigint / 2).
2. Podczas wstawiania na początku tabeli ustaw order = round("order of first record" / 2)
3. Wstawiając na końcu tabeli ustaw order = round("max_bigint - order of last record" / 2) 4) Wstawiając na środku ustaworder = round("order of record before - order of record after" / 2)

Ta metoda ma bardzo dużą liczność. Jeśli masz błąd ograniczenia lub uważasz, że masz niewielką liczność, możesz odbudować kolumnę zamówienia (normalizować).

W maksymalnej sytuacji z normalizacją (z tą strukturą) możesz mieć „otwór kardynalności” w 32 bitach.

Pamiętaj, aby nie używać typów zmiennoprzecinkowych - kolejność musi być dokładną wartością!

Ogólnie rzecz biorąc, zamawianie odbywa się zgodnie z pewnymi informacjami zawartymi w aktach, tytule, dowodzie osobistym lub czymkolwiek odpowiednim dla danej sytuacji.

Jeśli potrzebujesz specjalnego zamówienia, użycie kolumny liczb całkowitych nie jest tak złe, jak mogłoby się wydawać. Na przykład, aby zrobić miejsce na płytę zajmującą 5. miejsce, możesz zrobić coś takiego:

update table_1 set place = place + 1 where place > 5.

Mamy nadzieję, że możesz zadeklarować kolumnę uniquei być może mieć procedurę, dzięki której przegrupowania będą „atomowe”. Szczegóły zależą od systemu, ale taki jest ogólny pomysł.

… Jest to prawdopodobnie jeszcze bardziej bałagan, ponieważ możesz skończyć z dziwnymi miejscami po przecinku (gdzie się zatrzymujesz? 2,75? 2,875? 2,8125?)

Kogo to obchodzi? Liczby te są dostępne tylko dla komputera, więc nie ma znaczenia, ile cyfr ułamkowych mają i jak brzydko nam się wydają.

Użycie wartości dziesiętnych oznacza, że ​​aby przenieść element F między elementami J i K, wystarczy wybrać wartości porządkowe dla J i K, a następnie uśrednić je, a następnie zaktualizować F. Dwie instrukcje SELECT i jedna instrukcja UPDATE (prawdopodobnie wykonano to przy użyciu izolacji możliwej do serializacji, aby uniknąć zakleszczenia).

Jeśli chcesz zobaczyć na wyjściu liczby całkowite, a nie ułamki, oblicz wartości całkowite w aplikacji klienta lub użyj funkcji ROW_NUMBER () lub RANK () (jeśli zawiera je RDBMS).

W moim projekcie planuję wypróbować rozwiązanie podobne do rozwiązania liczb dziesiętnych, ale zamiast tego użyć tablic bajtowych:

def pad(x, x_len, length):
    if x_len >= length:
        return x
    else:
        for _ in range(length - x_len):
            x += b"\x00"
        return x

def order_index(_from, _to, count, length=None):
    assert _from != _to
    assert _from < _to

    if not length:
        from_len = len(_from)
        to_len = len(_to)
        length = max(from_len, to_len)

        _from = pad(_from, from_len, length)
        _to = pad(_to, to_len, length)

    from_int = int.from_bytes(_from, "big")
    to_int = int.from_bytes(_to, "big")
    inc = (to_int - from_int)//(count + 1)
    if not inc:
        length += 1
        _from += b"\x00"
        _to += b"\x00"
        return order_index(_from, _to, count, length)

    return (int.to_bytes(from_int + ((x+1)*inc), length, "big") for x in range(count))

>>> index = order_index(b"A", b"Z", 24)
>>> [x for x in index]
[b'B', b'C', b'D', b'E', b'F', b'G', b'H', b'I', b'J', b'K', b'L', b'M', b'N', b'O', b'P', b'Q', b'R', b'S', b'T', b'U', b'V', b'W', b'X', b'Y']
>>> 
>>> index = order_index(b"A", b"Z", 25)
>>> [x for x in index]
[b'A\xf6', b'B\xec', b'C\xe2', b'D\xd8', b'E\xce', b'F\xc4', b'G\xba', b'H\xb0', b'I\xa6', b'J\x9c', b'K\x92', b'L\x88', b'M~', b'Nt', b'Oj', b'P`', b'QV', b'RL', b'SB', b'T8', b'U.', b'V$', b'W\x1a', b'X\x10', b'Y\x06']

Chodzi o to, że nigdy nie możesz zabraknąć możliwych wartości pośrednich, ponieważ po prostu dołączasz znak b"\x00"do odpowiednich rekordów, jeśli potrzebujesz więcej wartości. (nie intma ograniczeń w Pythonie 3, w przeciwnym razie musiałbyś wybrać kawałek bajtów na końcu, aby porównać, przy założeniu, że między dwiema sąsiednimi wartościami różnice byłyby upakowane pod koniec.)

Na przykład, że masz dwa rekordy, b"\x00"a b"\x01", a chcesz rekord przejść między nimi. Nie ma żadnych dostępnych wartości między 0x00i 0x01, więc dołączasz je b"\x00"do obu, a teraz masz kilka wartości między nimi, których możesz użyć do wstawienia nowych wartości.

>>> records = [b"\x00", b"\x01", b"\x02"]
>>> values = [x for x in order_index(records[0], records[1], 3)]
>>> records = records + values
>>> records.sort()
>>> records
[b'\x00', b'\x00@', b'\x00\x80', b'\x00\xc0', b'\x01', b'\x02']

Baza danych może łatwo to posortować, ponieważ wszystko kończy się w porządku leksykograficznym. Jeśli usuniesz rekord, nadal jest w porządku. W moim projekcie utworzyłem b"\x00"i b"\xff"jako FIRSToraz LASTrekordy, aby użyć ich jako wirtualnych wartości „od” i „do” do dodania / dodania nowych rekordów:

>>> records = []
>>> value = next(order_index(FIRST, LAST, 1))
>>> value
b'\x7f'
>>> records.append(value)
>>> value = next(order_index(records[0], LAST, 1))
>>> value
b'\xbf'
>>> records.append(value)
>>> records.sort()
>>> records
[b'\x7f', b'\xbf']
>>> value = next(order_index(FIRST, records[0], 1))
>>> value
b'?'
>>> records.append(value)
>>> records.sort()
>>> records
[b'?', b'\x7f', b'\xbf']

Znalazłem tę odpowiedź znacznie lepiej. Cytując to w całości:

Bazy danych są zoptymalizowane pod kątem niektórych rzeczy. Jednym z nich jest szybka aktualizacja wielu wierszy. Staje się to szczególnie prawdziwe, gdy baza danych wykonuje swoją pracę.

Rozważać:

order song
1     Happy Birthday
2     Beat It
3     Never Gonna Give You Up
4     Safety Dance
5     Imperial March

I chcesz przejść Beat Itdo końca, będziesz mieć dwa zapytania:

update table 
  set order = order - 1
  where order >= 2 and order <= 5;

update table
  set order = 5
  where song = 'Beat It'

I to wszystko. To skaluje się bardzo dobrze przy bardzo dużych liczbach. Spróbuj umieścić kilka tysięcy utworów na hipotetycznej liście odtwarzania w bazie danych i sprawdź, ile czasu zajmuje przeniesienie utworu z jednego miejsca do drugiego. Ponieważ mają one bardzo znormalizowane formy:

update table 
  set order = order - 1
  where order >= ? and order <= ?;

update table
  set order = ?
  where song = ?

Masz dwa przygotowane oświadczenia, które możesz bardzo efektywnie wykorzystać.

Daje to pewne znaczące zalety - kolejność tabeli jest czymś, o czym możesz racjonalnie myśleć. Trzecia piosenka maorder zawsze 3. Jedynym sposobem na zagwarantowanie tego jest użycie kolejnych liczb całkowitych jako kolejności. Użycie pseudo-połączonych list lub liczb dziesiętnych lub liczb całkowitych z przerwami nie pozwoli Ci zagwarantować tej właściwości; w takich przypadkach jedynym sposobem na zdobycie n-tej piosenki jest posortowanie całej tabeli i uzyskanie n-tej płyty.

I naprawdę jest to o wiele łatwiejsze, niż się wydaje. Łatwo jest ustalić, co chcesz zrobić, wygenerować dwie instrukcje aktualizacji, a inni ludzie mogą przejrzeć te dwie instrukcje aktualizacji i zorientować się, co się dzieje.