Список реализаций поверх SQL
Мне нужно реализовать абстракцию списка поверх базы данных SQL. Эта абстракция списка должна поддерживать операции добавления, удаления и вставки.
Я планирую реализовать таблицу «ключ-значение», в которой ключ содержит информацию о сортировке / порядке, а значение содержит значения списка. Чтобы добавить элементы вверху, мне просто нужно создать ключ, который упорядочивает / сортирует над предыдущим верхом. Чтобы вставить элемент, мне просто нужно создать ключ, который упорядочивает / сортирует между двумя записями в позиции вставки. При такой схеме мне не нужно перебалансировать таблицу после того, как я вставлю элемент посередине.
Одна из возможных наивных реализаций - использовать дробные числа для ключей. Чтобы вставить значение между двумя элементами, я просто вычисляю среднее значение ключей для двух элементов и использую его как ключ для вставленного значения. Большинство БД имеют конечную точность для чисел. Чтобы преодолеть это, мы можем преобразовать число в строку и использовать различные библиотеки произвольной точности для вычисления среднего. По этой схеме ключ увеличивается на 1 цифру pr insert. См. Пример реализации ниже
function between(prev_key:number,next_key:number):number {
var insert_key = (prev_key + next_key) / 2.0;
assert(insert_key > prev_key && insert_key < next_key);
return insert_key;
}
Увеличение ключа на 1 цифру для каждой вставленной строки не очень масштабируемо. Я экспериментировал с различными схемами ключей и «промежуточными» реализациями. Но у большинства / всех есть проблемы с быстро растущей длиной ключей на вставке. Мое чутье подсказывает мне, что для этого есть оптимальная стратегия, но решение ускользает от меня.
Обратите внимание, что в этом примере я использую число в качестве типа ключа, но ключ может быть строковым или любым другим, если я могу правильно сгенерировать ключ между ключом и порядком.
Любые идеи?
Насколько я понимаю, это уменьшит проблему, но не решит ее. Сложность размера ключа по-прежнему будет O (N) относительно размера списка, то есть 1M строк будет генерировать длину ключа в диапазоне 100k. Я ищу что-то близкое к решению O (log N) для размера ключа :)
Ответы 2
Используя одно значение для индексации ваших значений, вы реализуете список поверх того, что по сути является массивом.
Было бы проще использовать структуру данных, напоминающую список, т.е. где каждая запись имеет указатели на следующий и предыдущий узел. В SQL указатели - это внешние ключи. В списке в памяти идентификатором узла будет его адрес, который является случайным, поэтому в SQL вы можете просто использовать автоматически увеличивающийся PK:
CREATE TABLE List (
ID INTEGER PRIMARY KEY,
Prev INTEGER REFERENCES List,
Next INTEGER REFERENCES List,
Value
);
Чтобы вставить или удалить, вы должны настроить значения Prev / Next в самом узле и его соседних узлах.
Чтобы перебирать список, вы должны следовать указателям Next, что требует рекурсивного CTE:
WITH RECURSIVE iteration AS (
SELECT Value, Next
FROM List
WHERE ID = 0 -- or Prev IS NULL, or however you identify the first entry
UNION ALL
SELECT Value, Next
FROM List
JOIN iteration ON List.ID = iteration.Next
)
SELECT Value FROM iteration;
Спасибо! Я не думал о применении рекурсивного CTE к этой проблеме, но вы правы, это решит мою проблему. И производительность должна быть в порядке с индексом первичного ключа по ID.
Мне все еще интересно, есть ли способ сгенерировать ключи таким образом, чтобы мой первоначальный подход работал для больших списков. Я оставлю эту тему открытой на день или два и посмотрю, получу ли я какие-нибудь интересные комментарии. Но считайте, что ваш ответ принят!
После ночного сна я думаю, что нашел способ сгенерировать эффективные ключи для алгоритмической проблемы, указанной в первоначальном сообщении.
Хитрость заключается в том, чтобы зарезервировать диапазон значений, если вам нужно увеличить длину ключа при вставке. Поэтому вместо добавления одной цифры, как при усреднении, мы «резервируем» N цифр. В этом зарезервированном диапазоне мы можем рассчитывать на единицу для каждой вставки, где ключ больше предыдущего. Это дает нам длину ключа O (log n) в зарезервированном диапазоне. Если нам нужно будет спуститься, у нас не будет места, и нам нужно будет снова расширяться. Но второй трюк - изменить зарезервированный диапазон для каждого расширения. Итак, в следующем зарезервированном диапазоне мы начинаем сверху и обратный отсчет.
Предварительное тестирование показывает, что эта структура генерирует очень компактные ключи как для случайных вставок, так и для нескольких вставок в одну и ту же позицию в списке и заголовке. Однако я думаю, что можно увеличить размер ключа, если «атаковать» эту структуру только правильным шаблоном вставки. Так что рекурсивный CTE, вероятно, более безопасный подход.
Я могу уточнить позже, если потребуется
Что ж, одна очевидная оптимизация длины, которую вы можете сделать, - это когда вы в среднем пытаетесь округлить ее и посмотреть, работает ли она по-прежнему. т.е. когда среднее значение 1 и 1,5, вы получаете 1,25. Округлите это до 1,3, и это все еще работает. Ключ не растет. На следующем шаге, сделав 1.5 и 1.3, вы получите 1.4. Или 1 и 1,3, вы получите 1,15, а округляя его, вы получите приемлемый 1,2. Только когда вы смотрите между 1,2 и 1,3, вам понадобится ключ, чтобы действительно вырасти в длину. Возможно, это все еще не идеально, но это, по крайней мере, лучше, чем каждый раз увеличивать ключ на 1 цифру ...