Сложность поиска по индексу в B-дереве или B+ дереве (наиболее распространенные типы индексов) примерно равна O(log N), где N - количество записей в таблице.
Эта логарифмическая сложность обусловлена древовидной структурой индекса. На каждом уровне дерева мы выбираем ветвь, содержащую нужный диапазон ключей, существенно сокращая пространство поиска. Высота дерева, а следовательно и количество шагов для поиска, растет по мере логарифму от количества записей.
Пример: в дереве с 1 миллионом записей, если каждый узел может содержать 100 указателей, высота дерева будет примерно log<sub>100</sub>(1,000,000) = 3. Это означает, что для поиска записи потребуется пройти всего около 3 узлов.