Как базы данных эффективны?

Полный ответ - тема многочисленных книг и диссертаций; -)

Однако основной ответ заключается в том, что все современные СУБД имеют несколько функций : Во-первых, у них есть очень эффективный оптимизатор запросов. Это поможет найти хороший (не всегда лучший) путь для ответа на предоставленный запрос. Конечно, это может помочь решить сложные вопросы больше, чем простые.

Во-вторых, они хранят данные в структурированном формате, в котором легко искать. Данные без кластеризованного индекса называются кучей, и это, как правило, менее эффективно для поиска, но это все же структурированные данные. Данные обычно имеют кластерный индекс, который логически упорядочивает данные. (Некоторые люди считают, что он физически упорядочивает данные. В этом есть доля правды, но это не совсем правда. Среди других есть отличная статья, опровергающая это убеждение, Ицик Бен Ган).

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

Это, конечно, грубое и ужасное упрощение. Если вы хотите глубокого понимания, будьте готовы получить докторскую степень по теории баз данных. Для понимания общего уровня вы можете взглянуть на книги о внутреннем устройстве баз данных. В частности, для SQL Server в SQL Server 2008 Internals есть много информации по этой теме.

Мне очень нравится Это объяснение (включая графику;)

Это заключение статьи:

Заключение

_{(источник: mattfleming.com )}

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