В «правильной» реляционной таблице каждое поле имеет фиксированную ширину, обычно называемую длинной поля. Это порождает определенные издержки: ведь не каждое поле будет заполняться полностью, а место для них всё равно уже отведено. Сама же длина конкретного поля будет задаваться тем значением, которое имеет наибольшее количество символов.
Для дальнейших рассуждений условимся, что у нас есть таблица с 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 больше искомого, то результат отрицательный. В противном случае мы нашли нужную запись. И проделали это не более, чем за 10 попыток. (А ведь могли найти и раньше!)
(Изменив условие «всегда меньше» вы получите те же 10 шагов, только считать будет сложнее.)
Можно сказать, что современные компьютеры выполняют миллионы операций за секунду и всё перечисленное не имеет значения.
Первая колонка в таблице описывает число необходимых сравнений (n), а вторая – 2n или количество сравниваемых объектов.
|
|
|
Синим в таблице показано число вариантов, кодируемое 2, 3, 4, 5 и 6-ю байтами. Красным – примерное число, соответствующее населению Земли. Таким образом, двоичным поиском можно найти любого человека не более, чем за 33 операции сравнения в базе данных.
Как уже было сказано, ускорение происходит и за счет загрузки данных в оперативную память. И в первую очередь это относится к индексам. Но надо понимать, что доступный объем памяти всегда ограничен. Это определяет важнейшее требование: индексы должны создаваться только те, которые используются постоянно или регулярно. Создание индекса «на всякий случай» – грубая ошибка.
В качестве послесловия надо отметить, что для создания индекса компьютер должен: прочитать все данные, отсортировать их, сохранить в виде файла. Происходит это намного дольше, чем последовательный перебор, но эта процедура потребуется только один раз. В дальнейшем, индекс будет изменяться только при изменении значений индексированного поля. В том числе и при создании новых записей.
Там где часто происходит поиск и поля, часто выводимые на экран. При реальной разработке эксперименты осложняются тем, что таблицы не заполнены значительным количеством записей и всё происходит быстро. жесткость структуры, индексы, оперативная память