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

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

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

Содержание

Причины ускорения поиска
Структура реляционной таблицы
Индексация
Обязательное создание индексов
Недостатки индексирования
Способы поиска информации

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

Очень простой вопрос, ответ на который ушел в «серую зону» знания.


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


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

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

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

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

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


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


Индексация

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

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

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

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

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

В случае наличия индекса (упорядоченного перечня), появляется возможность воспользоваться так называемым двоичным поиском.


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


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

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


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


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

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

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

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

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

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

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


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


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

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

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

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

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

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

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

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

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


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


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

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


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


Наиболее существенным для реализации всего перечисленного является правильная разработка структуры БД и, основанное на этом, создание постоянных индексов. Любые нестыковки приведут к задержкам в выполнении запросов, прямо пропорционально размерам таблиц.

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

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


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