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