Как работает хеш-таблица? Это быстрее, чем «SELECT * from ..»

Question

Допустим, у меня есть:

Key | Indexes | Key-values
----+---------+------------
001 | 100001  | Alex
002 | 100002  | Micheal
003 | 100003  | Daniel

Допустим, мы хотим найти 001, как выполнить быстрый процесс поиска с использованием хеш-таблицы?

Разве это не то же самое, что мы используем "SELECT * from .." в mysql? Я много читаю, говорят, «SELECT *» ищет от начала до конца, но хеш-таблица не? Почему и как?

Используя хеш-таблицу, сокращаем ли мы записи, которые ищем? Как?

Может кто-нибудь продемонстрировать, как вставить и получить процесс хэш-таблицы в код запроса MySQL? например,

SELECT * from table1 where hash_value="bla" ...

Другой сценарий: Если индексы похожи на S0001, S0002, T0001, T0002 и т. Д. В MySQL я мог бы использовать:

SELECT * from table WHERE value = S*

Разве это не то же самое и быстрее?

Answer 1

Простая хеш-таблица работает, сохраняя элементы в нескольких списках вместо одного. Он использует очень быстрый и повторяемый (то есть неслучайный) метод, чтобы выбрать, в каком списке хранить каждый элемент. Поэтому, когда пришло время снова найти элемент, он повторяет этот метод, чтобы определить, в каком списке искать, и затем выполняет обычный (медленный) линейный поиск в этом списке.

Разделение элементов на 17 списков ускоряет поиск в 17 раз, что является хорошим улучшением.

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

В вашем примере таблицы первый столбец - это ключ, то, что нам нужно, чтобы найти элемент. И давайте предположим, что мы будем поддерживать 17 списков. Чтобы вставить что-то, мы выполняем операцию с ключом, называемую хэшированием. Это просто превращает ключ в число. Он не возвращает случайное число, потому что он всегда должен возвращать одно и то же число для одного и того же ключа. Но в то же время цифры должны «широко распространяться».

Затем мы берем полученное число и используем модуль, чтобы уменьшить его до размера нашего списка:

Hash(key) % 17

Все это происходит очень быстро. Наши списки находятся в массиве, поэтому:

_lists[Hash(key % 17)].Add(record);

А потом, чтобы найти предмет с помощью этого ключа:

Record found = _lists[Hash(key % 17)].Find(key);

Обратите внимание, что каждый список может быть контейнером любого типа или классом связанного списка, который вы пишете вручную. Когда мы выполняем Find в этом списке, он работает медленно (проверьте ключ каждой записи).

Answer 2

Не беспокойтесь о том, что делает MySQL для быстрого поиска записей. Работа базы данных заключается в том, чтобы делать такие вещи для вас. Просто выполните запрос SELECT [columns] FROM table WHERE [condition]; и позвольте базе данных сгенерировать план запроса для вас. Обратите внимание, что вы не хотите использовать SELECT *, поскольку, если вы когда-нибудь добавите в таблицу столбец, который сломает все ваши старые запросы, которые основывались на определенном количестве столбцов в определенном порядке.

Если вы действительно хотите знать, что происходит под капотом (это полезно знать, но не реализуйте это сами: это цель базы данных! ), вам нужно знать, какие индексы есть и как они работают. Если у таблицы нет индекса по столбцам, включенным в предложение WHERE, то, как вы говорите, базе данных придется искать по каждой строке в таблице, чтобы найти те, которые соответствуют вашему условию. Но если является индексом, база данных будет искать в индексе точное местоположение нужных вам строк и переходить непосредственно к ним. Индексы обычно реализуются как B + -деревья , тип дерева поиска, которое использует очень мало сравнений для определения местоположения определенного элемента. Поиск B-дерева для определенного ключа очень быстрый. MySQL также может использовать хеш-индексы, но они, как правило, медленнее для использования баз данных. Хеш-индексы обычно работают хорошо только на длинных ключах (особенно в символьных строках), так как они уменьшают размер ключа до фиксированного размера хеша. Для типов данных, таких как целые и действительные числа, которые имеют четко определенный порядок и фиксированную длину, легкая возможность поиска B-дерева обычно обеспечивает лучшую производительность.

Возможно, вы захотите взглянуть на главы в Руководстве MySQL и Руководстве PostgreSQL по индексированию.

Answer 3

http://en.wikipedia.org/wiki/Hash_table

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

Answer 4

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

ВЫБРАТЬ * ИЗ таблицы, ГДЕ значение = hash_fn (независимо от_произведения_вс_билд_в_схиме_схемы)

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

Однако это не всегда так в зависимости от размера таблицы и максимального числа хеш-значений (где-то в вашем хеше часто есть «X mod-hash-table-size»). Чтобы позаботиться об этом, у вас должна быть детерминированная стратегия, которую вы используете каждый раз, когда получаете два значения с одинаковым идентификатором. Вам следует проверить Википедию для получения дополнительной информации об этой стратегии, которая называется обработкой коллизий и должна быть упомянута в той же статье, что и хеш-таблицы.

MySQL, вероятно, где-то использует хеш-таблицы из-за упомянутой возможности O (1) norheim.se (вверх).

Answer 5

Хеш-таблицы отлично подходят для поиска записей по цене O (1), где ключ (который используется для хеширования) уже известен. Они широко используются как в библиотеках коллекций, так и в механизмах баз данных. Вы должны быть в состоянии найти много информации о них в Интернете. Почему бы вам не начать с Википедии или просто выполнить поиск в Google?

Я не знаю деталей mysql. Если там есть структура, называемая «хэш-таблица», то это, вероятно, будет своего рода таблица, в которой для поиска ключей используется хэширование. Я уверен, что кто-то еще скажет вам об этом. =)

РЕДАКТИРОВАТЬ: (в ответ на комментарий)

Ok. Я попытаюсь сделать упрощенное объяснение: хеш-таблица - это таблица, в которой записи расположены в зависимости от функции ключа. Например, скажем, что вы хотите хранить информацию о наборе людей. Если вы храните его в обычном несортированном массиве, вам нужно будет последовательно перебирать элементы, чтобы найти искомую запись. В среднем для этого потребуется сравнение N / 2.

Если вместо этого вы помещаете все записи в индексы, основанные на первом символе имени человека. (A = 0, B = 1, C = 2 и т. Д.), Вы сразу сможете найти правильную запись, если знаете имя. Это основная идея. Возможно, вы понимаете, что для поддержки нескольких записей, имеющих одну и ту же первую букву, требуется некоторая специальная обработка (перефразировка или разрешение списков записей) Если у вас есть хеш-таблица с большими размерами, вы сможете сразу перейти к искомому элементу. Это означает приблизительно одно сравнение с отказом от специальной обработки, которую я только что упомянул.