Наиболее подходящая структура данных для упорядоченного списка в РСУБД? - PullRequest
Новая
       12

Наиболее подходящая структура данных для упорядоченного списка в РСУБД?

6 голосов
/ 25 июня 2009

Я храню упорядоченный список из нескольких миллионов элементов в базе данных MySQL. Разумно часто, элементы должны быть добавлены или удалены из списка; одинаково часто, позиция в списке пункта должна быть определена. Я бы сказал, что соотношение чтения / записи составляет около 50: 50.

Начиная с модели со связанным списком, я прочитал [1] и различные модели, обсуждаемые там. Для строгого связного списка модель списка смежности работала бы просто отлично, но, поскольку отношение чтения / записи более или менее одинаково, я выбрал подход «разделяй и властвуй», используя стандартные смежные списки:

Разделите весь список на «сегменты» приблизительной длины (скажем, ~ 10000), сохраняя индекс размеров сегментов и их относительное положение в основном списке. Каждый элемент назначается определенному сегменту и отслеживает его положение в этом сегменте.

При таком подходе позиция элемента определяется путем суммирования размеров сегментов, которые предшествовали сегменту элемента в списке, а затем добавления позиции элемента в его собственный сегмент. Чтобы вставить / удалить элемент из списка, «сдвиг» получаемых элементов локализуется в сегменте, в который элемент добавляется или удаляется; размер этого ведра также должен быть соответствующим образом обновлен.

В этом подходе есть некоторая денормализация (размеры сегментов), и она не является поточно-ориентированной, даже с транзакциями, потому что во время удаления / вставки таблица элементов должна запрашиваться для определения позиции сегмента элемента изменяются, а затем обновляются, чтобы выполнить «сдвиг» для всех других элементов в корзине этого элемента. Если только эти действия не являются атомарными (возможно, через хранимую процедуру?), Потоки постоянно тупиковые.

Существуют ли еще подходы к хранению данных такого типа в СУБД? Проблема безопасности потоков вызывает у меня сильную головную боль, и кажется, что должен быть лучший способ решить эту проблему, чем заставлять меня использовать хранимые процедуры.

Большое спасибо, Matt.

[1] Структура базы данных для древовидной структуры данных

1 Ответ

1 голос
/ 25 июня 2009

Если вам нужен связанный список (не иерархия), вы можете просто использовать подход, описанный в этой статье в моем блоге:

, с помощью этого простого запроса: 

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

Убедитесь, что ваши id и parent имеют индексы UNIQUE, определенные для того, чтобы это было эффективным.

Замените @r := 0 на @r := @id_of_record_to_start_with, чтобы начать просмотр с любого заданного id.

Чтобы узнать позицию элемента, просто переверните запрос: 

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
...