Как масштабируется время запроса базы данных в зависимости от размера базы данных?

Question

Недавно я недавно был в OEIS (Онлайн-энциклопедии целочисленных последовательностей), пытаясь найти конкретную последовательность, которая у меня была.

Теперь эта база данных довольно большая.На веб-сайте утверждается, что если бы издание 2006 года (! 5 лет) было напечатано, оно заняло бы 750 томов текста.

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

Однако, пренебрегая балансировкой нагрузки, сколько времени требуется для выполнения запроса по сравнению с размером базы данных?

Или, другими словами, какова временная сложность запроса относительно размера БД?

Редактировать: Чтобы сделать вещи более конкретными, предположим, что входной запрос просто ищет строкутакие номера, как:

1, 4, 9, 16, 25, 36, 49

Answer 1

Это сильно зависит от запроса, структуры базы данных, конкуренции и так далее.Но в целом большинство баз данных найдут способ использовать индекс, и этот индекс будет представлять собой некую древовидную структуру (см. http://en.wikipedia.org/wiki/B-tree для одного варианта), и в этом случае время доступа пропорционально log (n),или хеш, в этом случае время доступа в среднем пропорционально O (1) (объяснение того, как они работают, см. http://en.wikipedia.org/wiki/Hash_function#Hash_tables).

Таким образом, ответ обычно равен O (1)или O (log (n)) в зависимости от того, какой тип структуры данных используется.

Это может вызвать у вас удивление, почему мы не всегда используем хеш-функции.Есть несколько причин.Хеш-функции затрудняют получение диапазонов значений.Если хеш-функция не может правильно распределить данные, время доступа может стать O (n).Хэши иногда нуждаются в изменении размера, что потенциально очень дорого.И log (n) растет достаточно медленно, поэтому вы можете считать его достаточно близким к постоянному во всех практических наборах данных.(От 1000 до 1 петабайта это изменяется в 5 раз.) И часто активно запрашиваемые данные показывают какую-то местность, какие деревья лучше сохраняют в ОЗУ.В результате деревья несколько чаще встречаются на практике.(Хотя хэши отнюдь не редкость.)

Answer 2

Это зависит от ряда факторов, включая реализацию механизма базы данных, стратегию индексирования, специфику запроса, доступное оборудование, конфигурацию базы данных и т. Д.

Нет способа ответить на такой общий вопрос.

Answer 3

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