Руководство по созданию эффективных запросов

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

---

Алгоритмы доступа к данным 

41
ной таблице. Такое соотношение называется 
селективностью
(
избиратель-
ностью)
. Выбор алгоритма для определенной операции чтения зависит от 
селективности фильтров, которые могут применяться одновременно.
Представление данных
Неудивительно, что данные хранятся в файлах на жестких дисках. Любой 
файл, используемый для объектов базы данных, делится на блоки одинако-
вой длины; по умолчанию PostgreSQL использует блоки по 8192 байта каж-
дый. Блок – это единица, которая передается между жестким диском и опе-
ративной памятью, а количество операций ввода-вывода, необходимое для 
выполнения любого доступа к данным, равно количеству блоков, которые 
читаются или записываются.
Объекты базы данных состоят из логических элементов (строк таблиц, ин-
дексных записей и т. д.). PostgreSQL выделяет место для этих элементов бло-
ками. Несколько мелких элементов могут находиться в одном блоке; более 
крупные элементы могут быть распределены между несколькими блоками. 
Общая структура блока показана на рис. 3.1.
Заголовок блока
Указатели 
на логические 
элементы
Свободное 
пространство
Логические 
элементы 
(строки таблицы, 
индексные записи 
и т. д.)
Конец блока
Рис. 3.1 

Общая структура блока в PostgreSQL
Распределение элементов по блокам также зависит от типа объекта базы 
данных. Строки таблицы хранятся с использованием структуры данных, на-
зываемой кучей (heap): строка может быть вставлена в любой блок, в котором 
достаточно свободного места, без специального упорядочивания. Другие 
объекты (например, индексы) могут использовать блоки иначе.

---