Временная сложность выбора / вставки в таблицу SQL только с одним столбцом (первичный ключ)

Question

Что я храню

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

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

Как я храню

Конечно, наличие только одного столбца означает сохранение только первичного ключа. В этом случае создается MD5 ha sh URL-адреса, который вставляется в базу данных в качестве первичного ключа. Список может быть очень большим (сотни тысяч), но коллизии маловероятны, поэтому пока они не важны. Так что просто представьте, что этого не произойдет. Я использую MySQL, если это важно.

Мой вопрос

1. Какова временная сложность добавления нового URL-адреса в эту базу данных?
2. Что такое временная сложность проверки наличия URL-адреса?

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

Answer 1

Я предлагаю создать индекс для этой таблицы, поскольку индекс в виде b-дерева даст временную сложность O(log n) для поиска. Это будет намного лучше масштабироваться для одновременного доступа. При отсутствии индекса это будет полное сканирование таблицы для каждого запроса, а временная сложность этого составляет O(n), когда это выполняется параллельно, оно может не так хорошо масштабироваться. Вставка в эту таблицу будет медленнее, если есть индекс, а не индекс. Если предположить, что вставка происходит не так часто, как поиск, эта небольшая часть дополнительного времени не повредит.

Answer 2

Единственный способ прочитать что-то с временем O (1) в SQL - это использовать индекс ha sh - и даже это займет больше времени, когда ha sh заполнится.

Тем не менее, вы можете узнать об индексах ha sh в документации .

Тем не менее, я сомневаюсь, что он вам действительно нужен. Индекс b-дерева подходит для большинства целей, а O (log (n)) не очень заметен на объемах данных в базах данных. Но в вашем вопросе указано O (1), а не «достаточно быстро», поэтому узнайте о хешировании и индексах на основе ha sh.