Najbardziej odpowiednia struktura danych dla uporządkowanej listy w RDBMS?

Question

Przechowuję uporządkowaną listę kilku milionów pozycji w bazie danych MySQL. Raczej często trzeba dodawać lub usuwać przedmioty z listy; równie często należy określić pozycję na liście przedmiotu. Powiedziałbym, że stosunek odczytu do zapisu wynosi około 50:50.

Zaczynając od modelu z listą odsyłaczy, czytam [1] i różne omówione tam modele. W przypadku ścisłej listy połączonej model listy przyległej działałby dobrze, ale ponieważ stosunek odczytu/zapisu jest mniej więcej równy, wybrałem metodę dzielenia i podbijania przy użyciu standardowych list ciągłych:

Podziel całą listę do "kubełków" o przybliżonej długości (na przykład ~ 10000), zachowując indeks rozmiarów kubełków i ich względną pozycję na głównej liście. Każdy element jest przypisany do konkretnego zasobnika i śledzi jego pozycję w tym wiadrze.

Przy takim podejściu pozycję przedmiotu określa się przez zsumowanie rozmiarów segmentów, które poprzedzają pozycję elementu na liście, a następnie dodanie pozycji elementu do jego własnego zasobnika. Aby wstawić/usunąć pozycję z listy, "przesunięcie" pozycji, która jest wynikiem, jest zlokalizowane w wiadrze, do którego element jest dodawany lub usuwany; rozmiar tego kubełka również musi zostać odpowiednio zaktualizowany.

Istnieją pewne Denormalizacja w tym podejściu (wiadro rozmiarach), a to nie jest z natury wątku bezpieczny, nawet z transakcji, ponieważ podczas usunąć/wstawić tabelę pozycji musi być sprawdzony, aby ustalić pozycję wiadro z następujących element jest modyfikowany, a następnie aktualizowany, aby wykonać "przesunięcie" na wszystkich pozostałych elementach w tym elemencie. Dopóki te działania nie są atomowe (może za pośrednictwem procedury przechowywanej?) Wątki konsekwentnie zakleszczają.

Czy istnieją bardziej uzasadnione podejścia do utrzymywania tego rodzaju danych w RDBMS? Problem związany z bezpieczeństwem wątków powoduje duży ból głowy i wydaje mi się, że powinien istnieć lepszy sposób rozwiązania tego problemu, niż zmuszenie mnie do zastosowania procedur przechowywanych.

Wielkie dzięki, Matt.

[1] Database Structure for Tree Data Structure

Answer 1

Jeśli potrzebujesz połączonej listy (nie hierarchii), można po prostu użyć podejścia opisanego w tym artykule w moim blogu:

• Sorting lists

, z tym prostym zapytaniem:

SELECT @r AS _parent, 
     @r := (
     SELECT id 
     FROM t_list 
     WHERE parent = _parent 
     ) AS id 
FROM (
     SELECT @r := 0 
     ) vars, 
     t_list 

Upewnij się, że zdefiniowane w tym celu indeksy id i parent mają być wydajne.

Zamień @r := 0 na @r := @id_of_record_to_start_with, aby rozpocząć przeglądanie z dowolnego id.

Aby dowiedzieć się pozycję elementu, po prostu odwrócić zapytanie:

SELECT COUNT(*) 
FROM (
     SELECT @r AS _id, 
       @r := (
       SELECT parent 
       FROM t_list 
       WHERE id = _id 
       ) AS id 
     FROM (
       SELECT @r := @item_id 
       ) vars, 
       t_list 
     ) q