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

Question

Для разработки .. а) Таблица (BIGTABLE) может содержать миллион строк с первичным ключом в качестве идентификатора. (случайный и уникальный) б) Какой алгоритм можно использовать для получения идентификатора, который до сих пор не использовался. Этот номер будет использоваться для вставки еще одной строки в таблицу BIGTABLE.

Обновлен вопрос с более подробной информацией .. C) Эта таблица уже содержит около 100 тыс. Строк, и первичный ключ не является идентификатором. d) В настоящее время случайное число генерируется в качестве первичного ключа, и строка, вставленная в эту таблицу, в случае сбоя вставки генерируется другое случайное число. иногда проблема заключается в том, что случайные числа генерируются довольно случайно, но, к сожалению, они уже существуют в таблице. так что если мы попробуем число генерации случайных чисел через некоторое время, это сработает. e) Функция sybase rand () используется для генерации случайного числа.

Надеюсь, что это дополнение к вопросу поможет прояснить некоторые моменты.

Answer 1

Пропуск аргументации самой задачи, единственный алгоритм, который

• даст вам идентификатор, которого нет в таблице
• , который будет использоваться для вставки новой строки в таблицу
• приведет к тому, что таблица все еще будет иметь случайные уникальные идентификаторы

генерирует случайное число и затем проверяет, используется ли оно уже

Answer 2

Сначала проверьте, не взят ли Max (ID) + 1, и используйте его.

Если Max (ID) + 1 превышает максимум, выберите упорядоченный кусок сверху и начните цикл в обратном направлении, ища отверстие. Повторяйте куски, пока не закончится число (в этом случае выведите большую ошибку).

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

Answer 3

Требуется ли, чтобы новый идентификатор также был случайным? Если это так, лучший ответ - просто перебрать (рандомизировать, проверить на существование), пока вы не найдете тот, который не существует.

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

Вы должны сделать это атомарно, поэтому либо заблокируйте таблицу, либо используйте какой-либо другой элемент управления параллелизмом, соответствующий вашей конфигурации и схеме БД. Хранимые процы, блокировки таблиц, блокировки строк, SELECT ... ДЛЯ ОБНОВЛЕНИЯ, что угодно.

Обратите внимание, что при любом подходе вам может потребоваться обработка неудачных транзакций. Теоретически вы можете получить повторяющиеся проблемы с ключами в первой (хотя это маловероятно, если ваше пространство ключей мало заполнено), и вы, скорее всего, получите тупики на некоторых БД с подходами, подобными SELECT ... FOR UPDATE. Поэтому обязательно проверьте и перезапустите транзакцию при ошибке.

Answer 4

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

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

Answer 5

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

Ваш лучший вариант - использовать автоинкрементную способность MySQL. Другие базы данных имеют аналогичную функциональность. Вам гарантирован уникальный идентификатор, и у вас не будет проблем с параллелизмом.

Answer 6

в зависимости от вашей базы данных, вы можете использовать секвенсор (оракул) или автоинкремент (mysql, ms sql и т. Д.). Или в крайнем случае сделайте select max (id) + 1 в качестве нового идентификатора - просто будьте осторожны с параллельными запросами, чтобы не получить один и тот же max-id дважды - оберните его в замке с помощью оператора вставки

Answer 7

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

Answer 8

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