Как создать базу данных для хранения отсортированного списка?

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

  1. Вставить (x) - Вставить запись x в таблицу
  2. Удалить (x) - Удалить запись x из таблицы
  3. До (x, n) - вернуть записи 'n', предшествующие записи x в отсортированный список.
  4. После (x, n) - Верните записи «n», следующие за записью x в отсортированный список.
  5. First (n) - возвращает первые «n» записи из отсортированного списка.
  6. Last (n) - возвращает последние 'n' записи из отсортированного списка.
  7. Сравните (x, y) - задайте две записи x и y из таблицы, найдите, если x> у.

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

В частности, я ищу, чтобы реализовать таблицу, используя SimpleDB от Amazon. Но общий ответ для реляционной базы данных также должен быть полезен.

Обновление профиля нагрузки:

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

Если есть 100k активных пользователей (супер оптимизм: P), то моя приблизительная оценка в день будет

500 тыс. выбирает, 100 тыс. вставок и удаляет, обновления 500 тыс.

Я ожидаю, что таблица вырастет до 500 тыс. в целом.

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

37 голосов | спросил chitti 13 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowTue, 13 Sep 2011 04:55:03 +0400 2011, 04:55:03

4 ответа


19

Если ранг не является полностью произвольным, а выводится из другого свойства (например, имя, оценка игрока и т. д.), тогда внимательно посмотрите на Ответ Джоэля .

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

Учитывая, что вы ожидаете высокой активности вставки и обновления, но также относительно высокой активности чтения, я рекомендую сделать следующее:

  • Скопируйте таблицу в ранг, особенно если подавляющее большинство ваших запросов против ранга. Если нет, или если вы выбрали ключ кластеризации в SimpleDB, то просто создайте индекс с рангом в качестве ведущего столбца. Это будет удовлетворять запросам 3-6.
  • Индекс первой записи, а затем ранг (или, в мире SQL Server, только запись и INCLUDE -ing rank, или просто запись, если вы кластеризовали по рангу) удовлетворяли бы запрос 7.
  • Операции 1 и 2 можно оптимизировать, соответствующим образом распределив ваши данные (т. е. установите FILLFACTOR в SQL Server). Это особенно важно, если вы группируете ранг.
  • По мере того, как вы вставляете или обновляете ранги, сохраняйте как можно больше разницы между номерами рангов, чтобы свести к минимуму эту возможность, что вам нужно будет переклассифицировать существующую запись для размещения вставки или обновления рангов. Например, если вы оцениваете свои записи с шагом в 1000, вы оставляете достаточно места примерно на половину того, что многие изменения и вставки с минимальным шансом вам потребуется переименовать запись, не участвующую в этих изменениях.
  • Каждая ночь переопределяет все записи, чтобы сбросить промежутки между ними.
  • Вы можете настроить частоту массового повторного ранжирования, а также размер разрыва ранга для размещения ожидаемого количества вставок или обновлений по сравнению с количеством существующих записей. Поэтому, если у вас есть записи 100K и ожидайте, что ваши вставки и обновления будут составлять 10% от этого, оставьте достаточно места для новых рангов 10K и переоцените их в ночное время.
  • Повторное ранжирование записей 500K - это дорогостоящая операция, но делать раз в день или в нерабочее время должно быть хорошо для такой базы данных. Это массовое повторное ранжирование в нерабочее время для поддержания разрывов в рангах - это то, что экономит вам переопределение многих записей для каждого обновления ранга или вставки во время обычного и пикового часов.

Если вы ожидаете, что 100K + читает таблицу с размером 100K +, я не рекомендую использовать подход связанных списков. Он не будет хорошо масштабироваться до этих размеров.

ответил Nick Chammas 13 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowTue, 13 Sep 2011 05:03:13 +0400 2011, 05:03:13
10

Обычно я использую метод «rank», который вы описываете. Вместо того, чтобы возиться с обновлением строк, когда элементы необходимо переупорядочить, мне часто удавалось удалить все записи в списке и повторно вставлять новые элементы в правильном порядке. Этот метод явно оптимизирован для поиска.

Альтернативный подход состоял бы в том, чтобы смоделировать записи как связанные списки, используя столбец «предыдущий» рефлексивный внешний ключ в таблице:

ID   setID   item       predecessor
---  ------  ------     ------------
1    1       Apple      null
2    1       Orange     1
3    2       Cucumber   null
4    1       Pear       2
5    1       Grape      4
6    2       Carrot     3

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

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

ответил bpanulla 13 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowTue, 13 Sep 2011 07:15:01 +0400 2011, 07:15:01
5

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

ответил Joel Brown 13 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowTue, 13 Sep 2011 14:27:27 +0400 2011, 14:27:27
1

Это ограничения не RDBMS, как simpleDB. Необходимые функции не могут быть реализованы на стороне БД в simpleDB, они должны быть реализованы со стороны программирования /приложения.

Для RDBMS, например SQL server, требуемые функции являются рудиментарными для кластерного индекса.

  • Вставить (x) - Вставить запись x в таблицу> Простая вставка.
  • Удалить (x) - Удалить запись x из таблицы> Простое удаление.
  • До (x, n) - Возвращает записи 'n', предшествующие записи x в отсортированном списке. > Выберите верхние n результатов, где x меньше значения и порядка по предложению.

  • После (x, n) - Верните записи «n», следующие за записью x в отсортированном списке. > Выберите верхние n результатов, где x больше значения и порядок по условию.

  • First (n) - возвращает первые «n» записи из отсортированного списка. > Выберите лучшие результаты.

  • Last (n) - возвращает последние 'n' записи из отсортированного списка. > Выберите верхние n результатов после заказа по убыванию.

  • Сравните (x, y) - задайте две записи x и y из таблицы, найдите, если x> у. > Инструкция TSQL IF.
ответил StanleyJohns 14 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowWed, 14 Sep 2011 08:17:21 +0400 2011, 08:17:21

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132