Jak zaprojektować bazę danych do przechowywania posortowanej listy?

Chcę przechowywać posortowaną listę w bazie danych. Chcę wydajnie wykonać następujące operacje.

1. Wstaw (x) - Wstaw rekord x do tabeli
2. Usuń (x) - Usuń rekord x z tabeli
3. Przed (x, n) - zwraca rekordy „n” poprzedzające rekord x na posortowanej liście.
4. Po (x, n) - zwraca rekordy „n” następujące po rekordzie x z posortowanej listy.
5. Pierwszy (n) - Zwraca pierwsze rekordy „n” z posortowanej listy.
6. Last (n) - Zwraca ostatnie „n” rekordy z posortowanej listy.
7. Porównaj (x, y) - Biorąc pod uwagę dwa rekordy xiy z tabeli, sprawdź, czy x> y.

Prostą metodą, o której mógłbym pomyśleć, jest zapisanie w tabeli i zapytaniu jakiegoś atrybutu „ranga” poprzez sortowanie według tego atrybutu. Ale w tej metodzie wstawianie / modyfikowanie rekordu o randze staje się kosztowną operacją. Czy istnieje lepsza metoda?

W szczególności chcę zaimplementować tabelę za pomocą SimpleDB firmy Amazon. Ale ogólna odpowiedź na relacyjną bazę danych również powinna być pomocna.

Aktualizacja profilu obciążenia:

Ponieważ planuję to dla aplikacji internetowej, zależy to od liczby użytkowników korzystających z aplikacji.

Jeśli jest 100 000 aktywnych użytkowników (super optymizm: P), to mój bardzo przybliżony szacunek na dzień

500k wybiera, 100k wstawia i usuwa, 500k aktualizacji

Spodziewałbym się, że stół wzrośnie do 500 tys.

Chcę zoptymalizować operacje aktualizacji, wstawiania i porównywania. Ranga przedmiotów będzie się ciągle zmieniać i muszę aktualizować tabelę.

Jeśli ranga nie jest całkowicie arbitralna, ale można ją wyprowadzić z innej własności (np. Imię, wynik gracza itp.), Przyjrzyj się odpowiedzi Joela .

Jeśli jest to dowolna właściwość twoich danych, to powinna być przechowywana jako kolumna w twojej tabeli rekordów. Zakładając, że Amazon SimpleDB jest podobny do typowego RDBMS, możesz następnie zindeksować tę kolumnę i szybko zaspokoić wszystkie powyższe zapytania za pomocą odpowiedniej strategii indeksowania. Jest to normalne w przypadku RDBMS.

Biorąc pod uwagę, że oczekujesz wysokiej aktywności wstawiania i aktualizacji, ale także stosunkowo wysokiej aktywności odczytu, zalecam wykonanie następujących czynności:

• Zgromadź tabelę na poziomie, szczególnie jeśli zdecydowana większość twoich zapytań jest przeciwna randze. Jeśli nie, lub jeśli wybranie klucza klastrowania nie jest dostępne w SimpleDB, po prostu utwórz indeks z rangą jako wiodącą kolumną. Spełniałoby to zapytania 3-6.
• Indeks najpierw rekordu, a następnie rangi (lub, w świecie SQL Server, po prostu zapisz i INCLUDE-ing rangę, lub po prostu zapisz, jeśli masz klastrowane rangi) spełniłby zapytanie 7.
• Operacje 1 i 2 można zoptymalizować, odpowiednio rozdzielając dane (tj. Ustawiając FILLFACTORw SQL Server). Jest to szczególnie ważne, jeśli skupisz się na rankingu.
• Wstawiając lub aktualizując rangi, zachowaj jak największą lukę między numerami rang, aby zminimalizować możliwość zmiany rangi istniejącego rekordu, aby uwzględnić wstawienie lub aktualizację rang. Na przykład, jeśli uszeregujesz swoje rekordy w krokach co 1000, pozostawisz wystarczająco dużo miejsca na około połowę tylu zmian i wkładek z minimalną szansą, będziesz musiał zmienić pozycję rekordu, który nie jest bezpośrednio zaangażowany w te zmiany.
• Każdej nocy zmieniaj rangę wszystkich rekordów, aby wyzerować odstępy między nimi.
• Możesz dostroić częstotliwość masowych ponownych rankingów, a także rozmiar odstępu w rankingu, aby uwzględnić oczekiwaną liczbę wstawek lub aktualizacji w stosunku do liczby istniejących rekordów. Więc jeśli masz 100 000 rekordów i spodziewasz się, że twoje wstawki i aktualizacje będą stanowić 10% tego, zostaw wystarczająco dużo miejsca na 10 000 nowych rang i zmieniaj rangę co noc.
• Zmiana rankingu rekordów 500 000 jest kosztowną operacją, ale dla takich baz danych taka operacja powinna być odpowiednia raz dziennie lub w tygodniu poza godzinami pracy. To przesunięcie masy poza godzinami pracy, aby utrzymać luki w rankingach, pozwala zaoszczędzić Ci konieczności zmiany rankingu wielu rekordów dla każdej aktualizacji lub wstawienia rankingu w godzinach normalnych i szczytowych.

Jeśli spodziewasz się, że 100K + odczytów na stole o wielkości 100K + nie polecam podejścia z listą połączoną. Nie będzie dobrze skalować do tych rozmiarów.

Ogólnie używam opisanej przez ciebie metody „rangi”. Zamiast kłopotać się aktualizowaniem wierszy, gdy trzeba było zmienić kolejność elementów, często mogłem uciec od usunięcia wszystkich rekordów z listy i ponownego wstawienia nowych elementów w odpowiedniej kolejności. Ta metoda jest wyraźnie zoptymalizowana do wyszukiwania.

Alternatywnym podejściem byłoby modelowanie rekordów jako połączonej listy przy użyciu kolumny tabeli klucza zwrotnego „poprzednik” w tabeli:

ID   setID   item       predecessor
---  ------  ------     ------------
1    1       Apple      null
2    1       Orange     1
3    2       Cucumber   null
4    1       Pear       2
5    1       Grape      4
6    2       Carrot     3

Możesz łatwo pobrać listę oraz dodawać i usuwać elementy przy niewielkim obciążeniu, ale uporządkowanie rekordów we właściwej kolejności będzie trudne. Być może istnieje sprytny sposób na zrobienie tego w jednym zapytaniu, prawdopodobnie z dużą ilością aliasowanych połączeń tabel.

Tego drugiego podejścia często używam, gdy modeluję relację typu drzewo (kategorie, foldery, zestawy i podzbiory). Generalnie miałem jakąś funkcję rekurencyjną, aby zrekonstruować pełne drzewo w mojej aplikacji.

Myślę, że należy przechowywać właściwość lub właściwości używane do obliczenia rangi, a następnie zbudować nad nimi indeks. Zamiast próbować zmusić bazę danych do fizycznego przechowywania danych w uporządkowanej kolejności lub za pomocą ręcznie zarządzanej połączonej listy, dlaczego nie pozwolić silnikowi bazy danych robić to, do czego został przeznaczony?

Są to ograniczenia nieobsługiwane przez RDBMS, takie jak simpleDB. Wymaganych funkcji nie można zaimplementować po stronie DB w simpleDB, należy je zaimplementować od strony programowania / aplikacji.

W przypadku RDBMS SQL serverwymagane funkcje są podstawowe dla indeksu klastrowego.

• Wstaw (x) - Wstaw rekord x do tabeli> Prosta wstawka.
• Usuń (x) - Usuń rekord x z tabeli> Proste usuwanie.

• Przed (x, n) - zwraca rekordy „n” poprzedzające rekord x na posortowanej liście. > Wybierz najlepsze n wyników, gdzie x mniej niż wartość i uporządkuj według klauzuli.

• Po (x, n) - zwraca rekordy „n” następujące po rekordzie x z posortowanej listy. > Wybierz najlepsze n wyników, gdzie x jest większe od wartości i uporządkuj według klauzuli.

• Pierwszy (n) - Zwraca pierwsze rekordy „n” z posortowanej listy. > Wybierz najlepsze n wyników.

• Last (n) - Zwraca ostatnie „n” rekordy z posortowanej listy. > Wybierz najlepsze n wyników po zamówieniu według opisu.

• Porównaj (x, y) - Biorąc pod uwagę dwa rekordy xiy z tabeli, sprawdź, czy x> y. > Instrukcja IFSQL.

Oto, czego użyłem, aby zmienić ranking mojej tabeli Postgres po każdej wstawce:

CREATE OR REPLACE FUNCTION re_rank_list() RETURNS trigger AS $re_rank_list$
DECLARE
    temprow record;
    row_idx integer := 1;    
BEGIN
    FOR temprow IN
    SELECT * FROM your_schema.your_list WHERE list_id = NEW.list_id ORDER BY rank ASC
    LOOP
        UPDATE your_schema.your_list SET rank = row_idx * 100 WHERE id = temprow.id;
        row_idx := row_idx + 1;
    END LOOP;
    RETURN NEW;
END;
$re_rank_list$ LANGUAGE plpgsql;


CREATE TRIGGER re_rank_list AFTER UPDATE ON your_schema.your_list_value
    FOR EACH ROW 
    WHEN (pg_trigger_depth() = 0)
    EXECUTE PROCEDURE re_rank_list();

W moim przypadku użycia wydajność nie jest problemem, ale pewność, że nigdy się nie złamie lub nie zadziała, jest ważna.