Поиск информации

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

Попробуем внести в это некоторую ясность.

Причины ускорения поиска

  1. Жесткая структура реляционных таблиц с фиксированным размером каждого поля.
  2. Наличие индексов.
  3. Загрузка данных со сравнительно медленного жесткого диска в быструю оперативную память.

Структура реляционной таблицы

Под структурой реляционной таблицы понимают описание образующих её полей: наименование, тип хранимых данных, размер поля в байтах.

В «правильной» реляционной таблице каждое поле имеет фиксированную ширину, обычно называемую длинной поля. Это порождает определенные издержки: ведь не каждое поле будет заполняться полностью, а место для них всё равно уже отведено. Сама же длина конкретного поля будет задаваться тем значением, которое имеет наибольшее количество символов.

Для дальнейших рассуждений условимся, что у нас есть таблица с 10 полями по 10 символов. В сумме на одну запись это даст 100 символов или 100 байтов хранимой на диске информации.

Что же это даёт?


Доступ к этим материалам предоставляется только зарегистри­рован­ным пользователям!


Индексация

Индексация или индексирование — создание специального файла, содержащего упорядоченные значения (текст по алфавиту, числа/даты в порядке возрастания или убывания и т.д.) с номерами их записей.

Зачем создавать индексы? Ведь они будут занимать дополнительное место на диске (число для номера записи, разделитель, полное содержимое поля или суммы нескольких полей), причем настолько немаленькое, что могут оказаться больше самой базы данных!

Для того, чтобы это понять, давайте порассуждаем, как происходит поиск информации в файле.

Задав условие поиска (пусть это будет буква «а»), мы вынуждаем компьютер последовательно перебирать все символы, содержащиеся в файле и для каждого задавать вопрос: «Не "а" ли этот символ»? В обычных условиях объем информации сравнительно невелик, перебор и сравнение с образцом происходит быстро и, в сумме, полный поиск не занимает много времени. Именно эти рассуждения, помноженные на рост вычислительных возможностей, легли в основу большинства современных ложных концепций и мифов.

Однако, если представить себе таблицу с миллионами или миллиардами строк, да ещё учесть довольно большое время перехода от строки к строке, то подобный перебор может занять минуты, а то и часы.

В случае наличия индекса (упорядоченного перечня), появляется возможность воспользоваться так называемым двоичным поиском. Его смысл заключается в том, что все данные делятся пополам (формально это соответствует степени числа 2) и определяется, больше искомое значение, чем серединное или меньше?

Попробуем оценить поиск для 1024 записей (210) двумя способами.

Последовательный перебор. Даже без учета скорости перемещения между записями, в худшем случае, нам придется просмотреть все 1024 записи. С точки зрения теории вероятностей, нам потребуется в среднем сделать 512 переборов. Проще говоря, половину от числа записей, что на больших объемах и займет очень много времени. Так работает абсолютно подавляющее большинство приложений.

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


Доступ к этим материалам предоставляется только зарегистри­рован­ным пользователям!


Можно сказать, что современные компьютеры выполняют миллионы операций за секунду и всё перечисленное не имеет значения. Но, на практике, перебор записей в таблице из 1 млн строк на весьма быстром компьютере занимает несколько десятков секунд. Подобные задержки не позволили бы пользоваться большими массивами данных для поиска и анализа. Двоичный же поиск полностью снимает остроту проблемы. Издержки — расходование места для хранения индексных файлов.

Первая колонка в приведенной ниже таблице описывает число необходимых сравнений (n), а вторая — 2n или количество сравниваемых объектов.


Доступ к этим материалам предоставляется только зарегистри­рован­ным пользователям!


Синим в таблице показано число вариантов, кодируемое 2, 3, 4, 5 и 6-ю байтами. Красным — примерное число, соответствующее населению Земли. Таким образом, двоичным поиском можно найти любого человека не более, чем за 33 операции сравнения в базе данных.

Причины для создания индекса (назначение):

  1. Вывод упорядоченных данных, то есть расположенных в порядке возрастания или убывания значений. Данный смысл условно можно считать спорным.
  2. Необходимость быстрого поиска.

Как уже было сказано, ускорение происходит и за счет загрузки данных в оперативную память. И, в первую очередь, это относится к индексам. Но надо понимать, что доступный объем памяти всегда ограничен. Это определяет важнейшее требование: индексы должны создаваться только те, которые используются постоянно или регулярно. Создание индекса «на всякий случай» — грубая ошибка.

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

Недостатки индексирования

Не стоит безоглядно хвалить что бы то ни было, так как у всего есть отрицательные качества. Каковы же они у индексов?


Доступ к этим материалам предоставляется только зарегистри­рован­ным пользователям!


Обязательное создание индексов

При реальном создании БД, также, как и при выполнении учебных заданий, неизбежно встают вопросы: для каких полей создавать индекс надо, для каких стоит подумать, а когда их создание будет ошибкой?

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

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

Сразу отмечу для студентов: указывать индексы для первичных полей (кодов) можно, но не обязательно. Это вытекает из совсем первичной сути и не может рассматриваться ни в качестве работы, ни в качестве ошибки.

При реальной разработке эксперименты осложняются тем, что таблицы не заполнены значительным количеством записей и всё происходит быстро. Оценить эффект не представляется возможным.

Немного спекуляции, основанной на правде жизни. Если индекса(ов) нет, то выполнение запроса на сайте отнимет много ограниченного процессорного времени. Если он есть, то расходуется ограниченная услугой память. Это есть та сущность, которую нам подарила услуга хостинга и её реализация, гм, не совсем грамотными специалистами, оценивающими грамотность разработчиков БД. Проблема в том, что мы дальше должны играть в шараду, никак не формализуемую, так как все прогнозы могут относится лишь к сфере ожидаемого.

Способы поиска информации в БД

В какой-то степени можно говорить, что данный вопрос выдуман лично мной. Сложилось ли это случайно или было вполне закономерным результатом педагогического процесса — сказать сложно, да и не так уж и интересно. Важно другое: разбор этой темы позволяет задуматься над обратной стороной БД — их реальным использованием. А, с учетом нехватки времени на практическую реализацию, да и невозможностью сделать это в нужном объеме, умозрительное восприятие приобретает дополнительную значимость.


Доступ к этим материалам предоставляется только зарегистри­рован­ным пользователям!


Незначительность списка и некоторая «каша»" связана с обратной стороной медали: именно без учета всего изложенного невозможно ни разработать правильную структуру, ни создать комфортное (читай эффективное) рабочее место.

Далее следует обратиться к теме отчетов.

См. также Полнотекстовый поиск


Copyright © 1993–2021 Мацкявичюс Д.А. Все права защищены.
Никакая часть сайта не может быть воспроизведена никаким способом без письменного разрешения правообладателя и явной ссылки на данный ресурс.