Алгоритм соединения слиянием сортированных списков: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
Execer (обсуждение | вклад) м стилевые правки |
MBHbot (обсуждение | вклад) м →Ссылки: Project talk:Викификатор#Шаблон:Rq, replaced: {{rq|sources}} → {{подст:нет источников}} |
||
| (не показано 10 промежуточных версий 7 участников) | |||
| Строка 16: | Строка 16: | ||
Таблица1.ВстатьНаПервуюЗапись; |
Таблица1.ВстатьНаПервуюЗапись; |
||
Таблица2.ВстатьНаПервуюЗапись; |
Таблица2.ВстатьНаПервуюЗапись; |
||
Пока Таблица1.НеПоследняяЗапись и |
Пока Таблица1.НеПоследняяЗапись и Таблица2.НеПоследняяЗапись |
||
{ |
{ |
||
Если Таблица1.Колонка1 < Таблица2.Колонка2 |
|||
{ |
|||
Таблица1.ПерейтиКСледующейЗаписи; |
Таблица1.ПерейтиКСледующейЗаписи; |
||
} |
|||
Если Таблица1.Колонка1 = Таблица2.Колонка2 |
Иначе Если Таблица1.Колонка1 = Таблица2.Колонка2 |
||
{ |
{ |
||
Вывести (Таблица1.ТекущаяЗапись, Таблица2.ТекущаяЗапись); |
Вывести (Таблица1.ТекущаяЗапись, Таблица2.ТекущаяЗапись); |
||
Таблица1.ПерейтиКСледующейЗаписи; |
Таблица1.ПерейтиКСледующейЗаписи; |
||
Таблица2.ПерейтиКСледующейЗаписи; |
|||
} |
} |
||
| ⚫ | |||
| ⚫ | |||
{ |
{ |
||
Таблица2.ПерейтиКСледующейЗаписи; |
Таблица2.ПерейтиКСледующейЗаписи; |
||
| Строка 35: | Строка 36: | ||
== Преимущества == |
== Преимущества == |
||
* Соединение слиянием эффективнее, чем |
* Соединение слиянием эффективнее, чем [[алгоритм соединения вложенными циклами]], при условии, что списки изначально были отсортированы. В принципе, накладные расходы на сортировку могут быть распределены между несколькими операциями соединения. |
||
* Соединение слиянием в |
* Соединение слиянием в отличие от [[алгоритм соединения хешированием|соединения с использованием хеширования]] может использоваться при больших размерах соединяемых таблиц. |
||
* Соединение слиянием может использоваться для соединений с условиями отличными от равенства, чего не позволяет [[алгоритм соединения хэшированием]]. Однако допустимы не любые условия соединения. |
|||
== Недостатки == |
== Недостатки == |
||
* Главным недостатком алгоритма является необходимость в |
* Главным недостатком алгоритма является необходимость в предварительной сортировке списков. Накладные расходы на сортировку могут быть неприемлемо высокими. |
||
* При |
* При реализации в [[СУБД]], соединение слиянием требует больше памяти и менее гибко, чем [[алгоритм соединения вложенными циклами]]. В связи с этим на практике рекомендуют избегать этого вида соединения. Во многих СУБД соединение слиянием по умолчанию не используется оптимизатором запросов и должно быть включено явно. |
||
* Соединение слиянием, как и [[алгоритм соединения хешированием]], требует в условиях наличия не менее одного условия равенства. |
|||
== Ссылки == |
== Ссылки == |
||
* [http://www.sql.ru/articles/mssql/2007/051102mergejoin.shtml#20 Craig Freedman: Материалы статьи Merge Join] |
* [http://www.sql.ru/articles/mssql/2007/051102mergejoin.shtml#20 Craig Freedman: Материалы статьи Merge Join] |
||
{{Нет источников |дата=2024-10-19}} |
|||
{{rq|sources}} |
|||
[[Категория:СУБД]] |
[[Категория:СУБД]] |
||
[[Категория:Алгоритмы]] |
[[Категория:Алгоритмы баз данных]] |
||
Текущая версия от 11:23, 19 октября 2024
Алгоритм соединения слиянием сортированных списков (merge join, sort merge join, sort-merge join) — разновидность алгоритма соединения.
Алгоритм получает на вход две таблицы и условие соединения. Результатом его работы является таблица с результатами соединения.
Входные таблицы должны быть отсортированы по столбцам, участвующим в условии соединения. Соединение осуществляется за одно сканирование (проход по) каждой из входных таблиц. То есть одна и та же строка считывается только один раз, что даёт преимущество перед соединением вложенными циклами.
Простой пример на псевдокоде:
//нужно соединить Таблицу 1 и Таблицу 2
//по условию: Таблица1.Колонка1 = Таблица2.Колонка2
//Для упрощения примера будем считать, что значения в Колонке2 уникальны
Таблица1.Сортировать(Колонка1);
Таблица2.Сортировать(Колонка2);
Таблица1.ВстатьНаПервуюЗапись;
Таблица2.ВстатьНаПервуюЗапись;
Пока Таблица1.НеПоследняяЗапись и Таблица2.НеПоследняяЗапись
{
Если Таблица1.Колонка1 < Таблица2.Колонка2
{
Таблица1.ПерейтиКСледующейЗаписи;
}
Иначе Если Таблица1.Колонка1 = Таблица2.Колонка2
{
Вывести (Таблица1.ТекущаяЗапись, Таблица2.ТекущаяЗапись);
Таблица1.ПерейтиКСледующейЗаписи;
Таблица2.ПерейтиКСледующейЗаписи;
}
Иначе Если Таблица1.Колонка1 > Таблица2.Колонка2
{
Таблица2.ПерейтиКСледующейЗаписи;
}
}
Преимущества
[править | править код]- Соединение слиянием эффективнее, чем алгоритм соединения вложенными циклами, при условии, что списки изначально были отсортированы. В принципе, накладные расходы на сортировку могут быть распределены между несколькими операциями соединения.
- Соединение слиянием в отличие от соединения с использованием хеширования может использоваться при больших размерах соединяемых таблиц.
Недостатки
[править | править код]- Главным недостатком алгоритма является необходимость в предварительной сортировке списков. Накладные расходы на сортировку могут быть неприемлемо высокими.
- При реализации в СУБД, соединение слиянием требует больше памяти и менее гибко, чем алгоритм соединения вложенными циклами. В связи с этим на практике рекомендуют избегать этого вида соединения. Во многих СУБД соединение слиянием по умолчанию не используется оптимизатором запросов и должно быть включено явно.
- Соединение слиянием, как и алгоритм соединения хешированием, требует в условиях наличия не менее одного условия равенства.
Ссылки
[править | править код] | В статье не хватает ссылок на источники (см. рекомендации по поиску). |