Алгоритм соединения хэшированием

Алгоритм соединения хэшированием (hash join) разновидность алгоритма соединения.

Алгоритм получает на вход 2 таблицы и условие соединения. Результатом его работы является таблица с результатами соединения.

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

На псевдокоде алгоритм можно описать примерно так:

[ХэшТаблица] = СтроитьХэшТаблицу([МеньшаяТаблица], [УсловиеСоединения]);
Для каждой строки [r] из [БольшаяТаблица]
   Вывести ([r], ИскатьВХэшТаблице([ХэшТаблица],[r]));

Преимущества:

  • Соединение хэшированием существенно быстрее соединения вложенными циклами. При относительно небольшом размере меньшей таблицы это самый эффективный вид соединения.

Недостатки:

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

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

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home