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

Материал из Викиконспекты
Перейти к: навигация, поиск
Эта статья находится в разработке!

Структура

Типы памяти
Тип Характеристика Величина
Оперативная память Объём 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