Подсистема хранения данных

Эта статья находится в разработке!

Структура

Типы памяти

Тип	Характеристика	Величина
Оперативная память	Объём	16 - 256 ГБ
	Цена	~5 $/ГБ
	Быстродействие	~10+ ГБ/с
	Время доступа	1-10 μ/с
SSD	Объём	0.5 - 8 ТБ
	Цена	~0.1 $/ГБ
	Быстродействие	0.500-6 ГБ/с
	Время доступа	0.1-0.2 мс
Жёсткие диски	Объём	4 - 12 ТБ
	Цена	~0.03 $/ГБ
	Быстродействие	10-200 МБ/с
	Время доступа	5-100 мс

СУБД могут хранить данные в оперативной памяти, на SSD, на жёстком диске.

Многие СУБД для хранения данных всё ещё оптимизируют под особенности жёсткие дисков. Хотим сократить общее количество обращений к диску и по возможности сделать их последовательными.

Особенности жёстких дисков

• Большое время поиска
• Скорость чтения
  • Последовательный доступ – средняя
  • Случайный доступ – низкая
• Сократить число обращений
  • Сделать их последовательными

Страничная организация памяти

Все современные СУБД умеют использовать.

Память разбита на равные страницы

• Прямое отображение в память
• Загрузка и выгрузка всей страницы
• Для IA32 и AMD64 обычно 4КБ (для маленьких страниц), 2МБ или 4МБ (для больших страниц)

Обработка быстрее чем чтение

Обработка в оперативной памяти обычно быстрее, чем чтение. Позволяет заниматься промежуточным сжатием данных и т.д. (чтобы уменьшить объём хранимый на диске)

Последовательности страниц

• Хранят данные одного типа. Обычно данный одной таблицы или индекса, для которых типичны к следующей/предыдущей странице.
• Частые переходы к следующей/предыдущей странице
• Желательно хранить последовательно

Модули системы хранения

Схема доступа к данным

Диспетчер диска

• Каталог страниц
• Оптимизация последовательностей страниц

Диспетчер страниц

• Доступ к страницам
• Распределение памяти
• Выгрузка данных

Диспетчер записей

• Доступ к записям

Организация данных

• Файл – одна или несколько таблиц (чаще всего)
• Таблица – несколько страниц
• Страница – несколько записей

Какие проблемы?

Записи длиннее страницы. Не все СУБД это позволяют (записи длиннее страницы не поддерживаются (исключение - колонки BLOB, CLOB, которые могут храниться отдельно))

Список страниц

Схема списка страниц

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

• Диспетчер диска – последовательности
• Диспетчер памяти – предвыборка

Идентификатор записи (RID)

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

• Id страницы
• Id записи внутри страницы

Не должен меняться со временем, поскольку используется одновременно во многих местах для ссылки на эту запись, иначе нам придётся хранить в памяти и на диске отображение из старых номеров в новые и каждый раз проверять не изменился ли Id (не дешево) или нужно будет найти все места, где идентификатор записи использовался и все поменять.

Хранение данных на странице

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

Когда записи не помещаются, создаём страницу переполнения и переносим на неё примерно половину записей, что даст пространство для роста на соответствующей странице.

Как избежать цепочек

Чтобы не возникало связного списка страниц переполнения, запишем в исходную страницу указатель на место, где находится конкретная запись (исходную страницу всегда знаем, поскольку идентификатор записи - это в первую очередь идентификатор страницы).

Сжатие данных

Тратим больше процессорного времени, в надежде потратить меньше времени для ввода/вывода (чаще всего окупается).

• Больше вычислений
• Меньше ввода-вывода
• Часто – быстрее

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

Пример

• Сжатие по полям
• Инкрементальное сжатие
• Префиксное сжатие

Литература

• Дейт К. Введение в системы баз данных (Приложение Г)
• Кнут Д. Искусство программирования. Том 3. Сортировка и поиск
• Silberschatz A., Korth H. F., Sudarshan S. Database System Concepts