Хранение переупорядочиваемого списка в базе данных

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

Сначала я пробовал positionстолбец, но, похоже, было бы неэффективно менять значение позиции каждого другого элемента при его перемещении.

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

Другое решение, которое я видел, - это использование десятичных чисел и просто вставление элементов в промежутки между ними, что пока кажется лучшим решением, но я уверен, что должен быть лучший способ.

Я бы сказал, что типичный список будет содержать около 20 или около того элементов, и я, вероятно, ограничу его до 50. Переупорядочение будет использовать перетаскивание и, вероятно, будет сделано в пакетном режиме, чтобы предотвратить условия гонки и тому подобное от Аякс просит. Я использую postgres (на героку), если это имеет значение.

У кого-нибудь есть какие-либо идеи?

Приветствия за любую помощь!

Во-первых, не пытайтесь делать что-то умное с десятичными числами, потому что они вас злят. REALи DOUBLE PRECISIONнеточны и могут неправильно представлять то, что вы вкладываете в них. NUMERICэто точно, но правильная последовательность шагов изменит вашу точность, и ваша реализация будет плохо работать.

Ограничение количества движений одним взлетом и падением делает всю операцию очень простой. Чтобы получить список последовательно пронумерованных элементов, вы можете переместить элемент вверх, уменьшив его позицию и увеличивая номер позиции независимо от того, что придумал предыдущий декремент. (Другими словами, предмет 5станет, 4а то, что было предметом, 4станет 5обменом, как описал Моронс в своем ответе.) Сдвиг его будет противоположным. Индексируйте свою таблицу по уникальному идентификатору списка и позиции, и вы можете сделать это с двумя UPDATEs внутри транзакции, которая будет выполняться очень быстро. Если ваши пользователи не перестраивают свои списки на сверхчеловеческих скоростях, это не вызовет большой нагрузки.

Перетаскивание (например, перемещение элемента, 6чтобы сидеть между элементами 9и 10) немного сложнее и должно выполняться по-разному в зависимости от того, находится ли новая позиция выше или ниже старой. В приведенном выше примере вы должны открыть отверстие, увеличивая все позиции больше чем 9, обновляя позицию элемента 6, чтобы она стала новой, 10а затем уменьшая позицию на все, что больше, чем 6заполнить освободившееся место. С тем же индексированием, которое я описал ранее, это будет быстро. На самом деле вы можете сделать это немного быстрее, чем я описал, уменьшив количество строк, к которым обращается транзакция, но это микрооптимизация, в которой вам не нужно, пока вы не докажете, что есть узкое место.

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

Тот же ответ здесь https://stackoverflow.com/a/49956113/10608

Решение: создать indexстроку (потому что строки, по сути, имеют бесконечную «произвольную точность»). Или, если вы используете int, увеличьте indexна 100 вместо 1.

Проблема производительности заключается в следующем: между двумя отсортированными элементами нет промежуточных значений.

item      index
-----------------
gizmo     1
              <<------ Oh no! no room between 1 and 2.
                       This requires incrementing _every_ item after it
gadget    2
gear      3
toolkit   4
box       5

Вместо этого сделайте так (лучшее решение ниже):

item      index
-----------------
gizmo     100
              <<------ Sweet :). I can re-order 99 (!) items here
                       without having to change anything else
gadget    200
gear      300
toolkit   400
box       500

Еще лучше: вот как Джира решает эту проблему. Их «ранг» (то, что вы называете индексом) - это строковое значение, которое дает тонну передышки между ранжированными предметами.

Вот реальный пример базы данных jira, с которой я работаю

   id    | jira_rank
---------+------------
 AP-2405 | 0|hzztxk:
 ES-213  | 0|hzztxs:
 AP-2660 | 0|hzztzc:
 AP-2688 | 0|hzztzk:
 AP-2643 | 0|hzztzs:
 AP-2208 | 0|hzztzw:
 AP-2700 | 0|hzztzy:
 AP-2702 | 0|hzztzz:
 AP-2411 | 0|hzztzz:i
 AP-2440 | 0|hzztzz:r

Обратите внимание на этот пример hzztzz:i. Преимущество строкового ранга в том, что вам не хватает места между двумя предметами, вам все равно не нужно переоценивать что-либо еще. Вы просто начинаете добавлять больше символов в строку, чтобы сузить фокус.

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

Почему? Предположим, вы используете подход со связанными таблицами со столбцами (listID, itemID, nextItemID).

Вставка нового элемента в список стоит одну вставку и одну измененную строку.

Перемещение элемента стоит три модификации строки (перемещаемый элемент, элемент перед ним и элемент перед новым местоположением).

Удаление элемента стоит одно удаление и одна измененная строка.

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

«но кажется, что это было бы совершенно неэффективно»

Вы измерили это? Или это только предположение? Не делайте таких предположений без каких-либо доказательств.

«20-50 наименований в списке»

Честно говоря, это не "много предметов", для меня это звучит очень мало.

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

Это действительно вопрос масштаба и варианта использования.

Сколько предметов вы ожидаете в списке? Если миллионы, я думаю, что гонг десятичный маршрут является очевидным.

Если 6, то нумерация целых чисел является очевидным выбором. s Также вопросы, как списки или переставить. Если вы используете стрелки вверх и вниз (двигаясь вверх или вниз на один слот за раз), я бы использовал целые числа, а затем поменялся местами с предыдущим (или следующим) на ходу.

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

tl; dr: нужно больше информации.

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

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

При условии, что

• Все элементы покупок могут быть перечислены с 32-битными целыми числами.
• Для списка пожеланий пользователя установлен максимальный размер. (Я видел, что какой-то популярный сайт использует не более 20-40 пунктов)

Сохраните отсортированный список пожеланий пользователя в виде упакованной последовательности целых чисел (целочисленных массивов) в одном столбце. Каждый раз, когда список пожеланий переупорядочивается, весь массив (одна строка; один столбец) обновляется - что должно быть выполнено с одним обновлением SQL.

https://www.postgresql.org/docs/current/static/arrays.html

Если цель другая, придерживайтесь подхода «столбец позиции».

Относительно «скорости», убедитесь, что сравнительный анализ хранимой процедуры. Хотя выпуск более 20 отдельных обновлений для одного списка пожеланий может быть медленным, возможен быстрый способ использования хранимой процедуры.

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

• Если positionполе должно быть последовательным без пробелов, то вам нужно будет переупорядочить весь список. Это операция O (N). Преимущество заключается в том, что клиентской стороне не потребуется особая логика для получения заказа.

• Если мы хотим избежать операции O (N), НО ЕЩЕ сохраняйте точную последовательность, один из подходов состоит в том, чтобы использовать «самоссылку для ссылки на предыдущее (или следующее) значение». Это сценарий со списком связанных учебников. По замыслу, это НЕ повлечет за собой «много других предметов в списке». Однако для этого требуется, чтобы на стороне клиента (веб-служба или, возможно, мобильное приложение) была реализована логика обхода связанного списка для получения порядка.

• Некоторые варианты не используют ссылку, то есть связанный список. Они выбирают представление всего порядка в виде отдельного большого двоичного объекта, такого как JSON-array-in-a-string [5,2,1,3,...]; такой порядок будет храниться в отдельном месте. Этот подход также имеет побочный эффект, заключающийся в том, что клиентский код должен поддерживать этот отдельный двоичный объект заказа.

• Во многих случаях нам на самом деле не нужно хранить точный порядок, нам просто нужно поддерживать относительный ранг среди каждой записи. Поэтому мы можем допустить разрыв между последовательными записями. Вариации включают в себя: (1) использование целых чисел с пробелами, такими как 100, 200, 300 ... но вы быстро исчерпаете пробелы и затем потребуется процесс восстановления; (2) использование десятичной дроби, которая идет с естественными пробелами, но вам нужно будет решить, можете ли вы жить с возможным ограничением точности; (3) использование ранга на основе строк, как описано в этом ответе, но будьте осторожны с хитрыми ловушками реализации .

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

Используйте число с плавающей запятой для столбца позиции.

Затем вы можете изменить порядок списка, изменив только положение столбца в «перемещенной» строке.

В основном, если ваш пользователь хочет позиционировать «красный» после «синего», но до «желтого»

Тогда вам просто нужно рассчитать

red.position = ((yellow.position - blue.position) / 2) + blue.position

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

Вы можете реализовать это, используя целочисленное поле с начальным зазором, скажем, 1000. Таким образом, ваше начальное oredring будет 1000-> синий, 2000-> желтый, 3000-> красный. После «перемещения» красного за синим у вас будет 1000-> синий, 1500-> красный, 2000-> желтый.

Проблема в том, что при кажущемся большом начальном разрыве в 1000 всего 10 ходов вы попадете в ситуацию, такую ​​как 1000-> синий, 1001-puce, 1004-> осада ......, где вы больше не сможете вставить что-нибудь после «синего» без нумерации всего списка. Используя числа с плавающей запятой, всегда будет точка «на полпути» между двумя позициями.

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

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

Дело в том , что нет ! При использовании связанного списка вставка, удаление и переупорядочение являются O(1)операциями, а навязанная базой данных ссылочная целостность гарантирует, что не будет битых ссылок, потерянных записей или циклов.

Вот пример:

CREATE TABLE Wishlists (
  WishlistId int           NOT NULL IDENTITY(1,1) PRIMARY KEY,
  [Name]     nvarchar(200) NOT NULL
);

CREATE TABLE WishlistItems (
  ItemId     int           NOT NULL IDENTITY(1,1),
  WishlistId int           NOT NULL,
  Text       nvarchar(200) NOT NULL,
  SortAfter  int               NULL,

  CONSTRAINT PK_WishlistItem PRIMARY KEY ( ItemId, WishlistId ),
  CONSTRAINT FK_Wishlist_WishlistItem FOREIGN KEY ( WishlistId ) REFERENCES Wishlists ( WishlistId ),
  CONSTRAINT FK_Sorting FOREIGN KEY ( SortAfter, WishlistId ) REFERENCES WishlistItems ( ItemId, WishlistId )
);

CREATE UNIQUE INDEX UX_Sorting ON WishlistItems ( SortAfter, WishlistId );

 -----

SET IDENTITY_INSERT Wishlists ON;

INSERT INTO Wishlists ( WishlistId, [Name] ) VALUES
  ( 1, 'Wishlist 1' ),
  ( 2, 'Wishlist 2' );

SET IDENTITY_INSERT Wishlists OFF;

SET IDENTITY_INSERT WishlistItems ON;

INSERT INTO WishlistItems ( ItemId, WishlistId, [Text], SortAfter ) VALUES
( 1, 1, 'One', NULL ),
( 2, 1, 'Two', 1 ),
( 3, 1, 'Three', 2 ),
( 4, 1, 'Four', 3 ),
( 5, 1, 'Five', 4 ),
( 6, 1, 'Six', 5 ),
( 7, 1, 'Seven', 6 ),
( 8, 1, 'Eight', 7 );

SET IDENTITY_INSERT WishlistItems OFF;

Обратите внимание на следующее:

• Использование составного первичного ключа и внешнего ключа FK_Sortingдля предотвращения случайного обращения элементов к неправильному родительскому элементу.
• UNIQUE INDEX UX_SortingВыполняет две роли:
  • Поскольку он допускает одно NULLзначение, каждый список может иметь только 1 «головной» элемент.
  • Это предотвращает утверждение о том, что два или более элементов находятся в одном и том же месте сортировки (за счет предотвращения дублирования SortAfterзначений).

Основные преимущества этого подхода:

• Никогда не требуется перебалансировка или обслуживание - как в случае заказов сортировки на основе intили real, в которых между частями после частого переупорядочения в конечном итоге заканчивается свободное пространство.
• Только элементы, которые переупорядочены (и их братья и сестры) должны быть обновлены.

Этот подход имеет недостатки, однако:

• Вы можете отсортировать этот список в SQL только с помощью Recursive CTE, потому что вы не можете сделать это просто ORDER BY.
  • В качестве обходного пути вы можете создать оболочку VIEWили TVF, которые используют CTE для добавления производного, содержащего возрастающий порядок сортировки, но это будет дорого использовать в больших операциях.
• Вы должны загрузить весь список в свою программу, чтобы отобразить его - вы не можете работать с подмножеством строк, потому что тогда SortAfterстолбец будет ссылаться на элементы, которые не загружены в вашу программу.
  • Однако загрузка всех элементов для списка проста из-за составного первичного ключа (то есть просто сделать SELECT * FROM WishlistItems WHERE WishlistId = @wishlistToLoad).
• Выполнение любой операции, пока UX_Sortingона включена, требует поддержки СУБД для отложенных ограничений.
  • т.е. идеальная реализация этого подхода не будет работать в SQL Server до тех пор, пока не будет добавлена ​​поддержка отложенных ограничений и индексов.
  • Обходной путь - сделать уникальный индекс фильтрованным индексом, который допускает несколько NULLзначений в столбце, что, к сожалению, означает, что список может иметь несколько элементов HEAD.
    • Обходной путь для этого обходного пути заключается в добавлении третьего столбца, Stateкоторый представляет собой простой флаг для объявления, является ли элемент списка «активным» или нет - и уникальный индекс игнорирует неактивные элементы.
  • Это то, что SQL Server использовал для поддержки еще в 1990-х годах, а затем они необъяснимым образом прекратили поддержку.

Обходной путь 1: Нужна способность выполнять тривиально ORDER BY.

Вот ВИД, использующий рекурсивный CTE, который добавляет SortOrderстолбец:

CREATE VIEW OrderableWishlistItems AS 

    WITH c ( ItemId, WishlistId, [Text], SortAfter, SortOrder )
    AS
    (
        SELECT
              ItemId, WishlistId, [Text], SortAfter, 1 AS SortOrder
        FROM
              WishlistItems
        WHERE
              SortAfter IS NULL

        UNION ALL

        SELECT
              i.ItemId, i.WishlistId, i.[Text], i.SortAfter, c.SortOrder + 1
        FROM
              WishlistItems AS i
              INNER JOIN c ON
                  i.WishlistId = c.WishlistId
                  AND
                  i.SortAfter = c.ItemId
    )
    SELECT
        ItemId, WishlistId, [Text], SortAfter, SortOrder
    FROM
        c;

Вы можете использовать этот VIEW в других запросах, где вам нужно отсортировать значения, используя ORDER BY:

Query:

    SELECT * FROM OrderableWishlistItems

Results:

    ItemId  WishlistId  Text        SortAfter   SortOrder
    1       1           One         (null)      1
    2       1           Two             1       2
    3       1           Three           2       3
    4       1           Four            3       4
    5       1           Five            4       5
    6       1           Six             5       6
    7       1           Seven           6       7
    8       1           Eight           7       8

Обходной путь 2: Предотвращение UNIQUE INDEXнарушений ограничений при выполнении операций:

Добавьте Stateстолбец в WishlistItemsтаблицу. Столбец помечен HIDDENтак, что большинство инструментов ORM (например, Entity Framework) не включают его, например, при создании моделей.

CREATE TABLE WishlistItems (
  ItemId     int           NOT NULL IDENTITY(1,1),
  WishlistId int           NOT NULL,
  Text       nvarchar(200) NOT NULL,
  SortAfter  int               NULL,
  [State]    bit           NOT NULL HIDDEN,

  CONSTRAINT PK_WishlistItem PRIMARY KEY ( ItemId, WishlistId ),
  CONSTRAINT FK_Wishlist_WishlistItem FOREIGN KEY ( WishlistId ) REFERENCES Wishlists ( WishlistId ),
  CONSTRAINT FK_Sorting FOREIGN KEY ( SortAfter, WishlistId ) REFERENCES WishlistItems ( ItemId, WishlistId )
);

CREATE UNIQUE INDEX UX_Sorting ON WishlistItems ( SortAfter, WishlistId ) WHERE [State] = 1;

Операции:

Добавление нового элемента в конец списка:

1. Сначала загрузите список, чтобы определить ItemIdтекущий последний элемент в списке, и сохраните его @tailItemIdили используйте SELECT MAX( SortOrder ) FROM OrderableWishlistItems WHERE WishlistId = @listId.
2. INSERT INTO WishlistItems ( WishlistId, [Text], SortAfter ) VALUES ( @listId, @text, @tailItemId ),

Изменение порядка позиций 4 ниже 7

BEGIN TRANSACTION

    DECLARE @itemIdToMove int = 4
    DECLARE @itemIdToMoveAfter int = 7

    DECLARE @prev int = ( SELECT SortAfter FROM WishlistItems WHERE ItemId = @itemIdToMove )

    UPDATE WishlistItems SET [State] = 0 WHERE ItemId IN ( @itemIdToMove , @itemIdToMoveAfter )

    UPDATE WishlistItems SET [SortAfter] = @itemIdToMove WHERE ItemId = @itemIdToMoveAfter 

    UPDATE WishlistItems SET [SortAfter] = @prev WHERE SortAfter = @itemIdToMove 

    UPDATE WishlistItems SET [State] = 1 WHERE ItemId IN ( @itemIdToMove, @itemIdToMoveAfter )

COMMIT;

Удаление пункта 4 из середины списка:

Если элемент находится в конце списка (т.е. где NOT EXISTS ( SELECT 1 FROM WishlistItems WHERE SortAfter = @itemId )), то вы можете сделать один DELETE.

Если у элемента есть элемент, отсортированный после него, вы выполняете те же шаги, что и при переупорядочении элемента, за исключением того, DELETEчто вы выполняете его впоследствии, вместо настройки State = 1;.

BEGIN TRANSACTION

    DECLARE @itemIdToRemove int = 4

    DECLARE @prev int = ( SELECT SortAfter FROM WishlistItems WHERE ItemId = @itemIdToRemove )

    UPDATE WishlistItems SET [State] = 0 WHERE ItemId = @itemIdToRemove

    UPDATE WishlistItems SET [SortAfter] = @prev WHERE SortAfter = @itemIdToRemove

    DELETE FROM WishlistItems WHERE ItemId = @itemIdToRemove

COMMIT;