Подсистема хранения данных — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(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МБ
 
−
* Обработка быстрее чем чтение
 
−
* Последовательности страниц
 
−
** Данные одного типа
 
−
** Частые переходы к следующей/предыдущей странице
 
−
** Желательно хранить последовательно
 
  
−
== Литература ==
+
=== Память разбита на равные страницы ===
 +
* Прямое отображение в память
 +
* Загрузка и выгрузка всей страницы
 +
* Для 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
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Подсистема_хранения_данных&oldid=81791»