Почему поиск по индексу имеет логарифмическую сложность?

Question

Индекс не похож на словарь? Если у вас есть ключ, вы можете сразу получить к нему доступ?

Очевидно, что индексы иногда хранятся в виде B-деревьев ... почему?

Answer 1

Словари не сортируются неявно, B-Tree s.

Индекс B-Tree можно использовать для доступа на расстоянии, например:

WHERE col1 BETWEEN value1 AND value2

или заказ, как это:

ORDER BY col1

Вы не можете сразу получить доступ к странице в индексе B-Tree: вам нужно просмотреть дочерние страницы, число которых увеличивается логарифмически.

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

Answer 2

Индексы базы данных обычно (почти всегда) хранятся как B-деревья. И все сбалансированные древовидные структуры имеют O (log n) сложность для поиска.

«Словарь» - это «Абстрактный тип данных» (ADT), т. Е. Это функциональное описание, которое не обозначает реализацию. Некоторые словари могут использовать поиск Hashtable для O (1), другие могут использовать дерево и достичь O (log n).

Основная причина, по которой БД использует B-деревья (по сравнению с любым другим видом дерева), заключается в том, что B-деревья являются самобалансирующимися и очень «мелкими» (требующими небольшого дискового ввода-вывода)

Answer 3

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

Хеш может быть эффективным, но требует больше места и в конечном итоге приведет к коллизиям.

Дерево B имеет хороший баланс между производительностью поиска и пространством.

Answer 4

Если ваши единственные запросы - это тесты на равенство, то, по правде говоря, словари являются хорошим выбором, так как они будут выполнять поиск за амортизированное O (1) время. Однако, если вы хотите расширить запросы, включив проверки диапазона, например (select * from students where age > 10), тогда ваши словари внезапно полностью теряют свои преимущества. Именно здесь появляются древовидные индексы. С помощью древовидного индекса вы можете выполнять равенства диапазон проверок в логарифмическом времени.

Существует одна проблема с наивными древовидными структурами. Они становятся несбалансированными, это означает, что после добавления определенных значений в индекс древовидная структура становится однобокой (например, длинной строкой), и поиск снова начинает занимать O (N). Это может быть решено путем балансировки вашего дерева. B-Tree является одним из таких подходов, который также использует преимущества систем, способных выполнять большие блоки ввода / вывода, и поэтому наиболее подходит для баз данных.

Answer 5

Хэши - это самые быстрые структуры данных для поиска, но есть некоторые проблемы:

а) не отсортированы б) независимо от того, насколько хорош хеш, будут возникать коллизии, что становится проблематично при большом количестве данных c) для поиска хеш-значения в индексируемом хэш-файле требуется много времени, поэтому хеширование в большинстве случаев имеет смысл только для данных в оперативной памяти (ОЗУ), что делает их непригодными для баз данных, которые в большинстве случаев не подходят данные в ОЗУ

Сортированные деревья решают эти проблемы, и, в частности, операции с b-деревьями могут быть эффективно реализованы с использованием файлов. Единственный недостаток - они имеют более медленное время поиска в виде хэш-структуры.

Ни одна структура данных не является идеальной во всех случаях, в зависимости от предполагаемого размера данных и того, как вы их используете, лучше.

Answer 6

Вы можете достичь O(1), если предварительно выделите N записей массив и хэш ключ к этим N значениям ,

Но тогда, если у вас хранится более N записей, возникает коллизия. Таким образом, для каждого ключа в массиве у вас есть список значений . Так что это уже не точно O(1). Сканирование самого списка будет O(m), где m - среднее число столкновений.

Example with hash = n mod 3
0  -->  [0,a] [3,b] ...
1  -->  [1,a] [4,b] [7,b] ...
2  -->  [2,a] [5,b] ...

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

Конечно, вы можете выбрать N настолько большим, что массив / хэш будет быстрее, чем B-Tree. Но массив имеет фиксированный предварительно выделенный размер. Так что если N = 1000 и вы сохраняете 3 значения, вы потеряли 997 слотов в массиве.

Так что это, по сути, компромисс производительности компромисс. Для небольшого набора значений отлично подходит array и хеширование. Для большого набора значений наиболее эффективны B-Tree.

Answer 7

hashindex (например, в mysql и postgres) имеет постоянную сложность (O (1)) для поиска.

 CREATE INDEX ... USING HASH