Здравствуйте, Serginio1, Вы писали:
V>>При джоинах на индексе этот алгоритм для каждой строчки выполняется не в "чистом" виде, а лишь по интервалу от предыдущего найденного значения (соединяются-то сортированные наборы), т.е. в случае простого join== почти всегда сводится к операции перехода на следующую строку, если текущая строка основного ключа не подошла строке внешнего ключа. S>Да и это ерунда, так ка данные находятся в кэше. Это малая величина по сравнению с основным временем поиска.
Эти рассуждения устарели лет эдак на 15.
Мы тут уже разбирали, что для десктопов уже доступны относительно быстрые RAID-технологии поверх SSD.
Относительно скорости оперативной памяти, разумеется, бо они уже примерно одного порядка.
Поэтому уже относительно давно можно рассуждать о "чистой" стоимости алгоритмов, без разбиения их на "бесплатную" часть поверх RAM и "платную" часть доступа к диску.
Усё, обе части одинаково платные.
Отсюда и пляшем.
S> Еще раз я для чего тебе ссылку то давал. При поиске останавливается на месте которое меньше или равно.
Или на месте, которое больше или равно — это зависит от конкретного вида алгоритма бинарного поиска: "Upper Bound" vs "Lower Bound".
Или возвращает две позиции, между которыми должно находиться искомое значение — бо классический алгоритм "binary search" оперирует парой индексов.
Разновидности Upper/Lower Bound возвращают один индекс, т.е. отличаются лишь своей концовкой, когда принимается решение — какой из двух результирующих индексов выкинуть.
В любом случае, когда речь идёт о "слиянии" отсортированных последовательностей, то применять эти алгоритмы в чистом виде — нубство.
Например, есть разновидности слияния с двух концов таких последовательностей одновременно, бо в этом случае на каждой итерации область поиска сужается.
И, хотя с математической верхний предел сложности у такого алгоритма такой же, но нижний резко отличается, в том числе из-за чисто "механических" причин — более близкие индексы более близко расположены на диске и в памяти.
S>Почитай алгоритм. Он кстати используется и для вставки если ключ не найден.
