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

Question

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

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

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

Answer 1

Вопрос, конечно, зачем вам случайный идентификатор?

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

Решение, с которым я пошел, состояло в том, чтобы объединить последовательный int32 со случайным int32, чтобы получить int64, который я использовал в качестве идентификатора клиента. В PostgreSQL:

CREATE FUNCTION lift(integer, integer) returns bigint AS $$
SELECT ($1::bigint << 31) + $2
$$ LANGUAGE SQL;

CREATE FUNCTION random_pos_int() RETURNS integer AS $$
select floor((lift(1,0) - 1)*random())::integer
$$ LANGUAGE sql;

ALTER TABLE client ALTER COLUMN id SET DEFAULT
lift((nextval('client_id_seq'::regclass))::integer, random_pos_int());

Сгенерированные идентификаторы являются «наполовину» случайными, в то время как другая «половина» гарантирует, что вы не можете получить один и тот же идентификатор дважды:

select lift(1, random_pos_int());  => 3108167398
select lift(2, random_pos_int());  => 4673906795
select lift(3, random_pos_int());  => 7414644984
...

Answer 2

Почему уникальный идентификатор Random? Почему бы не использовать IDENTITY? Как был выбран идентификатор для существующих строк.

Возможно, самое простое (выберите Max (ID) из BIGTABLE), а затем убедитесь, что ваш новый "Random" ID больше этого ...

РЕДАКТИРОВАТЬ : На основании добавленной информации я бы предположил, что вы облажались.

Если это вариант: скопируйте таблицу, затем переопределите ее и используйте столбец идентификации.

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

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

Answer 3

Лучше всего сделать так, чтобы ваше пространство ключа было достаточно большим, чтобы вероятность столкновений была чрезвычайно низкой, и тогда не беспокойтесь об этом. Как уже упоминалось, GUID сделает это за вас. Или вы можете использовать чисто случайное число, если у него достаточно битов.

Эта страница имеет формулу для расчета вероятности столкновения .

Answer 4

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

int id;
do {
  id = generateRandomId();
} while (doesIdAlreadyExist(id));
doSomethingWithNewId(id); 

Answer 5

Немного за пределами коробки.

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

В конечном итоге вам придется выполнять проверки, но они могут быть перенесены во второй процесс, который не включает в себя сложный процесс вставки в bigtable.

Или сгенерируйте несколько миллиардов случайных чисел и удалите дубликаты, тогда вам не придется беспокоиться в течение достаточно долгого времени.

Answer 6

Выберите случайное число, проверьте, существует ли оно уже, если это так, продолжайте попытки, пока не наберете тот, который не существует.

Редактировать: Или еще лучше, пропустите проверку и попробуйте вставить строку с разными идентификаторами, пока она не заработает.

Answer 7

Если это то, что вам нужно делать часто, вы, вероятно, захотите сохранить живую (не-db) структуру данных, чтобы помочь вам быстро ответить на этот вопрос. Дерево с 10 путями было бы хорошо. Когда приложение запускается, оно заполняет дерево, читая ключи из БД, а затем синхронизирует его с различными вставками и удаляемыми файлами, сделанными в БД. Пока ваше приложение является единственным, которое обновляет базу данных, к дереву можно очень быстро обращаться при проверке того, что следующий большой случайный ключ еще не используется.

Answer 8

Сделайте ключевое поле УНИКАЛЬНЫМ и ИДЕНТИЧНЫМ, и вам не придется об этом беспокоиться.

Answer 9

Первый вопрос: это запланированная или уже работающая база данных. Если в нем уже есть данные, то ответ bmdhacks правильный. Если это плановая база данных, вот второй вопрос:
Ваш первичный ключ действительно должен быть случайным? Если ответ «да», используйте функцию для создания случайного идентификатора с известным начальным числом и счетчиком, чтобы узнать, сколько идентификаторов было создано. Каждый созданный идентификатор будет увеличивать счетчик.
Если вы храните в тайне начальное число (т. Е. Семя вызывается и объявляется как личное), тогда никто другой не сможет предсказать следующий идентификатор.

Answer 10

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

Можно ли выполнить несколько запросов на BigTable и посмотреть, есть ли диапазоны, которые могут быть использованы? то есть. между 100 000 и 234 000 пока нет идентификаторов, поэтому мы могли бы добавить там идентификаторы?