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

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

 CREATE INDEX ... USING HASH 

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

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

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

Вы можете получить 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 слотов в массиве.

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

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

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

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

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

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

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

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

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

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