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

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

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

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

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

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

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

Что же это даёт? Если в обычной программе для перехода к следующей строчке пришлось бы последовательно перебирать все символы для нахождения конца строки, то в БД всё намного проще, так как следующую запись искать не нужно. Надо просто сместиться на количество байт, соответствующее сумме размеров полей. Если смещение происходит на несколько записей, то полученное число надо умножить на количество «перескакиваемых» записей.

То есть, для нашего примера, вторая запись начнется со 101 байта (100×1+1), а 1001-я — со 100 001 байта (100×1000+1).

Переход с записи 1001 на 2001 означает смещение на 1000 записей (2001 – 1001) или 100 000 байтов (100×1000). При этом мы окажемся на 200 001 байте от начала файла (100×2000+1). И расчет, и сам переход произойдут практически мгновенно и это время никак не будет зависеть от "дальности" перемещения.

Индексация

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

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

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

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

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

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

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

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

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

  1. Делим совокупность значений пополам и исследуем запись 512 (29).
  2. Делим совокупность значений пополам и исследуем запись 256 (28).
  3. —"— 128 (27).
  4. —"— 64 (26).
  5. —"— 32 (25).
  6. —"— 16 (24).
  7. —"— 8 (23).
  8. —"— 4 (22).
  9. —"— 2 (21).
  10. Делим пополам и исследуем запись 1 (20).

Если запись №1 больше искомого, то результат отрицательный. В противном случае мы нашли нужную запись. И проделали это не более, чем за 10 попыток. (А ведь могли найти и раньше!)

(Изменив условие «всегда меньше» вы получите те же 10 шагов, только считать будет сложнее.)

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

Первая колонка в приведенной ниже таблице описывает число необходимых сравнений (n), а вторая — 2n или количество сравниваемых объектов.
101 024
112 048
124 096
138 192
1416 384
1532 768
1665 536
17131 072
18262 144
19524 288
201 048 576
212 097 152
224 194 304
238 388 608
2416 777 216
2533 554 432
2667 108 864
27134 217 728
28268 435 456
29536 870 912
301 073 741 824
312 147 483 648
324 294 967 296
338 589 934 592
3417 179 869 184
3534 359 738 368
3668 719 476 736
37137 438 953 472
38274 877 906 944
39549 755 813 888
401 099 511 627 776
412 199 023 255 552
424 398 046 511 104
438 796 093 022 208
4417 592 186 044 416
4535 184 372 088 832
4670 368 744 177 664
47140 737 488 355 328
48281 474 976 710 656
49562 949 953 421 312
501 125 899 906 842 624
512 251 799 813 685 248
524 503 599 627 370 496
539 007 199 254 740 992
5418 014 398 509 481 984

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

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

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

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

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

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

Во-первых, любое изменение поля, в том числе и при добавлении/удалении записи приведет к необходимости исправления индекса, а на это требуется время. Проблема может встать столь остро, что, при массовых изменениях, намного быстрее удалить все индексы, произвести изменения, а затем заново создать индексы.

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

В-третьих, бездумное создание индексов может привести к расходованию места на диске, на несколько порядков превышающее то, которое занимают таблицы БД, то есть собственно информация.

В-четвертых, индексы хранятся в оперативной памяти, а ее намного меньше, чем дисковой. Докачка индексов в память во время поиска также приводит к замедлению.

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

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

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

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

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

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

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


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


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

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


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