тупое решение, если записей немного и не пугает делать full scan на каждый селект:
в каждой записи хранить:
— собственный приоритет (любое положительное число)
— сумму приоритетов всех предыдущих элементов (в порядке добавления, например, по id)
и где-то хранить сумму всех приоритетов (на самом деле, можно получать из записи с максимальным id)
можно их нормализовать, но тогда не получится сделать быстрый insert.
select сводится к генерации нескольких рандомных чисел из диапазона [0, сумма_всех_приоритетов), и выборке элементов, где диапазон [сумма, сумма+свой_приоритет) включает хотя бы одно из выбранных чисел.
insert — простое дописывание в конец, обновление суммы приоритетов
delete — простое удаление
update (изменение приоритета) — удаление+вставка если приоритет увеличился, простой апдейт, если уменьшился.
есть неприятный спецэффект, что селект может вернуть меньше элементов чем надо, если несколько чисел попали в один диапазон или в «дырку» от удаленного элемента.
можно или выбирать сразу с небольшим запасом, или довыбирать по необходимости.
периодически (после большого числа удалений) есть смысл перестраивать приоритеты заново.
итого — все операции за амортизированную O(1), кроме селекта, с которым все печально.
для его оптимизации можно использовать spatial index (не в курсе насчет поддержки в современных БД), т.к. у нас запрос на принадлежность точки отрезку.
честное и быстрое, но сложное решение:
строить дерево, в листьях которого — id из таблицы и приоритеты, в промежуточных узлах — суммы приоритетов в поддеревьях.
select одного элемента (для простоты далее рассматривается бинарное дерево):
генерируем число от 0 до суммы приоритетов (хранится в корне), идем от корня:
— если число меньше суммы приоритетов в левом поддереве, то налево
— иначе — направо, и вычитаем из числа сумму приоритетов в левом поддереве
— когда дойдем до листа — вернуть его id
update/insert/delete — обычные операции с деревом с обновлением суммы приоритетов во всех промежуточных вершинах.
(надо быстро уметь искать лист по его id, для этого дерево можно делать сортированным по id, а можно не заморачиваться, и сделать через хэш, тогда порядок в дереве любой, что сильно все упрощает — не надо перебалансировать и вставлять можно на место любого удаленного).
производительность всех операций — O(logN), выборки — O(KlogN), где K — размер выборки.
тоже есть проблема, что один элемент может выбраться несколько раз, чтобы это побороть, можно выбранные элементы удалять сразу после выбора (ну или просто обнулять приоритет), а в самом конце вставлять обратно.
как все это хранить?
ну если все влезает в память — то отлично, вешаем отдельного демона, который при старте строит дерево по исходной табличке и поехали.
если нет — либо в базе (но эффективность работы с деревьями на реляционных базах это большой вопрос), либо в файлах, т.е., по сути, писать свой движок базы…
но это уже явный overkill =) наверняка существуют готовые решения, которые все это уже делают.
Простой
Простой
Средний
Средний
