Лекция: Блочный поиск
Снова вспомним пример с записной книжкой. Пусть в вашей записной книжке имеется алфавитный индекс в виде вырезанной «лесенки» или в виде букв вверху страницы. Несколькостраниц, помеченных одной буквой, назовем блоком. Имеется блок «А», блок «Б» и т. д. до блока «Я».
Индекс – это часть ключа поиска (например, первая буква).
Записи телефонов и адресов расставлялись в записной книжке по блокам в соответствии с первой буквой. Однако внутри блока записи не упорядочены в алфавитном порядке следующих букв, как это делается в словарях и энциклопедиях. Записи вкнижке мы ведем в порядке поступления. При такой организации данных поиск нужного телефона будет происходить блочно-последовательным методом:
1) с помощью алфавитного индекса выбирается блок с нужной буквой;
2) внутри блока поиск производится путем последовательного перебора.
Большинство книг в начале или в конце текста содержат оглавления: список названий разделов с указанием страниц, с которых они начинаются. Разделы – это те же блоки. Поиск нужной информации в книге начинается с просмотра оглавления, с дальнейшим переходом к нужному разделу, который затем просматривается последовательно. Очевидно, это тот же блочно-последовательный методпоиска.
Списки с указанием на блоки данных называются списками указателей.
Разбиение данных на блоки может быть многоуровневым. В толстых словарях блок на букву «А» разбивается, например, на блоки по второй букве: блок от «АБ» до «АЖ», следующий от «AЗ» до «АН» и т.д. Такой порядок называется лексикографическим.
В поисковом множестве с многоуровневой блочной структурой происходит поиск методом спуска:сначала отыскивается нужный блок первого уровня, затем второго и т.д. Внутри блока последнего уровня может происходить либо последовательный поиск (если данных в нем относительно немного), либо оптимизированный поиск типа половинного деления. Поиску методом спуска часто помогают многоуровневые списки указателей.