Как хранить заказанную информацию в реляционной базе данных

20

Я пытаюсь понять, как правильно хранить упорядоченную информацию в реляционной базе данных.

Пример:

Скажем, у меня есть плейлист, состоящий из песен. Внутри моей реляционной базы данных у меня есть таблица Playlists, содержащая некоторые метаданные (имя, создатель и т. Д.). У меня также есть таблица с именем Songs, playlist_idа также информация о песне (имя, исполнитель, продолжительность и т. Д.).

По умолчанию, когда новая песня добавляется в список воспроизведения, она добавляется в конец. При заказе на Song-ID (по возрастанию), порядок будет порядок добавления. Но что если пользователь сможет переупорядочить песни в плейлисте?

Я выдвинул пару идей, каждая из которых имела свои преимущества и недостатки:

  1. Столбец с именем order, который является целым числом . Когда песня перемещается, порядок всех песен между ее старым и новым положением изменяется, чтобы отразить это изменение. Недостатком этого является то, что каждый раз, когда песня перемещается, нужно выполнять множество запросов, и алгоритм перемещения не такой тривиальный, как с другими опциями.
  2. Столбец с именем order, который является десятичным ( NUMERIC). Когда песня перемещается, ей присваивается значение с плавающей запятой между двумя соседними числами. Недостаток: десятичные поля занимают больше места, и, возможно, из-за них может не хватить точности, если только не будут приняты меры по перераспределению диапазона после каждых нескольких изменений.
  3. Другим способом было бы иметь previousи nextполе, которое ссылается на другие песни. (или имеют значение NULL в случае с первой, или последней песней в списке воспроизведения прямо сейчас; в основном вы создаете связанный список ). Недостаток: запросы типа «найти X-ую песню в списке» больше не являются постоянными, а имеют линейное время.

Какая из этих процедур чаще всего используется на практике? Какая из этих процедур является самой быстрой в средних и больших базах данных? Есть ли другие способы архивировать это?

РЕДАКТИРОВАТЬ: для простоты, в примере песня принадлежит только одному списку воспроизведения (отношение многие-к-одному). Конечно, можно также использовать Junction Table, чтобы song⟷playlist был отношением «многие ко многим» (и примените одну из вышеуказанных стратегий к этой таблице).

Qqwy
источник
1
Вы можете использовать первый вариант (порядок как целое число) с 100 шагами. Тогда вам не нужно переупорядочивать, если вы перемещаете одну песню, просто возьмите значение между 100. Время от времени вам может понадобиться новое перенумерация, чтобы получить снова пропуски между песнями.
Кнут
4
«Недостатком этого является то, что каждый раз, когда песня перемещается, нужно выполнять множество запросов» ?! - update songorder set order = order - 1 where order >= 12 & order <= 42; update songorder set order = 42 where id = 123;это два обновления - не тридцать. Три, если вы хотите наложить уникальное ограничение на порядок.
2
Используйте первый вариант, если вы не уверены, что вам нужно что-то еще. Одна из проблем, с которыми сталкиваются программисты, плохо знакомые с базами данных, заключается в непонимании того, что базы данных очень, очень хороши в подобных вещах. Не бойтесь ставить свою базу данных на работу.
GrandmasterB
1
Queries like 'find the Xth Song in the list' are no longer constant-timeверно и для варианта 2.
Док Браун
2
@MikeNakis: Это кажется дорогим, но вся работа выполняется на сервере, который (как правило) оптимизирован для такого рода работы. Я не стал бы использовать эту технику для таблицы с миллионами строк, но я бы не стал сбрасывать со счетов ее для таблицы с несколькими тысячами.
TMN

Ответы:

29

Базы данных оптимизированы для определенных вещей. Быстрое обновление большого количества строк является одним из них. Это становится особенно актуальным, когда вы позволяете базе данных выполнять свою работу.

Рассмотреть возможность:

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

И вы хотите перейти Beat Itк концу, у вас будет два запроса:

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

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

Вот и все. Это очень хорошо масштабируется с очень большими числами. Попробуйте поместить несколько тысяч песен в гипотетический список воспроизведения в вашей базе данных и посмотрите, сколько времени потребуется для перемещения песни из одного места в другое. Поскольку они имеют очень стандартизированные формы:

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

update table
  set order = ?
  where song = ?

У вас есть два подготовленных заявления, которые вы можете использовать очень эффективно.

Это дает некоторые существенные преимущества - порядок таблиц можно обдумать. Третья песня имеет order3, всегда. Единственный способ гарантировать это - использовать последовательные целые числа в качестве порядка. Использование псевдосвязанных списков или десятичных чисел или целых чисел с пробелами не позволит вам гарантировать это свойство; в этих случаях единственный способ получить n-ю песню - это отсортировать всю таблицу и получить n-ную запись.

И действительно, это намного проще, чем вы думаете. Просто выяснить, что вы хотите сделать, сгенерировать два оператора обновления, а другим людям посмотреть на эти два оператора обновления и понять, что делается.

Vedant
источник
2
Мне начинает нравиться этот подход.
Майк Накис
2
@MikeNakis это работает хорошо. Существует также двоичное дерево, основанное на аналогичной идее - модифицированное дерево предварительного заказа . Требуется немного больше, чтобы разобраться, но это позволяет вам делать очень хорошие запросы для иерархических данных. У меня никогда не было проблем с производительностью, даже на больших деревьях. Я уделяю большое внимание умению рассуждать о коде до тех пор, пока не покажется, что простому коду не хватает необходимой производительности (а это было только в экстремальных ситуациях).
Будут ли какие-либо проблемы с использованием, orderтак order byкак это ключевое слово?
kojow7
@ kojow7, если ваши поля имеют имена, конфликтующие с ключевыми словами, вы должны заключить их в отметки "` ".
Андри
Этот подход имеет смысл, но что является лучшим способом получить orderзначение при добавлении новой песни в список воспроизведения. Скажем, это 9-я песня, есть ли лучший способ вставить 9, orderчем делать COUNTдо добавления записи?
Делашум
3

Прежде всего, из вашего описания того, что вы сделали, неясно, но вам нужна PlaylistSongsтаблица, которая содержит a PlaylistIdи a SongId, описывающие, какие песни принадлежат каким плейлистам.

Именно в этой таблице вы должны добавить информацию для заказа.

Мой любимый механизм с реальными числами. Я реализовал это недавно, и это сработало как шарм. Когда вы хотите переместить песню в определенную позицию, вы вычисляете ее новое Orderingзначение как среднее значение Orderingзначений предыдущей и следующей песни. Если вы используете 64-битное действительное число, вы достигнете точности примерно в то же самое время, когда ад замерзнет, ​​но если вы действительно пишете свое программное обеспечение для потомков, тогда подумайте о переназначении хороших округленных целочисленных Orderingзначений для всех песен в каждой плейлист время от времени.

В качестве дополнительного бонуса, вот код, который я написал, который реализует это. Конечно, вы не можете использовать его как есть, и для меня сейчас было бы слишком много работы по его дезинфекции для вас, поэтому я только публикую его, чтобы вы могли извлечь из него идеи.

Класс ParameterTemplate(что угодно, не спрашивайте!) Метод получает список шаблонов параметров, к которым принадлежит этот шаблон, от его родителя ActivityTemplate. (Как бы то ни было, не спрашивайте!) Код содержит некоторую защиту от нехватки точности. Делитель используется для тестирования: в модульном тесте используется большой делитель, чтобы быстро выйти за пределы точности и, таким образом, активировать защитный код точности. Второй метод является общедоступным и «только для внутреннего использования; не вызывать», чтобы тестовый код мог его вызывать. (Он не может быть закрытым для пакета, потому что мой тестовый код не находится в том же пакете, что и код, который он тестирует.) Поле, которое управляет порядком, вызывается Ordering, вызывается через getOrdering()и setOrdering(). Вы не видите SQL, потому что я использую объектно-реляционное отображение через Hibernate.

/**
 * Moves this {@link ParameterTemplate} to the given index in the list of {@link ParameterTemplate}s of the parent {@link ActivityTemplate}.
 *
 * The index must be greater than or equal to zero, and less than or equal to the number of entries in the list.  Specifying an index of zero will move this item to the top of
 * the list. Specifying an index which is equal to the number of entries will move this item to the end of the list.  Any other index will move this item to the position
 * specified, also moving other items in the list as necessary. The given index cannot be equal to the current index of the item, nor can it be equal to the current index plus
 * one.  If the given index is below the current index of the item, then the item will be moved so that its new index will be equal to the given index.  If the given index is
 * above the current index, then the new index of the item will be the given index minus one.
 *
 * NOTE: this method flushes the persistor and refreshes the parent node so as to guarantee that the changes will be immediately visible in the list of {@link
 * ParameterTemplate}s of the parent {@link ActivityTemplate}.
 *
 * @param toIndex the desired new index of this {@link ParameterTemplate} in the list of {@link ParameterTemplate}s of the parent {@link ActivityTemplate}.
 */
public void moveAt( int toIndex )
{
    moveAt( toIndex, 2.0 );
}

/**
 * For internal use only; do not invoke.
 */
public boolean moveAt( int toIndex, double divisor )
{
    MutableList<ParameterTemplate<?>> parameterTemplates = getLogicDomain().getMutableCollections().newArrayList();
    parameterTemplates.addAll( getParentActivityTemplate().getParameterTemplates() );
    assert parameterTemplates.getLength() >= 1; //guaranteed since at the very least, this parameter template must be in the list.
    int fromIndex = parameterTemplates.indexOf( this );
    assert 0 <= toIndex;
    assert toIndex <= parameterTemplates.getLength();
    assert 0 <= fromIndex;
    assert fromIndex < parameterTemplates.getLength();
    assert fromIndex != toIndex;
    assert fromIndex != toIndex - 1;

    double order;
    if( toIndex == 0 )
    {
        order = parameterTemplates.fetchFirstElement().getOrdering() - 1.0;
    }
    else if( toIndex == parameterTemplates.getLength() )
    {
        order = parameterTemplates.fetchLastElement().getOrdering() + 1.0;
    }
    else
    {
        double prevOrder = parameterTemplates.get( toIndex - 1 ).getOrdering();
        parameterTemplates.moveAt( fromIndex, toIndex );
        double nextOrder = parameterTemplates.get( toIndex + (toIndex > fromIndex ? 0 : 1) ).getOrdering();
        assert prevOrder <= nextOrder;
        order = (prevOrder + nextOrder) / divisor;
        if( order <= prevOrder || order >= nextOrder ) //if the accuracy of the double has been exceeded
        {
            parameterTemplates.clear();
            parameterTemplates.addAll( getParentActivityTemplate().getParameterTemplates() );
            for( int i = 0; i < parameterTemplates.getLength(); i++ )
                parameterTemplates.get( i ).setOrdering( i * 1.0 );
            rocs3dDomain.getPersistor().flush();
            rocs3dDomain.getPersistor().refresh( getParentActivityTemplate() );
            moveAt( toIndex );
            return true;
        }
    }
    setOrdering( order );
    rocs3dDomain.getPersistor().flush();
    rocs3dDomain.getPersistor().refresh( getParentActivityTemplate() );
    assert getParentActivityTemplate().getParameterTemplates().indexOf( this ) == (toIndex > fromIndex ? toIndex - 1 : toIndex);
    return false;
}
Майк Накис
источник
Я бы использовал целочисленный порядок, и если бы мне казалось, что переупорядочение слишком дорого, я бы просто уменьшил количество переупорядочений, сделав каждый скачок на X, где X - это количество, которое мне нужно, чтобы уменьшить переупорядочение, скажем, на 20, что должно быть хорошо, как стартер.
Уоррен П
1
@WarrenP да, я знаю, это тоже можно сделать таким образом, поэтому я просто назвал этот «мой любимый» подход вместо «лучший» или «единственный» подход.
Майк Накис
0

Что сработало для меня, для небольшого списка из порядка 100 наименований было использовать гибридный подход:

  1. Десятичный столбец SortOrder, но с достаточной точностью, чтобы сохранить разницу в 0,5 (т. Е. Десятичная (8,2) или что-то в этом роде).
  2. При сортировке возьмите PK строки выше и ниже, куда текущая строка была перемещена, если они существуют. (У вас не будет строки выше, если вы переместите элемент в первую позицию, например)
  3. Разместите PK текущей, предыдущей и следующей строки на сервере для выполнения сортировки.
  4. Если у вас есть предыдущая строка, установите текущую позицию строки на prev + 0.5. Если у вас есть только следующий, установите текущую позицию строки на следующий - 0,5.
  5. Далее у меня есть сохраненный процесс, который обновляет все позиции с помощью функции Row_Number в SQL Server, упорядочивая по новому порядку сортировки. Это преобразует порядок с 1,1,5,2,3,4,6 до 1,2,3,4,5,6, поскольку функция row_number дает целочисленные порядковые номера.

Таким образом, вы получите целочисленный порядок без пробелов, сохраненный в десятичном столбце. Это довольно чисто, я чувствую. Но он может не очень хорошо масштабироваться, если у вас есть сотни тысяч строк, которые нужно обновить, и все сразу. Но если да, то почему вы используете пользовательскую сортировку? (Примечание: если у вас большая таблица с миллионами пользователей, но у каждого пользователя есть только несколько сотен элементов для сортировки, вы можете использовать описанный выше подход очень хорошо, так как в любом случае вы будете использовать предложение where, чтобы ограничить изменения только одним пользователем )

Джон
источник