[МУЗЫКА]

[МУЗЫКА] Здравствуйте!

Сегодня мы поговорим с вами о физическом хранении таблиц.

SQL является декларативным языком, и когда мы определяли структуры таблиц,

то мы не обращали внимания на то, каким образом данные будут храниться на диске.

И, в принципе, пользователь может этого не знать.

Но для того, чтобы правильно писать запросы и строить дополнительные

структуры, которые позволят выполнить ваши запросы оптимальным способом,

нам нужно все-таки немножко заглянуть внутрь и посмотреть,

как же хранятся данные непосредственно на диске.

Существует два принципиальных подхода к хранению таблиц.

Первый подход — это построчное хранение, второй подход — колоночное хранение.

Наибольшее распространение получил первый подход.

На нем мы сегодня остановимся.

Основной единицей хранения данных на диске являются страницы,

и мы стараемся располагать строки таблицы так,

чтобы каждая строка целиком размещалась в одной странице.

Страница — это очень небольшое количество данных,

поэтому они объединяются в более крупные единицы, называемые экстентами.

Как оценить скорость доступа к данным?

Обычно операции, которые производятся в оперативной памяти, выполняются быстро,

потому что скорость доступа к оперативной памяти намного больше, чем доступ к диску.

Поэтому оценивать мы будем при помощи подсчета операций с дисковой памятью:

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

Первый способ организации таблицы — это хранение файлов,

так называемое «файлы в виде кучи» или хранение таблицы с добавлением в конец.

В таком случае мы не организуем никакого порядка в наших записях,

и записи добавляются в конец файла по мере поступления.

Конечно, записи могут удаляться, и тогда в середине файлов впоследствии образуются

пустые места, которые мы можем заполнять вновь поступившими записями,

а можем так и оставлять эти места свободными.

Попробуем оценить поиск в таблице с добавлением в конец.

У нас нет другого способа для организации поиска,

кроме как полного сканирования таблицы.

Так называется просмотр всех блоков, начиная с первого,

пока мы не найдем нужную запись.

В среднем, наша запись может обнаружиться в среднем блоке, потому что

она с равной вероятностью обнаруживается как в первом, так и в последнем.

Поэтому среднее количество блоков, которое нам придется посмотреть, это N / 2.

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

отсортированными по какому-то значению ключа.

В таком случае у нас, конечно, сложнее будут происходить операции вставки

и изменений, потому что нам нужно будет поддерживать порядок записи внутри файла.

Зато мы выиграем при такой организации в поиске,

потому что наш поиск сократится до двоичного логарифма от количества блоков,

используемых для хранения записи в таблице.

Представьте, что вы ищете какое-то слово в словаре.

Вы знаете, что словарь у вас отсортирован по возрастанию слов.

Все слова в словаре отсортированы в алфавитном порядке.

Вы можете открыть словарь на середине, определить половинку,

в которой вы ищете слово, эту половинку разделить на 2 и так далее.

Это объясняет вам такую оценку поиска, которая выражается двоичным логарифмом.

Конечно, организация файлов в отсортированном порядке по значению

какого-то ключа дает нам преимущество в поиске,

но двоичный логарифм от количества блоков — это все-таки еще очень большое число.

Поэтому нам могут понадобится какие-то дополнительные структуры,

которые позволят нам производить поиск быстрее.

Для того чтобы нам строить дополнительные структуры,

нам нужно определиться с типами запросов, которые мы хотим выполнять.

Среди типов запросов можно выделить: первое — это поиск на точное

значение ключа, когда мы хотим найти ровно одну запись.

Второй тип запросов — это диапазонные значения, когда мы хотим найти значения

ключей, находящихся в определенном, специфицированном нами диапазоне.

Следующий вид запросов — это ранговые запросы,

когда нам требуется в результате получить достаточно большую выборку.

Другой вид запросов, который потребует полного сканирования таблицы,

это запросы с использованием функций агрегирования.

Например, подсчет общего количества записей или суммы по какому-то полю

таблицы.

Мы видим, что запросы к данным могут быть разными.

Поэтому нам могут понадобиться разные структуры, которые позволяют выполнить эти

запросы наиболее эффективным способом.

Индексирование данных.

Базы данных (Databases)

Rencontrer les enseignants