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