[МУЗЫКА]
[МУЗЫКА] Здравствуйте!
Сегодня мы поговорим с вами о физическом хранении таблиц.
SQL является декларативным языком, и когда мы определяли структуры таблиц,
то мы не обращали внимания на то, каким образом данные будут храниться на диске.
И, в принципе, пользователь может этого не знать.
Но для того, чтобы правильно писать запросы и строить дополнительные
структуры, которые позволят выполнить ваши запросы оптимальным способом,
нам нужно все-таки немножко заглянуть внутрь и посмотреть,
как же хранятся данные непосредственно на диске.
Существует два принципиальных подхода к хранению таблиц.
Первый подход — это построчное хранение, второй подход — колоночное хранение.
Наибольшее распространение получил первый подход.
На нем мы сегодня остановимся.
Основной единицей хранения данных на диске являются страницы,
и мы стараемся располагать строки таблицы так,
чтобы каждая строка целиком размещалась в одной странице.
Страница — это очень небольшое количество данных,
поэтому они объединяются в более крупные единицы, называемые экстентами.
Как оценить скорость доступа к данным?
Обычно операции, которые производятся в оперативной памяти, выполняются быстро,
потому что скорость доступа к оперативной памяти намного больше, чем доступ к диску.
Поэтому оценивать мы будем при помощи подсчета операций с дисковой памятью:
сколько страниц нам нужно считать, чтобы добраться до нашей записи.
Первый способ организации таблицы — это хранение файлов,
так называемое «файлы в виде кучи» или хранение таблицы с добавлением в конец.
В таком случае мы не организуем никакого порядка в наших записях,
и записи добавляются в конец файла по мере поступления.
Конечно, записи могут удаляться, и тогда в середине файлов впоследствии образуются
пустые места, которые мы можем заполнять вновь поступившими записями,
а можем так и оставлять эти места свободными.
Попробуем оценить поиск в таблице с добавлением в конец.
У нас нет другого способа для организации поиска,
кроме как полного сканирования таблицы.
Так называется просмотр всех блоков, начиная с первого,
пока мы не найдем нужную запись.
В среднем, наша запись может обнаружиться в среднем блоке, потому что
она с равной вероятностью обнаруживается как в первом, так и в последнем.
Поэтому среднее количество блоков, которое нам придется посмотреть, это N / 2.
Попробуем использовать другую организацию файлов: если мы будем хранить наши данные,
отсортированными по какому-то значению ключа.
В таком случае у нас, конечно, сложнее будут происходить операции вставки
и изменений, потому что нам нужно будет поддерживать порядок записи внутри файла.
Зато мы выиграем при такой организации в поиске,
потому что наш поиск сократится до двоичного логарифма от количества блоков,
используемых для хранения записи в таблице.
Представьте, что вы ищете какое-то слово в словаре.
Вы знаете, что словарь у вас отсортирован по возрастанию слов.
Все слова в словаре отсортированы в алфавитном порядке.
Вы можете открыть словарь на середине, определить половинку,
в которой вы ищете слово, эту половинку разделить на 2 и так далее.
Это объясняет вам такую оценку поиска, которая выражается двоичным логарифмом.
Конечно, организация файлов в отсортированном порядке по значению
какого-то ключа дает нам преимущество в поиске,
но двоичный логарифм от количества блоков — это все-таки еще очень большое число.
Поэтому нам могут понадобится какие-то дополнительные структуры,
которые позволят нам производить поиск быстрее.
Для того чтобы нам строить дополнительные структуры,
нам нужно определиться с типами запросов, которые мы хотим выполнять.
Среди типов запросов можно выделить: первое — это поиск на точное
значение ключа, когда мы хотим найти ровно одну запись.
Второй тип запросов — это диапазонные значения, когда мы хотим найти значения
ключей, находящихся в определенном, специфицированном нами диапазоне.
Следующий вид запросов — это ранговые запросы,
когда нам требуется в результате получить достаточно большую выборку.
Другой вид запросов, который потребует полного сканирования таблицы,
это запросы с использованием функций агрегирования.
Например, подсчет общего количества записей или суммы по какому-то полю
таблицы.
Мы видим, что запросы к данным могут быть разными.
Поэтому нам могут понадобиться разные структуры, которые позволяют выполнить эти
запросы наиболее эффективным способом.
Михайлова Еленадоцент, ИО заведующего кафедрой информационно-аналитических систем СПбГУ
