Подсистема хранения данных — различия между версиями
(added structure) |
(up final) |
||
(не показаны 2 промежуточные версии этого же участника) | |||
Строка 1: | Строка 1: | ||
{{В разработке}} | {{В разработке}} | ||
− | + | = Структура = | |
{| class="wikitable" style="float:right; margin-left:0.8em; clear:right;" | {| class="wikitable" style="float:right; margin-left:0.8em; clear:right;" | ||
|+ Типы памяти | |+ Типы памяти | ||
Строка 51: | Строка 51: | ||
СУБД могут хранить данные в оперативной памяти, на SSD, на жёстком диске. | СУБД могут хранить данные в оперативной памяти, на SSD, на жёстком диске. | ||
− | Многие СУБД для хранения данных всё ещё оптимизируют под особенности жёсткие дисков. | + | Многие СУБД для хранения данных всё ещё оптимизируют под особенности жёсткие дисков. Хотим сократить общее количество обращений к диску и по возможности сделать их последовательными. |
=== Особенности жёстких дисков === | === Особенности жёстких дисков === | ||
* Большое время поиска | * Большое время поиска | ||
Строка 60: | Строка 60: | ||
** Сделать их последовательными | ** Сделать их последовательными | ||
− | == | + | == Страничная организация памяти == |
− | + | Все современные СУБД умеют использовать. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | == Литература | + | === Память разбита на равные страницы === |
+ | * Прямое отображение в память | ||
+ | * Загрузка и выгрузка всей страницы | ||
+ | * Для IA32 и AMD64 обычно 4КБ (для маленьких страниц), 2МБ или 4МБ (для больших страниц) | ||
+ | |||
+ | === Обработка быстрее чем чтение === | ||
+ | Обработка в оперативной памяти обычно быстрее, чем чтение. Позволяет заниматься промежуточным сжатием данных и т.д. (чтобы уменьшить объём хранимый на диске) | ||
+ | |||
+ | === Последовательности страниц === | ||
+ | * Хранят данные одного типа. Обычно данный одной таблицы или индекса, для которых типичны к следующей/предыдущей странице. | ||
+ | * Частые переходы к следующей/предыдущей странице | ||
+ | * Желательно хранить последовательно | ||
+ | |||
+ | == Модули системы хранения == | ||
+ | [[Файл:dbms-data-access.png|450px|thumb|right|Схема доступа к данным]] | ||
+ | === Диспетчер диска === | ||
+ | * Каталог страниц | ||
+ | * Оптимизация последовательностей страниц | ||
+ | === Диспетчер страниц === | ||
+ | * Доступ к страницам | ||
+ | * Распределение памяти | ||
+ | * Выгрузка данных | ||
+ | === Диспетчер записей === | ||
+ | * Доступ к записям | ||
+ | |||
+ | = Организация данных = | ||
+ | * Файл – одна или несколько таблиц (чаще всего) | ||
+ | * Таблица – несколько страниц | ||
+ | * Страница – несколько записей | ||
+ | |||
+ | === Какие проблемы? === | ||
+ | Записи длиннее страницы. Не все СУБД это позволяют (записи длиннее страницы не поддерживаются (исключение - колонки BLOB, CLOB, которые могут храниться отдельно)) | ||
+ | |||
+ | == Список страниц == | ||
+ | [[Файл:dbms-page-list.png|470px|thumb|right|Схема списка страниц]] | ||
+ | Типичным представлением является список страниц, который нужен диспетчеру памяти для организации их последовательного упорядочивания и предвыборки, если мы заранее знаем, что сканируем все страницы целиком. | ||
+ | |||
+ | * Диспетчер диска – последовательности | ||
+ | * Диспетчер памяти – предвыборка | ||
+ | |||
+ | === Идентификатор записи (RID) === | ||
+ | У нас есть идентификатор не только страницы, но и отдельных записей на странице для того, чтобы по идентификатору записи можно было легко было определить страницу на которой он лежит, он состоит из | ||
+ | * Id страницы | ||
+ | * Id записи внутри страницы | ||
+ | |||
+ | Не должен меняться со временем, поскольку используется одновременно во многих местах для ссылки на эту запись, иначе нам придётся хранить в памяти и на диске отображение из старых номеров в новые и каждый раз проверять не изменился ли Id (не дешево) или нужно будет найти все места, где идентификатор записи использовался и все поменять. | ||
+ | |||
+ | === Хранение данных на странице === | ||
+ | В конце страницы помещается каталог записей, который по укороченному идентификатору записи позволяет определить, где соответствующая запись начинается. | ||
+ | [[Файл:dbms-records-on-page.png|470px|none|Схема хранения данных на странице]] | ||
+ | |||
+ | Когда записи не помещаются, создаём страницу переполнения и переносим на неё примерно половину записей, что даст пространство для роста на соответствующей странице. | ||
+ | [[Файл:dbms-overflow-page.png|470px|none|Схема страницы переполнения]] | ||
+ | |||
+ | ==== Как избежать цепочек ==== | ||
+ | Чтобы не возникало связного списка страниц переполнения, запишем в исходную страницу указатель на место, где находится конкретная запись (исходную страницу всегда знаем, поскольку идентификатор записи - это в первую очередь идентификатор страницы). | ||
+ | |||
+ | == Сжатие данных == | ||
+ | Тратим больше процессорного времени, в надежде потратить меньше времени для ввода/вывода (чаще всего окупается). | ||
+ | * Больше вычислений | ||
+ | * Меньше ввода-вывода | ||
+ | * Часто – быстрее | ||
+ | |||
+ | Мы можем прибегать к использованию структур данных, поскольку мы храним связанные записи, в частности у них одинаковая структура и т.д. | ||
+ | |||
+ | === Пример === | ||
+ | * Сжатие по полям | ||
+ | * Инкрементальное сжатие | ||
+ | * Префиксное сжатие | ||
+ | |||
+ | = Литература = | ||
* ''Дейт К. Введение в системы баз данных (Приложение Г)'' | * ''Дейт К. Введение в системы баз данных (Приложение Г)'' | ||
* ''Кнут Д. Искусство программирования. Том 3. Сортировка и поиск'' | * ''Кнут Д. Искусство программирования. Том 3. Сортировка и поиск'' |
Версия 15:15, 20 декабря 2021
Содержание
Структура
Тип | Характеристика | Величина |
---|---|---|
Оперативная память | Объём | 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