Как представить и вставить в упорядоченный список в SQL?

Question

Я хочу представить список "привет", "привет", "до свидания", "хорошего дня", "привет" (с таким порядком) в таблице SQL:

pk | i | val
------------
1  | 0 | hi
0  | 2 | hello
2  | 3 | goodbye
3  | 4 | good day
5  | 6 | howdy

'pk' - столбец первичного ключа. Не обращайте внимания на его значения.

«i» - это «индекс», который определяет порядок значений в столбце «val». только используется для установления порядка, а значения в противном случае не важны.

У меня проблема с вставкой значений в список при сохранении порядка. Например, если я хочу вставить «эй», и я хочу, чтобы оно отображалось между «привет» и «до свидания», то мне нужно сместить значения «i» для «до свидания» и «хорошего дня "(но желательно не" привет "), чтобы освободить место для новой записи.

Итак, есть ли стандартный шаблон SQL для выполнения операции сдвига, но только сдвиг элементов, которые необходимы? (Обратите внимание, что простая «таблица UPDATE SET i = i + 1 WHERE i> = 3» не работает, поскольку она нарушает ограничение уникальности для «i», а также без необходимости обновляет строку «howdy».)

Или, есть ли лучший способ представить упорядоченный список? Я полагаю, что вы могли бы сделать 'i' значением с плавающей запятой и выбрать значения между ними, но тогда вам придется выполнить отдельную операцию перебалансировки, когда такого значения не существует.

Или есть какой-нибудь стандартный алгоритм для генерации строковых значений между произвольными другими строками, если бы я сделал 'i' varchar?

Или я должен просто представить его как связанный список? Я избегал этого, потому что хотел бы также иметь возможность сделать SELECT .. ORDER BY, чтобы привести все элементы в порядок.

Answer 1

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

Если вы используете Oracle, а связанный список представляет собой отдельную таблицу(или даже ту же таблицу с идентификатором, ссылающимся на себя - чего я бы избегал), тогда вы можете использовать запрос CONNECT BY и псевдостолбец LEVEL для определения порядка сортировки.

Answer 2

Этого легко добиться, используя каскадный триггер, который обновляет любую запись «index», равную новой записи в операции вставки / обновления, до значения индекса +1. Это будет каскадно проходить по всем строкам, пока первый пробел не остановит каскад - см. Второй пример в этой записи блога для реализации PostgreSQL.

Этот подход должен работать независимо от используемой СУБД, при условии, что он поддерживает триггеры для запуска перед обновлением / вставкой. Он в основном делает то, что вы делаете, если бы вы реализовали желаемое поведение в коде (увеличивайте все следующие значения индекса, пока не встретите пробел), но более простым и эффективным способом.

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

Answer 3

Если вы используете не числа, а строки, у вас может быть таблица:

pk | i | val
------------
1  | a0 | hi
0  | a2 | hello
2  | a3 | goodbye
3  | b  | good day
5  | b1 | howdy

Вы можете вставить a4 между a3 и b, a21 между a2 и a3, a1 между a0 и a2 и так далее. Вам понадобится умная функция, чтобы сгенерировать i для нового значения v между p и n, и индекс может становиться все длиннее и длиннее, или вам время от времени требуется большая перебалансировка.

Другой подход может заключаться в реализации (двойного) связного списка в таблице, где вы сохраняете не индексы, а ссылки на предыдущий и следующий, что означает, что вам обычно нужно обновить 1-2 элементы:

pk | prev | val
------------
1  |   0  | hi
0  |   1  | hello
2  |   0  | goodbye
3  |   2  | good day
5  |   3  | howdy

эй, между привет и до свидания:

эй, получи пк 6,

pk | prev | val
------------
1  |   0  | hi
0  |   1  | hello 
6  |   0  | hi <- ins
2  |   6  | goodbye <- upd
3  |   2  | good day
5  |   3  | howdy

предыдущий элемент будет hello с pk = 0, а goodbye, который сейчас связан с hello, должен в будущем связываться с hey.

Но я не знаю, возможно ли найти механизм 'order by' для многих реализаций db.

Answer 4

Я попытался ответить на вопрос, аналогичный этому, в этом посте: Изменение порядка упорядоченных списков . Надеюсь, это поможет.