Информатика | Официальный сайт московской государственной гимназии 1549

Методические материалы по информатике

Базы данных: поиск информации

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

  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 шагов, только считать будет сложнее.)

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

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

10 1 024
11 2 048
12 4 096
13 8 192
14 16 384
15 32 768
16 65 536
17 131 072
18 262 144
19 524 288
20 1 048 576
21 2 097 152
22 4 194 304
23 8 388 608
24 16 777 216
25 33 554 432
26 67 108 864
27 134 217 728
28 268 435 456
29 536 870 912
30 1 073 741 824
31 2 147 483 648
32 4 294 967 296
33 8 589 934 592
34 17 179 869 184
35 34 359 738 368
36 68 719 476 736
37 137 438 953 472
38 274 877 906 944
39 549 755 813 888
40 1 099 511 627 776
41 2 199 023 255 552
42 4 398 046 511 104
43 8 796 093 022 208
44 17 592 186 044 416
45 35 184 372 088 832
46 70 368 744 177 664
47 140 737 488 355 328
48 281 474 976 710 656
49 562 949 953 421 312
50 1 125 899 906 842 624
51 2 251 799 813 685 248
52 4 503 599 627 370 496
53 9 007 199 254 740 992
54 18 014 398 509 481 984

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

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

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

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

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

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