Как масштабируется время запроса базы данных в зависимости от размера базы данных?
Недавно я недавно был в OEIS (Онлайн-энциклопедии целочисленных последовательностей), пытаясь найти конкретную последовательность, которая у меня была.
Теперь эта база данных довольно большая. На веб-сайте говорится, что если бы издание 2006 года (! 5 лет) было напечатано, оно заняло бы 750 томов текста.
Я уверен, что это та же проблема, с которой Google должен справиться. Но у них также есть распределенная система, в которой они используют преимущества балансировки нагрузки.
Однако, пренебрегая балансировкой нагрузки, сколько времени занимает выполнение запроса по сравнению с размером базы данных?
Или, другими словами, какова временная сложность запроса относительно размера БД?
Изменить: чтобы сделать вещи более конкретным, предположим, что входной запрос просто ищет строку чисел, таких как:
1, 4, 9, 16, 25, 36, 49
3 ответа
Это сильно зависит от запроса, структуры базы данных, конкуренции и так далее. Но в целом большинство баз данных найдут способ использовать индекс, и этот индекс будет либо некой древовидной структурой (см. http://en.wikipedia.org/wiki/B-tree для одного варианта), в этом случае доступ время пропорционально log(n) или хешу, в этом случае время доступа в среднем пропорционально O(1) (см. http://en.wikipedia.org/wiki/Hash_function для объяснения того, как они Работа).
Таким образом, ответ обычно O(1) или O(log(n)) в зависимости от того, какой тип структуры данных используется.
Это может вызвать у вас удивление, почему мы не всегда используем хеш-функции. Есть несколько причин. Хеш-функции затрудняют получение диапазонов значений. Если хеш-функция не может правильно распределить данные, время доступа может стать O(n). Хэши иногда нуждаются в изменении размера, что потенциально очень дорого. И log(n) растет достаточно медленно, поэтому вы можете считать его достаточно близким к постоянному во всех практических наборах данных. (От 1000 до 1 петабайта он варьируется в 5 раз.) И часто активно запрашиваемые данные показывают какую-то местность, какие деревья лучше хранят в оперативной памяти. В результате деревья несколько чаще встречаются на практике. (Хотя хэши отнюдь не редкость.)
Это зависит от ряда факторов, включая реализацию механизма базы данных, стратегию индексирования, специфику запроса, доступное оборудование, конфигурацию базы данных и т. Д.
Нет возможности ответить на такой общий вопрос.
Правильно спроектированная и реализованная база данных с терабайтами данных может на самом деле превзойти плохо спроектированную небольшую базу данных (в частности, базу без индексации и базу данных, которая использует плохо выполняемые несаркируемые запросы и такие вещи, как коррелированные подзапросы). Вот почему любой, кто ожидает больших объемов данных, должен нанять специалиста по проектированию баз данных для больших баз данных, чтобы сделать первоначальный проект не позднее, когда база данных велика. Вам также может понадобиться инвестировать в тип оборудования, которое вам необходимо для обработки размера.