ta muallif kitobidan iqtiboslar  Распределенные данные. Алгоритмы работы современных систем хранения информации

Локальные запросы (поступающие непосредственно от клиентов или от других узлов) выполняются подсистемой хранения данных, которая включает в себя несколько компонентов с четко заданными функциями: Диспетчер транзакций
2 kishiga yoqdi
Fikr bildirish
Транзакция базы данных должна обладать свойствами атомарности, согласованности, изолированности и долговечности (atomicity, consistency, isolation, durability, ACID) [HAERDER83].
Fikr bildirish
Такие привязанные расширения страниц называются страницами переполнения. Для ясности в рамках этого раздела мы будем называть исходную страницу первичной страницей.
Fikr bildirish
Подведем итоги. Чтобы упростить структуру B-дерева, мы предполагаем, что каждый узел занимает одну страницу. Страница состоит из заголовка фиксированного размера, блока указателей на ячейки и ячеек. Ячейки содержат ключи и указатели на страницы, представляющие дочерние узлы или соответствующие записи данных. В B-деревьях используется простая иерархия указателей: идентификаторы страниц для поиска дочерних узлов в файле дерева и смещения ячеек для поиска ячеек внутри страницы.
Fikr bildirish
Для удаления элемента на странице не требуется удалять саму ячейку и смещать другие ячейки для заполнения освободившегося пространства. Вместо этого можно пометить ячейку как удаленную и обновить размещенный в памяти список доступности, указав объем освободившейся памяти и предоставив указатель на освобожденную область. В списке доступности хранятся смещения освобожденных сегментов и их размеры. Вставляя новую ячейку, мы сначала проверяем список доступности, чтобы определить, есть ли сегмент, в который она может поместиться. Пример фрагментированной страницы с доступными сегментами приведен на рис. 3.9.
Fikr bildirish
Для эффективного сохранения записей переменного размера, таких как строки, большие двоичные объекты и т.д., можно использовать такой способ организации, как слоттированная страница (т. е. страница со слотами, slotted page) [SILBERSCHATZ10] или каталог слотов[RAMAKRISHNAN03]. Этот подход используется во многих базах данных, например в PostgreSQL (https://databass.dev/links/61).
Fikr bildirish
СУБД хранят записи в файлах данных и индексных файлах. Эти файлы разбиты на секции фиксированного размера, называемые страницами, размер которых часто составляет несколько блоков файловой системы. Размер страниц обычно находится в диапазоне от 4 до 16 килобайт.
Fikr bildirish
Файл обычно начинается с заголовка фиксированного размера и может заканчиваться трейлером фиксированного размера, содержащим вспомогательную информацию, к которой необходимо обеспечить быстрый доступ или которая необходима для декодирования остальной части файла. Остальная часть файла разбита на страницы. Схема такой организации файлов показана на рис. 3.3.
Fikr bildirish
В системах баз данных обычно разделяются файлы данных и индексныефайлы
Fikr bildirish
Минимальная единица, которую можно записать (запрограммировать) или прочитать, — это страница. Однако мы можем вносить изменения только в пустые ячейки памяти (т. е. в те, которые были стерты до записи). Минимальный объект для стирания — это не страница, а блок, содержащий несколько страниц, поэтому его часто называют блоком стирания. Страницы в пустом блоке должны записываться последовательно.
Fikr bildirish