Версия 14:59, 20 декабря 2021

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

Содержание

1 Структура
2 Организация данных
3 Литература

Структура

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

@@ Строка 51: / Строка 51: @@
 СУБД могут хранить данные в оперативной памяти, на SSD, на жёстком диске.
-Многие СУБД для хранения данных всё ещё оптимизируют под особенности жёсткие дисков.
+Многие СУБД для хранения данных всё ещё оптимизируют под особенности жёсткие дисков. Хотим сократить общее количество обращений к диску и по возможности сделать их последовательными.
 === Особенности жёстких дисков ===
 * Большое время поиска
@@ Строка 60: / Строка 60: @@
 ** Сделать их последовательными
-== Страницы памяти ==
+== Страничная организация памяти ==
-* Память разбита на равные страницы
+Все современные СУБД умеют использовать.
-** Прямое отображение в память
-** Загрузка и выгрузка всей страницы
-** Для IA32 и AMD64 обычно 4КБ, 2МБ или 4МБ
-* Обработка быстрее чем чтение
-* Последовательности страниц
-** Данные одного типа
-** Частые переходы к следующей/предыдущей странице
-** Желательно хранить последовательно
-[[Файл:dbms-data-access.png|470px|thumb|right|Доступ к данным]]
+=== Память разбита на равные страницы ===
+* Прямое отображение в память
+* Загрузка и выгрузка всей страницы
+* Для IA32 и AMD64 обычно 4КБ (для маленьких страниц), 2МБ или 4МБ (для больших страниц)
-=== Модули системы хранения ===
+=== Обработка быстрее чем чтение ===
-* Диспетчер диска
+Обработка в оперативной памяти обычно быстрее, чем чтение. Позволяет заниматься промежуточным сжатием данных и т.д. (чтобы уменьшить объём хранимый на диске)
-** Каталог страниц
-** Оптимизация последовательностей страниц
+=== Последовательности страниц ===
-* Диспетчер страниц
+* Хранят данные одного типа. Обычно данный одной таблицы или индекса, для которых типичны к следующей/предыдущей странице.
-** Доступ к страницам
+* Частые переходы к следующей/предыдущей странице
-** Распределение памяти
+* Желательно хранить последовательно
-** Выгрузка данных
-* Диспетчер записей
+== Модули системы хранения ==
-** Доступ к записям
+[[Файл:dbms-data-access.png|450px|thumb|right|Схема доступа к данным]]
+=== Диспетчер диска ===
+* Каталог страниц
+* Оптимизация последовательностей страниц
+=== Диспетчер страниц ===
+* Доступ к страницам
+* Распределение памяти
+* Выгрузка данных
+=== Диспетчер записей ===
+* Доступ к записям
 = Организация данных =
-* Файл – одна или несколько таблиц
+* Файл – одна или несколько таблиц (чаще всего)
 * Таблица – несколько страниц
 * Страница – несколько записей
-* Какие проблемы?
-** Записи длиннее страницы
+=== Какие проблемы? ===
+Записи длиннее страницы. Не все СУБД это позволяют (записи длиннее страницы не поддерживаются (исключение - колонки BLOB, CLOB, которые могут храниться отдельно))
 == Список страниц ==
-[[Файл:dbms-page-list.png|470px|thumb|right|Список страниц]]
+[[Файл:dbms-page-list.png|470px|thumb|right|Схема списка страниц]]
+Типичным представлением является список страниц, который нужен диспетчеру памяти для организации их последовательного упорядочивания и предвыборки, если мы заранее знаем, что сканируем все страницы целиком.
 * Диспетчер диска – последовательности
 * Диспетчер памяти – предвыборка
-=== Идентификатор записи ===
+=== Идентификатор записи (RID) ===
-* Id записи (RID)
+У нас есть идентификатор не только страницы, но и отдельных записей на странице для того, чтобы по идентификатору записи можно было легко было определить страницу на которой он лежит, он состоит из
-** Id страницы
+* Id страницы
-** Id записи на странице
+* Id записи внутри страницы
-* Используется во многих местах
-** Не должен меняться
+Не должен меняться со временем, поскольку используется одновременно во многих местах для ссылки на эту запись, иначе нам придётся хранить в памяти и на диске отображение из старых номеров в новые и каждый раз проверять не изменился ли Id (не дешево) или нужно будет найти все места, где идентификатор записи использовался и все поменять.
-[[Файл:dbms-records-on-page.png|470px|thumb|right|Записи на странице]]
-[[Файл:dbms-overflow-page.png|470px|thumb|right|Страницы переполнения]]
+=== Хранение данных на странице ===
+В конце страницы помещается каталог записей, который по укороченному идентификатору записи позволяет определить, где соответствующая запись начинается.
+[[Файл:dbms-records-on-page.png|470px|none|Схема хранения данных на странице]]
+Когда записи не помещаются, создаём страницу переполнения и переносим на неё примерно половину записей, что даст пространство для роста на соответствующей странице.
+[[Файл:dbms-overflow-page.png|470px|none|Схема страницы переполнения]]
+==== Как избежать цепочек ====
+Чтобы не возникало связного списка страниц переполнения, запишем в исходную страницу указатель на место, где находится конкретная запись (исходную страницу всегда знаем, поскольку идентификатор записи - это в первую очередь идентификатор страницы).
 == Сжатие данных ==

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