классифицировать файлы что это

File Classification Infrastructure в Windows Server 2012

Одним из краеугольных элементов технологии обеспечения идентификации и безопасности — Dynamic Access Control (динамического контроля доступа) в Windows Server 2012, является функционал File Classification Infrastructure (FCI — Инфраструктуры классификации файлов). FCI используется на файловых серверах организации и предоставляет возможность создавать новые свойства и атрибуты(File-classification properties) для классификации по ним файлов. FCI позволяет в автоматически режиме классифицировать файлы в соответствии с содержимым файла или каталогом, в котором они находится; осуществлять управление файлами (например, срок в течении которого возможен доступ к файлу); генерировать отчеты, показывающих распределение классификационных свойств на файловых сервере. Файлы на основании ключевых слов или паттернов могут в автоматическом режиме классифицироваться, например, как конфиденциальные или содержащее персональные данные. Однако пользователь (владелец) без использования FCI может и вручную классифицировать файлы.

FCI – это элемент Dynamic Access Control, который классифицирует файлы, присваивая им теги, от которых зависит применение политик DAC.

Впервые технология File Classification Infrastructure появилась в Windows Server 2008 R2. Какие же возможности она предоставляла? С помощью FCI возможно реализовать различные сценарии обработки документов в файловых хранилищах (в т.ч. содержащих конфиденциальную информацию): сбор, шифрование, перенос, архивирование, отправку по маршруту и удаление файлов. С помощью FCI можно, например, реализовать сценарий, позволяющий основываясь на классификации файлов, автоматического перемещения файлы из дорогих хранилищ в более дешевые и медленные, или например, автоматически делать файлы недоступными по истечению определенного времени.

Как классифицировать файл или каталог вручную

Файлы и каталоги можно классифицировать вручную, открыв окно свойств объекта и выбрав вкладку «Classification». В нашем примере из выпадающего списка предопределенных значений можно выбрать другие значения для атрибутов country и Department.

Автоматическая классификация

Для настройки автоматической классификации объектов в Windows Server 2012 необходимо с помочью консоли Server Manager установить роль File Server (файлового сервера).

Установив компонент File Server Resource Manager (FSRM), откройте соответствующую MMC консоль и среди знакомых групп Quota, File Screening, File Management вы увидите новый подраздел Classification Management (управление классификацией), состоящий в свою очередь из двух подразделов:

Чтобы настроить автоматическую классификацию документов, нужно создать правило классификации.

Одним из способов организации автоматической классификации файлов на основании местоположения – свойство классификации – FolderUsage. Это предопределённое свойство, хранящееся в разделе Classification Properties. По-умолчанию, в нем определены 4 типа данных:

Здесь же можно создать собственные типы данных.

Создадим здесь собственные типы папок для финансового (Financial) и инженерного отдела (Engineering).Затем необходимо определить какие файлы к какому отделу (типу данных) отнести. Для этого щелкните по пустому месту консоли FSRM в разделе ClassificationProperties и выберите пункт SetFolderManagementProperties

Выберите свойство FolderUsage и укажите папки, которые будут использоваться каждым департаментом, или содержащие определенный тип данных. Однако следует понимать, что в данном случае настраивается не классификация файлов (мы будем настраивать ее позже), мы определим принадлежность папок, которую задействуем в классифицирующем правиле

Создадим правило классификации данных

Пришло время в разделе ClassificationRules создать новое правило (контекстное меню Create Classification Rule):

Укажите имя правило (мы создаем правило классификации файлов как принадлежащих финансовому департаменту).

На вкладке Scope указываем каталоги, которые необходимо учитывать при проведении классификации, выберем созданное ранее правило FinancialData (автоматически добавляет все выбранные ранее папки), можно также добавить каталоги вручную (в примере это E:\share1).

На вкладке Classification можно выбрать один из двух методов классификации:

На скриншоте указано правило классификации на основании каталогов, правило классификации по содержимому будет рассмотрено ниже.

На вкладке Evaluation Type указывается порядок применения и повторного применения правил классификации к файлам. В примере ниже мы указали, что система может перезаписывать текущую классификацию, тем самым мы гарантируем, что пользовательская классификация будет переопределена корпоративным правилом.

В следующем правили классификации мы создадим правило классификации на основе содержимого файла:

В данном правиле осуществляется классификация данных по стране, поэтому мы добавим в него каталоги и инженерного и финансового департамента.

В данном правиле классификации на основе содержимого файла, мы попробуем классифицировать данные, относящиеся к стране Egypt.

В разделе Parameters выберите Configure. В появившемся окне можно реализовать поиск на основании регулярных выражений, строки или регистрозависимой строки.

С помощью регулярных выражений можно осуществлять поиск в текстовых документах (в том числе файла tiff) по различным критериям, например:

В нашем примере, мы осуществим поиск документов по ключевому слову Egypt, и в случае его обнаружения файл должен классифицироваться этим правилом (можно указать минимально и максимально необходимое количество вхождений ключевого слова в документ).

Итак, мы создали два правила классификации:

Попробуем теперь запустить автоматическую классификацию файлов. Пусть у нас имеется 2 файла, один из которых содержит слово Egypt, а второй – нет. Эти файлы помещены в Каталоги “Financial Files” и “R&D files”, как вы видите на данный момент они никак не классифицированы.

Запустим наши классифицирующие правила (Run Classification With All Rules):

С результатом работы правил можно познакомится в отчетах в отчетах.

Как вы видите, все отработало правильно, файлам с ключевым словом присвоена правильная страна, а всему содержимому каталога финансового отдела атрибут Finance.

На данном этапе никаких операций с классифицируемыми файлами выполнено не было, они были просто отмечены нужными нам атрибутами. В дальнейшем на основании классификации файлов с ними можно выполнить различные операции, в частности зашифровать файлы с помощью AD RMS (пример использования описан в статье Шифрование файлов с помощью AD RMS на базе инфраструктуры классификация файлов Windows Server 2012), или управлять доступом к ним посредством Windows Server 2012 Dynamic Access Control. Эти аспекты мы рассмотрим в следующих статьях серии.

Источник

Типы файловых систем, их предназначение и отличия

Рядовому пользователю компьютерных электронных устройств редко, но приходится сталкиваться с таким понятием, как «выбор файловой системы». Чаще всего это происходит при необходимости форматирования внешних накопителей (флешек, microSD), установке операционных систем, восстановлении данных на проблемных носителях, в том числе жестких дисках. Пользователям Windows предлагается выбрать тип файловой системы, FAT32 или NTFS, и способ форматирования (быстрое/глубокое). Дополнительно можно установить размер кластера. При использовании ОС Linux и macOS названия файловых систем могут отличаться.

Возникает логичный вопрос: что такое файловая система и в чем ее предназначение? В данной статье дадим ответы на основные вопросы касательно наиболее распространенных ФС.

Что такое файловая система

Обычно вся информация записывается, хранится и обрабатывается на различных цифровых носителях в виде файлов. Далее, в зависимости от типа файла, кодируется в виде знакомых расширений – *exe, *doc, *pdf и т.д., происходит их открытие и обработка в соответствующем программном обеспечении. Мало кто задумывается, каким образом происходит хранение и обработка цифрового массива в целом на соответствующем носителе.

Операционная система воспринимает физический диск хранения информации как набор кластеров размером 512 байт и больше. Драйверы файловой системы организуют кластеры в файлы и каталоги, которые также являются файлами, содержащими список других файлов в этом каталоге. Эти же драйверы отслеживают, какие из кластеров в настоящее время используются, какие свободны, какие помечены как неисправные.

Запись файлов большого объема приводит к необходимости фрагментации, когда файлы не сохраняются как целые единицы, а делятся на фрагменты. Каждый фрагмент записывается в отдельные кластеры, состоящие из ячеек (размер ячейки составляет один байт). Информация о всех фрагментах, как части одного файла, хранится в файловой системе.

Файловая система связывает носитель информации (хранилище) с прикладным программным обеспечением, организуя доступ к конкретным файлам при помощи функционала взаимодействия программ A PI. Программа, при обращении к файлу, располагает данными только о его имени, размере и атрибутах. Всю остальную информацию, касающуюся типа носителя, на котором записан файл, и структуры хранения данных, она получает от драйвера файловой системы.

На физическом уровне драйверы ФС оптимизируют запись и считывание отдельных частей файлов для ускоренной обработки запросов, фрагментации и «склеивания» хранящейся в ячейках информации. Данный алгоритм получил распространение в большинстве популярных файловых систем на концептуальном уровне в виде иерархической структуры представления метаданных (B-trees). Технология снижает количество самых длительных дисковых операций – позиционирования головок при чтении произвольных блоков. Это позволяет не только ускорить обработку запросов, но и продлить срок службы HDD. В случае с твердотельными накопителями, где принцип записи, хранения и считывания информации отличается от применяемого в жестких дисках, ситуация с выбором оптимальной файловой системы имеет свои нюансы.

Основные функции файловых систем

Файловая система отвечает за оптимальное логическое распределение информационных данных на конкретном физическом носителе. Драйвер ФС организует взаимодействие между хранилищем, операционной системой и прикладным программным обеспечением. Правильный выбор файловой системы для конкретных пользовательских задач влияет на скорость обработки данных, принципы распределения и другие функциональные возможности, необходимые для стабильной работы любых компьютерных систем. Иными словами, это совокупность условий и правил, определяющих способ организации файлов на носителях информации.

Основными функциями файловой системы являются:

Задачи файловой системы

Функционал файловой системы нацелен на решение следующих задач:

В многопользовательских системах реализуется задача защиты файлов от несанкционированного доступа, обеспечение совместной работы. При открытии файла одним из пользователей для других этот же файл временно будет доступен в режиме «только чтение».

Вся информация о файлах хранится в особых областях раздела (томах). Структура справочников зависит от типа файловой системы. Справочник файлов позволяет ассоциировать числовые идентификаторы уникальных файлов и дополнительную информацию о них с непосредственным содержимым файла, хранящимся в другой области раздела.

Операционные системы и типы файловых систем

Существует три основных вида операционных систем, используемых для управления любыми информационными устройствами: Windows компании Microsoft, macOS разработки Apple и операционные системы с открытым исходным кодом на базе Linux. Все они, для взаимодействия с физическими носителями, используют различные типы файловых систем, многие из которых дружат только со «своей» операционкой. В большинстве случаев они являются предустановленными, рядовые пользователи редко создают новые дисковые разделы и еще реже задумываются об их настройках.

В случае с Windows все выглядит достаточно просто: NTFS на всех дисковых разделах и FAT32 (или NTFS) на флешках. Если установлен NAS (сервер для хранения данных на файловом уровне), и в нем используется какая-то другая файловая система, то практически никто не обращает на это внимания. К нему просто подключаются по сети и качают файлы.

На мобильных гаджетах с ОС Android чаще всего установлена ФС версии ext4 во внутренней памяти и FAT32 на карточках microSD. Владельцы продукции Apple зачастую вообще не имеют представления, какая файловая система используется на их устройствах – HFS+, HFSX, APFS, WTFS или другая. Для них существуют лишь красивые значки папок и файлов в графическом интерфейсе.

Более богатый выбор у линуксоидов. Но здесь настройка и использование определенного типа файловой системы требует хотя бы минимальных навыков программирования. Тем более, мало кто задумывается, можно ли использовать в определенной ОС «неродную» файловую систему. И зачем вообще это нужно.

Рассмотрим более подробно виды файловых систем в зависимости от их предпочтительного использования с определенной операционной системой.

Файловые системы Windows

Исходный код файловой системы, получившей название FAT, был разработан по личной договоренности владельца Microsoft Билла Гейтса с первым наемным сотрудником компании Марком Макдональдом в 1977 году. Основной задачей FAT была работа с данными в операционной системе Microsoft 8080/Z80 на базе платформы MDOS/MIDAS. Файловая система FAT претерпела несколько модификаций – FAT12, FAT16 и, наконец, FAT32, которая используется сейчас в большинстве внешних накопителей. Основным отличием каждой версии является преодоление ограниченного объема доступной для хранения информации. В дальнейшем были разработаны еще две более совершенные системы обработки и хранения данных – NTFS и ReFS.

FAT (таблица распределения файлов)

Числа в FAT12, FAT16 и FAT32 обозначают количество бит, используемых для перечисления блока файловой системы. FAT32 является фактическим стандартом и устанавливается на большинстве видов сменных носителей по умолчанию. Одной из особенностей этой версии ФС является возможность применения не только на современных моделях компьютеров, но и в устаревших устройствах и консолях, снабженных разъемом USB.

Пространство FAT32 логически разделено на три сопредельные области:

К недостатком стандарта FAT32 относится ограничение размера файлов на диске до 4 Гб и всего раздела в пределах 8 Тб. По этой причине данная файловая система чаще всего используется в USB-накопителях и других внешних носителях информации. Для установки последней версии ОС Microsoft Windows 10 на внутреннем носителе потребуется более продвинутая файловая система.

С целью устранения ограничений, присущих FAT32, корпорация Microsoft разработала обновленную версию файловой системы exFAT (расширенная таблица размещения файлов). Новая ФС очень схожа со своим предшественником, но позволяет пользователям хранить файлы намного большего размера, чем четыре гигабайта. В exFAT значительно снижено число перезаписей секторов, ответственных за непосредственное хранение информации. Функция очень важна для твердотельных накопителей ввиду необратимого изнашивания ячеек после определенного количества операций записи. Продукт exFAT совместим с операционными системами Mac, Android и Windows. Для Linux понадобится вспомогательное программное обеспечение.

NTFS (файловая система новой технологии)

Стандарт NTFS разработан с целью устранения недостатков, присущих более ранним версиям ФС. Впервые он был реализован в Windows NT в 1995 году, и в настоящее время является основной файловой системой для Windows. Система NTFS расширила допустимый предел размера файлов до шестнадцати гигабайт, поддерживает разделы диска до 16 Эб (эксабайт, 10 18 байт ). Использование системы шифрования Encryption File System (метод «прозрачного шифрования») осуществляет разграничение доступа к данным для различных пользователей, предотвращает несанкционированный доступ к содержимому файла. Файловая система позволяет использовать расширенные имена файлов, включая поддержку многоязычности в стандарте юникода UTF, в том числе в формате кириллицы. Встроенное приложение проверки жесткого диска или внешнего накопителя на ошибки файловой системы chkdsk повышает надежность работы харда, но отрицательно влияет на производительность.

ReFS (Resilient File System)

Все это позволяет повысить надежность хранения файлов, обеспечивает быстрое и легкое восстановление данных.

Файловые системы macOS

Для операционной системы macOS компания Apple использует собственные разработки файловых систем:

Файловые системы Linux

В отличие от ОС Windows и macOS, ограничивающих выбор файловой системы предустановленными вариантами, Linux предоставляет возможность использования нескольких ФС, каждая из которых оптимизирована для решения определенных задач. Файловые системы в Linux используются не только для работы с файлами на диске, но и для хранения данных в оперативной памяти или доступа к конфигурации ядра во время работы системы. Все они включены в ядро и могут использоваться в качестве корневой файловой системы.

Основные файловые системы, используемые в дистрибутивах Linux:

Ext2, Ext3, Ext4 или Extended Filesystem – стандартная файловая система, первоначально разработанная еще для Minix. Содержит максимальное количество функций и является наиболее стабильной в связи с редкими изменениями кодовой базы. Начиная с ext3 в системе используется функция журналирования. Сегодня версия ext4 присутствует во всех дистрибутивах Linux.

JFS или Journaled File System разработана в IBM в качестве альтернативы для файловых систем ext. Сейчас она используется там, где необходима высокая стабильность и минимальное потребление ресурсов (в первую очередь в многопроцессорных компьютерах). В журнале хранятся только метаданные, что позволяет восстанавливать старые версии файлов после сбоев.

ReiserFS также разработана в качестве альтернативы ext3, поддерживает только Linux. Динамический размер блока позволяет упаковывать несколько небольших файлов в один блок, что предотвращает фрагментацию и улучшает работу с небольшими файлами. Недостатком является риск потери данных при отключении энергии.

XFS рассчитана на файлы большого размера, поддерживает диски до 2 терабайт. Преимуществом системы является высокая скорость работы с большими файлами, отложенное выделение места, увеличение разделов на лету, незначительный размер служебной информации. К недостаткам относится невозможность уменьшения размера, сложность восстановления данных и риск потери файлов при аварийном отключении питания.

Btrfs или B-Tree File System легко администрируется, обладает высокой отказоустойчивостью и производительностью. Используется как файловая система по умолчанию в OpenSUSE и SUSE Linux.

Другие ФС, такие как NTFS, FAT, HFS, могут использоваться в Linux, но корневая файловая система на них не устанавливается, поскольку они для этого не предназначены.

Дополнительные файловые системы

В операционных системах семейства Unix BSD (созданы на базе Linux) и Sun Solaris чаще всего используются различные версии ФС UFS (Unix File System), известной также под названием FFS (Fast File System). В современных компьютерных технологиях данные файловые системы могут быть заменены на альтернативные: ZFS для Solaris, JFS и ее производные для Unix.

Кластерные файловые системы включают поддержку распределенных хранилищ, расширяемость и модульность. К ним относятся:

Практический пример использования файловых систем

Владельцы мобильных гаджетов для хранения большого объема информации используют дополнительные твердотельные накопители microSD (HC), по умолчанию отформатированные в стандарте FAT32. Это является основным препятствием для установки на них приложений и переноса данных из внутренней памяти. Чтобы решить эту проблему, необходимо создать на карточке раздел с ext3 или ext4. На него можно перенести все файловые атрибуты (включая владельца и права доступа), чтобы любое приложение могло работать так, словно запустилось из внутренней памяти.

Надеюсь, краткий обзор основных ФС поможет решить практические задачи в части правильного выбора и настройки ваших компьютерных устройств в повседневной практике.

Источник

Тема 11. Физические модели баз данных

Оглавление

Цель: изучить принципы организации физических моделей организации данных, используемых в системах баз данных.

Задачи:

11.1. Классификация файлов и файловых структур, используемых в БД

Физические модели баз данных определяют способы размещения данных в среде хранения и способы доступа к этим данным, которые поддерживаются на физическом уровне. Исторически первыми системами хранения и доступа были файловые структуры и системы управления файлами (СУФ), которые фактически являлись частью операционных систем. СУБД создавала над этими файловыми моделями свою надстройку, которая позволяла организовать всю совокупность файлов таким образом, чтобы она работала как единое целое и получала централизованное управление от СУБД. Однако непосредственный доступ осуществлялся на уровне файловых команд, которые СУБД использовала при манипулировании всеми файлами, составляющими хранимые данные одной или нескольких баз данных.

Однако механизмы буферизации и управления файловыми структурами не приспособлены для решения задач собственно СУБД, эти механизмы разрабатывались просто для традиционной обработки файлов, и с ростом объемов хранимых данных они стали неэффективными для использования СУБД. Тогда постепенно произошел переход от базовых файловых структур к непосредственному управлению размещением данных на внешних носителях самой СУБД. И пространство внешней памяти уже выходило из-под владения системы управления файлами (СУФ) и управлялось непосредственно СУБД. При этом механизмы, применяемые в файловых системах, перешли во многом и в новые системы организации данных во внешней памяти, называемые чаще страничными системами хранения информации. Поэтому наш раздел, посвященный физическим моделям данных, мы начнем с обзора файлов и файловых структур, используемых для организации физических моделей, применяемых в базах данных, а в конце ознакомимся с механизмами организации данных во внешней памяти, использующими страничный принцип организации.

В каждой СУБД по-разному организованы хранение и доступ к данным, однако существуют некоторые файловые структуры, которые имеют общепринятые способы организации и широко применяются практически во всех СУБД.

В системах баз данных файлы и файловые структуры, которые используются для хранения информации во внешней памяти, можно классифицировать следующим образом (рис. 11.1). С точки зрения пользователя, файлом называется поименованная линейная последовательность записей, расположенных на внешних носителях.

Так как файл — это линейная последовательность записей, то всегда в файле можно определить текущую запись, предшествующую ей и следующую за ней. Всегда существует понятие первой и последней записи файла. В соответствии с методами управления доступом различают устройства внешней памяти с произвольной адресацией (магнитные и оптические диски) и устройства с последовательной адресацией (магнитофоны, стримеры).

На устройствах с произвольной адресацией теоретически возможна установка головок чтения-записи в произвольное место мгновенно. Практически существует время позиционирования головки, которое весьма мало по сравнению со временем считывания-записи.

В устройствах с последовательным доступом для получения доступа к некоторому элементу требуется «перемотать (пройти)» все предшествующие ему элементы информации.

Рис. 11.1. Классификация файлов, используемых в системах баз данных

Файлы с постоянной длиной записи, расположенные на устройствах прямого доступа (УПД), являются файлами прямого доступа.

В этих файлах физический адрес расположения нужной записи может быть вычислен по номеру записи (NZ).

Каждая файловая система СУФ поддерживает некоторую иерархическую файловую структуру, включающую чаще всего не ограниченное количество уровней иерархии в представлении внешней памяти.

Для каждого файла в системе хранится следующая информация:

Для файлов с постоянной длиной записи адрес размещения записи с номером K может быть вычислен по формуле

где ВА — базовый адрес, LZ — длина записи.

Как мы уже говорили ранее, если можно всегда определить адрес, на который необходимо позиционировать механизм считывания-записи, то устройства прямого доступа делают это практически мгновенно, поэтому для таких файлов чтение произвольной записи практически не зависит от ее номера. Файлы прямого доступа обеспечивают наиболее быстрый доступ к произвольным записям, и их использование считается наиболее перспективным в системах баз данных.

На устройствах последовательного доступа могут быть организованы файлы только последовательного доступа.

Файлы с переменной длиной записи всегда являются файлами последовательного доступа. Они могут быть организованы двумя способами:

Здесь LZN — длина N-й записи.

Несмотря на то, что файлы с прямым доступом обеспечивают наиболее быстрый способ доступа, мы не всегда можем хранить информацию в виде файлов прямого доступа, но главное, что доступ по номеру записи в базах данных семантически не выполним. Чаще всего в базах данных необходим поиск по первичному или возможному ключам, иногда необходима выборка по внешним ключам, но во всех этих случаях мы знаем значение ключа, но не знаем номера записи, который соответствует этому ключу.

При организации файлов прямого доступа в некоторых очень редких случаях возможно построение функции, которая по значению ключа однозначно вычисляет адрес (номер записи файла):

где NZ — номер записи, K — значение ключа, F( ) — функция.

Функция F() при этом должна быть монотонной, чтобы обеспечивать однозначное соответствие.

11.2. Методы хеширования для организации доступа к файлам

Далеко не всегда удается построить взаимнооднозначное соответствие между значениями ключа и номерами записей.

Часто бывает, что значения ключей разбросаны по нескольким диапазонам (рис. 11.2).

Рис. 11.2. Неравномерное распределение ключей

В этом случае не удается построить взаимнооднозначную функцию, либо эта функция будет иметь множество незадействованных значений, которые соответствуют недопустимым значениям ключа. В подобных случаях применяют различные методы хэширования (рандомизации) и создают специальные хэш-функции.

Суть методов хэширования состоит в том, что мы берем значения ключа (или некоторые его характеристики) и используем его для начала поиска, т. е. мы вычисляем некоторую хэш-функцию h(k) и полученное значение берем в качестве адреса начала поиска. Мы не требуем полного взаимнооднозначного соответствия, но для повышения скорости мы ограничиваем время этого поиска (количество дополнительных шагов) для окончательного получения адреса. Таким образом, мы допускаем, что нескольким разным ключам может соответствовать одно значение хэш-функции (т. е. один адрес). Подобные ситуации называются коллизиями. Значения ключей, которые имеют одно и то же значение хэш-функции, называются синонимами.

Поэтому при использовании хэширования как метода доступа необходимо принять два независимых решения:

Существует множество различных стратегий разрешения коллизий, но мы для примера рассмотрим две достаточно распространенные.

11.2.1. Стратегия разрешения коллизий с областью переполнения

Первая стратегия условно может быть названа стратегией с областью переполнения.

При выборе этой стратегии область хранения разбивается на 2 части:

Для каждой новой записи вычисляется значение хэш-функции, которое определяет адрес ее расположения, и запись заносится в основную область в соответствии с полученным значением хэш-функции.

Если вновь заносимая запись имеет такое же значение функции хэширования, которое использовала другая запись, уже имеющаяся в БД, то новая запись заносится в область переполнения на первое свободное место, а в записи-синониме, которая находится в основной области, делается ссылка на адрес вновь размещенной записи в области переполнения. Если же уже существует ссылка в записи-синониме, которая расположена в основной области, то новая запись получает дополнительную информацию в виде ссылки и уже в таком виде заносится в область переполнения.

При этом цепочка синонимов не разрывается, но мы не просматриваем ее до конца, чтобы расположить новую запись в конце цепочки синонимов, а располагаем всегда новую запись на второе место в цепочке синонимов, что существенно сокращает время размещения новой записи. При таком алгоритме время размещения любой новой записи составляет не более двух обращений к диску с учетом того, что номер первой свободной записи в области переполнения хранится в виде системной переменной.

Рассмотрим теперь механизмы поиска произвольной записи и удаления записи для этой стратегии хэширования.

При поиске записи сначала вычисляется значение ее хэш-функции и считывается первая запись в цепочке синонимов, которая расположена в основной области. Если искомая запись не соответствует первой в цепочке синонимов, то далее поиск происходит перемещением по цепочке синонимов, пока не будет обнаружена требуемая запись. Скорость поиска зависит от длины цепочки синонимов, поэтому качество хэш-функции определяется максимальной длиной цепочки синонимов. Хорошим результатом может считаться наличие не более 10 синонимов в цепочке.

При удалении произвольной записи сначала определяется ее место расположения. Если удаляемой является первая запись в цепочке синонимов, то после удаления на ее место в основной области заносится вторая (следующая) запись в цепочке синонимов, при этом все указатели (ссылки на синонимы) сохраняются.

Если же удаляемая запись находится в середине цепочки синонимов, то необходимо провести корректировку указателей: в записи, предшествующей удаляемой, в цепочке ставится указатель из удаляемой записи. Если это последняя запись в цепочке, то механизм изменения указателей такой же, т. е. в предшествующую запись заносится признак отсутствия следующей записи в цепочке, который ранее хранился в последней записи.

11.2.2. Организация стратегии свободного замещения

При этой стратегии файловое пространство не разделяется на области, но для каждой записи добавляется 2 указателя: указатель на предыдущую запись в цепочке синонимов и указатель на следующую запись в цепочке синонимов. Отсутствие соответствующей ссылки обозначается специальным символом, например нулем или пробелом. Для каждой новой записи вычисляется значение хэш-функции, и если данный адрес свободен, то запись попадает на заданное место и становится первой в цепочке синонимов. Если адрес, соответствующий полученному значению хэш-функции, занят, то по наличию ссылок определяется, является ли запись, расположенная по указанному адресу, первой в цепочке синонимов. Если да, то новая запись располагается на первом свободном месте и для нее устанавливаются соответствующие ссылки: она становится второй в цепочке синонимов, на нее ссылается первая запись, а она ссылается на следующую, если таковая есть. Если запись, которая занимает требуемое место, не является первой записью в цепочке синонимов, значит, она занимает данное место «незаконно» и при появлении «законного владельца» должна быть «выселена», т. е. перемещена на новое место. Механизм перемещения аналогичен занесению новой записи, которая уже имеет синоним, занесенный в файл. После перемещения «незаконной» записи вновь вносимая запись занимает свое законное место и становится первой записью в новой цепочке синонимов.

Механизмы удаления записей во многом аналогичны механизмам удаления в стратегии с областью переполнения. Однако еще раз кратко опишем их. Если удаляемая запись является первой записью в цепочке синонимов, то после удаления на ее место перемещается следующая (вторая) запись из цепочки синонимов и проводится соответствующая корректировка указателя третьей записи в цепочке синонимов, если таковая существует. Если же удаляется запись, которая находится в середине цепочки синонимов, то производится только корректировка указателей: в предшествующей записи указатель на удаляемую запись заменяется указателем на следующую за удаляемой запись, а в записи, следующей за удаляемой, указатель на предыдущую запись заменяется на указатель на запись, предшествующую удаляемой.

11.3. Индексные файлы

Несмотря на высокую эффективность хэш-адресации, в файловых структурах далеко не всегда удается найти соответствующую функцию, поэтому при организации доступа по первичному ключу широко используются индексные файлы. В некоторых коммерческих системах индексными файлами называются также файлы, организованные в виде инвертированных списков, которые используются для доступа по вторичному ключу. Мы будем придерживаться классической интерпретации индексных файлов и надеемся, что если вы столкнетесь с иной интерпретацией, то сумеете разобраться в сути, несмотря на некоторую путаницу в терминологии.

Индексные файлы можно представить как файлы, состоящие из двух частей. Это не обязательно физическое совмещение этих двух частей в одном файле, в большинстве случаев индексная область образует отдельный индексный файл, а основная область образует файл, для которого создается индекс. Но нам удобнее рассматривать эти две части совместно, так как именно взаимодействие этих частей и определяет использование механизма индексации для ускорения доступа к записям.

Мы предполагаем, что сначала идет индексная область, которая занимает некоторое целое число блоков, а затем идет основная область, в которой последовательно расположены все записи файла.

В зависимости от организации индексной и основной областей различают 2 типа файлов: с плотным индексом и с неплотным индексом. Эти файлы имеют еще дополнительные названия, которые напрямую связаны c методами доступа к произвольной записи, которые поддерживаются данными файловыми структурами.

Файлы с плотным индексом называются также индексно-прямыми файлами, а файлы с неплотным индексом называются также индексно-последовательными файлами.

Рассмотрим файлы с плотным индексом. В этих файлах основная область содержит последовательность записей одинаковой длины, расположенных в произвольном порядке, а структура индексной записи в них имеет следующий вид (рис. 11.3):

Рис. 11.3. Структура плотного индекса

Здесь значение ключа — это значение первичного ключа, а номер записи — это порядковый номер записи в основной области, которая имеет данное значение первичного ключа. Так как индексные файлы строятся для первичных ключей, однозначно определяющих запись, то в них не может быть двух записей, имеющих одинаковые значения первичного ключа. В индексных файлах с плотным индексом для каждой записи в основной области существует одна запись из индексной области. Все записи в индексной области упорядочены по значению ключа, поэтому можно применить более эффективные способы поиска в упорядоченном пространстве.

Длина доступа к произвольной записи оценивается не в абсолютных значениях, а в количестве обращений к устройству внешней памяти, которым обычно является диск. Именно обращение к диску является наиболее длительной операцией по сравнению со всеми обработками в оперативной памяти.

Самым эффективным алгоритмом поиска на упорядоченном массиве является логарифмический, или бинарный, поиск. Очень хорошо изложил этот алгоритм барон Мюнхгаузен, когда объяснял, как поймать льва в пустыне. При этом все пространство поиска разбивается пополам, и так как оно строго упорядочено, то определяется сначала, не является ли элемент искомым, а если нет, то в какой половине его надо искать. Далее определенную половину также делим пополам и производим аналогичные сравнения и т. д., пока не обнаружим искомый элемент. Максимальное количество шагов поиска определяется двоичным логарифмом от общего числа элементов в искомом пространстве поиска:

где N — число элементов.

Однако в нашем случае является существенным только число обращений к диску. Поиск происходит в индексной области, где применяется двоичный алгоритм поиска индексной записи, а потом путем прямой адресации мы обращаемся к основной области уже по конкретному номеру записи. Для того чтобы оценить максимальное время доступа, нам надо определить количество обращений к диску для поиска произвольной записи. На диске записи файлов хранятся в блоках. Размер блока определяется физическими особенностями дискового контроллера и операционной системой. В одном блоке могут размещаться несколько записей. Значит нам надо определить количество индексных блоков, которое потребуется для размещения всех требуемых индексных записей, а потому максимальное число обращений к диску будет равно двоичному логарифму от заданного числа блоков плюс единица. После поиска номера записи в индексной области необходимо обратиться к основной области файла. Поэтому формула для вычисления максимального времени доступа в количестве обращений к диску выглядит следующим образом:

Рассмотрим конкретный пример и сравним время доступа при последовательном просмотре и при организации плотного индекса.

Имеем следующие исходные данные.

Длина записи файла (LZ) — 128 байт. Длина первичного ключа (LK) — 12 байт. Количество записей в файле (KZ) — 100 000. Размер блока (LB) — 1 024 байт.

Рассчитаем размер индексной записи. Для представления целого числа в пределах 100 000 потребуется 3 байта, можем считать, что у нас допустима только четная адресация, поэтому нам надо отвести 4 байта для хранения номера записи, тогда длина индексной записи будет равна сумме размера ключа и ссылки на номер записи, т. е.:

Определим количество индексных блоков, которое требуется для обеспечения ссылок на заданное количество записей. Для этого сначала определим, сколько индексных записей может храниться в одном блоке:

Теперь определим необходимое количество индексных блоков:

Округление осуществляется в большую сторону, потому что пространство выделяется целыми блоками, и последний блок у нас будет заполнен не полностью.

А теперь можно вычислить максимальное количество обращений к диску при поиске произвольной записи:

Логарифм тоже округляем, так как считаем количество обращений, а оно должно быть целым числом.

Следовательно, для поиска произвольной записи по первичному ключу при организации плотного индекса потребуется не более 12 обращений к диску. А теперь оценим, какой выигрыш получится, ведь организация индекса связана с дополнительными накладными расходами на его поддержку, поэтому такая организация может быть оправдана только в том случае, когда она действительно дает значительный выигрыш. Если бы мы не создавали индексное пространство, то при произвольном хранении записей в основной области в худшем случае необходимо просмотреть все блоки, в которых хранится файл. Временем просмотра записей внутри блока пренебрегаем, так как этот процесс происходит в оперативной памяти.

Количество блоков, которое необходимо для хранения всех 100 000 записей, определим по следующей формуле:

И это означает, что максимальное время доступа равно 12 500 обращений к диску. Да, действительно, выигрыш существенный.

Рассмотрим, как осуществляются операции добавления и удаления новых записей.

При операции добавления осуществляется запись в конец основной области. В индексной области необходимо произвести занесение информации в конкретное место, чтобы не нарушать упорядоченность. Поэтому вся индексная область файла разбивается на блоки и при начальном заполнении в каждом блоке остается свободная область, которая определяется заданным процентом расширения файла.

После определения блока, в который должен быть занесен индекс, этот блок копируется в оперативную память, там он модифицируется путем вставки в нужное место новой записи (в оперативной памяти это делается на несколько порядков быстрее, чем на диске) и, измененный, записывается обратно на диск. Определим максимальное количество обращений к диску, которое требуется при добавлении записи, — это количество обращений, необходимое для поиска записи плюс одно обращение для занесения измененного индексного блока и плюс одно обращение для занесения записи в основную область:

Естественно, в процессе добавления новых записей процент расширения постоянно уменьшается. Когда исчезает свободная область, возникает переполнение индексной области. В этом случае возможны два решения: либо перестроить заново индексную область, либо организовать область переполнения для индексной области, в которой будут храниться не поместившиеся в основную область записи. Однако первый способ потребует дополнительного времени на перестройку индексной области, а второй увеличит время на доступ к произвольной записи и потребует организации дополнительных ссылок в блоках на область переполнения. Именно поэтому при проектировании физической базы данных так важно заранее как можно точнее определить объемы хранимой информации, спрогнозировать ее рост и предусмотреть соответствующее расширение области хранения. При удалении записи необходимо осуществить следующие действия: запись в основной области помечается как удаленная (отсутствующая); в индексной области соответствующий индекс уничтожается физически, т. е. записи, следующие за удаленной записью, перемещаются на ее место, и блок, в котором хранился данный индекс, заново записывается на диск. При этом количество обращений к диску для этой операции такое же, как и при добавлении новой записи.

11.3.1. Файлы с неплотным индексом, или индексно-последовательные файлы

Попробуем усовершенствовать способ хранения файла: будем хранить его в упорядоченном виде и применим алгоритм двоичного поиска для доступа к произвольной записи. Тогда время доступа к произвольной записи будет существенно меньше. Для нашего примера это будет:

И это существенно меньше, чем 12 500 обращений при произвольном хранении записей файла. Однако и поддержание основного файла в упорядоченном виде — операция сложная.

Неплотный индекс строится именно для упорядоченных файлов. Для этих файлов используется принцип внутреннего упорядочения для уменьшения количества хранимых индексов. Структура записи индекса для таких файлов имеет следующий вид (рис. 11.4).

Рис. 11.4. Структура неплотного индекса

В индексной области мы теперь ищем нужный блок по заданному значению первичного ключа. Так как все записи упорядочены, то значение первой записи блока позволяет нам быстро определить, в каком блоке находится искомая запись. Все остальные действия происходят в основной области.

Время сортировки больших файлов весьма значительно, но поскольку файлы поддерживаются сортированными с момента их создания, накладные расходы в процессе добавления новой информации будут гораздо меньше. Оценим время доступа к произвольной записи для файлов с неплотным индексом. Алгоритм решения задачи аналогичен описанному ранее.

Сначала определим размер индексной записи. Если ранее ссылка рассчитывалась исходя из того, что требовалось ссылаться на 100 000 записей, то теперь нам требуется ссылаться всего на 12 500 блоков, поэтому для ссылки достаточно 2 байт. Тогда длина индексной записи будет равна:

Тогда количество индексных записей в одном блоке будет равно KIZB = LB/LI = 1 024/14 = 73 индексные записи в одном блоке. Определим количество индексных блоков, которое необходимо для хранения требуемых индексных записей:

Тогда время доступа по прежней формуле будет определяться так:

Мы видим, что при переходе к неплотному индексу время доступа уменьшилось практически в полтора раза. Поэтому можно признать, что организация неплотного индекса дает выигрыш в скорости доступа.

Рассмотрим процедуры добавления и удаления новой записи при подобном индексе.

Здесь механизм включения новой записи принципиально отличен от ранее рассмотренного. Новая запись должна заноситься сразу в требуемый блок на требуемое место, которое определяется заданным принципом упорядоченности на множестве значений первичного ключа. Поэтому сначала ищется требуемый блок основной памяти, в который надо поместить новую запись, а потом этот блок считывается, затем в оперативной памяти корректируется содержимое блока и он снова записывается на диск на старое место. Здесь, так же как и в первом случае, должен быть задан процент первоначального заполнения блоков, но только применительно к основной области. В MS SQL server этот процент называется Fill-factor и используется при формировании кластеризованных индексов. Кластеризованными называются индексы, в которых исходные записи физически упорядочены по значениям выбранного атрибута. При внесении новой записи индексная область не корректируется.

Количество обращений к диску при добавлении новой записи равно количеству обращений, необходимых для поиска соответствующего блока плюс одно обращение, которое требуется для занесения измененного блока на старое место:

Уничтожение записи происходит путем ее физического удаления из основной области, при этом индексная область обычно не корректируется, даже если удаляется первая запись блока. Поэтому количество обращений к диску при удалении записи такое же, как и при добавлении новой записи.

Организация индексов в виде B-tree (B-деревьев)

Калькированный термин «B-дерево», в котором смешивается английский символ «B» и добавочное слово на русском языке, настолько устоялся в литературе, посвященной организации физического хранения данных, что я не решусь его корректировать. Встретив как-то термин «Б-дерево», я долго его трактовала, потому что привыкла уже к устоявшемуся обозначению. Поэтому будем работать с этим термином.

Построение В-деревьев связано с простой идеей построения индекса над уже построенным индексом. Действительно, если мы построим неплотный индекс, то сама индексная область может рассматриваться как основной файл, над которым надо снова построить неплотный индекс, а потом снова над новым индексом строим следующий и так до того момента, пока не останется всего один индексный блок.

В общем случае получим некоторое дерево, каждый родительский блок которого связан с одинаковым количеством подчиненных блоков, число которых равно числу индексных записей, размещаемых в одном блоке. Количество обращений к диску при этом для поиска любой записи одинаково и равно количеству уровней в построенном дереве. Исключение составляет самый нижний уровень, где расположены записи основной области. Именно эти записи и являются «листьями» (конечными вершинами) данного дерева. Такие деревья называются сбалансированными (balanсed) именно потому, что путь от корня до любого листа в этом древе одинаков. Термин «сбалансированное» (от английского balanced — сбалансированный, взвешенный) и дал название данному методу организации индекса. Не путайте, пожалуйста, с двоичными деревьями, они также могут иметь сокращение B-tree (Binary Tree), но это совсем другая структура.

Построим подобное дерево для нашего примера и рассчитаем для него количество уровней и, соответственно, количество обращений к диску.

На первом уровне, как нам известно, число блоков равно числу блоков основной области — 12 500 блоков. Второй уровень образуется из неплотного индекса, мы его тоже уже строили и вычислили, что количество блоков индексной области в этом случае равно 172 блокам. А теперь над этим вторым уровнем снова построим неплотный индекс. Не будем менять длину индексной записи, а будем считать ее прежней, равной 14 байтам. Количество индексных записей в одном блоке нам тоже известно и равно 73. Поэтому сразу определим, сколько блоков нам необходимо для хранения ссылок на 172 блока:

Снова округляем в большую сторону, потому что последний, третий, блок будет заполнен не полностью.

И над третьим уровнем строим новый, и на нем будет всего один блок, в котором будет всего три записи. Поэтому число уровней в построенном дереве равно четырем, и соответственно количество обращений к диску для доступа к произвольной записи равно четырем. Это не максимально возможное число обращений, а всегда одно и то же, одинаковое для доступа к любой записи:

Механизм добавления и удаления записи при организации индекса в виде В-дерева аналогичен механизму, применяемому в случае с неплотным индексом. И наконец, последнее, что хотелось бы прояснить, — это наличие вторых названий для плотного и неплотного индексов. В случае плотного индекса после определения местонахождения искомой записи доступ к ней осуществляется прямым способом по номеру записи, поэтому этот способ организации индекса и называется индексно-прямым. В случае неплотного индекса после нахождения блока, в котором расположена искомая запись, поиск внутри блока требуемой записи происходит последовательным просмотром и сравнением всех записей блока. Поэтому способ индексации с неплотным индексом называется еще и индексно-последовательным.

11.4. Моделирование отношений «один ко многим» на файловых структурах

Отношение иерархии является типичным для баз данных, поэтому моделирование иерархических связей является типичным для физических моделей баз данных.

Для моделирования отношений 1:М (один ко многим) и М:М (многие ко многим) на файловых структурах используется принцип организации цепочек записей внутри файла и ссылки на номера записей для нескольких взаимосвязанных файлов.

Моделирование отношения 1:М с использованием однонаправленных указателей

В этом случае связываются два файла, например F1 и F2, причем предполагается, что одна запись в файле F1 может быть связана с несколькими записями в файле F2. При этом файл F1 в этом комплексе условно называется основным, а файл F2 — зависимым, или подчиненным. Структура основного файла может быть условно представлена в виде трех областей.

Основной файл F1

Ссылка-указатель на первую запись в подчиненном файле, с которой начинается цепочка записей файла F2, связанных с данной записью

В подчиненном файле также к каждой записи добавляется специальный указатель, в нем хранится номер записи, которая является следующей в цепочке записей подчиненного файла, связанной с одной записью основного файла. Таким образом, каждая запись подчиненного файла делится на две области: область указателя и область, содержащую собственно запись.

Структура записи подчиненного файла:

Указатель на следующую запись в цепочке

В качестве примера рассмотрим связь между преподавателями и занятиями, которые эти преподаватели проводят. В файле F1 приведен список преподавателей, а в файле F2 — список занятий, которые они ведут.

В этом случае содержимое двух взаимосвязанных файлов F1 и F2 может быть расшифровано следующим образом: первая запись в файле F1 связана с цепочкой записей файла F2, которая начинается с записи номер 1, следующая запись номер 4 и последняя запись в цепочке — запись номер 5. Последняя — потому, что пятая запись не имеет ссылки на следующую запись в цепочке. Аналогично можно расшифровать и остальные связи. Если мы проведем интерпретацию данных связей на уровне предметной области, то можно утверждать, что преподаватель Иванов ведет предмет «Вычислительные сети» в группе 4306, «Моделирование» в группе 84305 и «Вычислительные сети» в группе 4309.

Алгоритм нахождения нужных записей подчиненного файла

Использование цепочек записей позволяет эффективно организовывать модификацию взаимосвязанных файлов. Для того чтобы эффективно использовать дисковое пространство при включении новой записи в подчиненный файл, ищем первое свободное место, т. е. запись, помеченную символом «*», и на ее место заносим новую запись, после этого производим модификацию соответствующих указателей. Необходимо различать 3 случая:

1) добавление записи на первое место в цепочке;

2) добавление записи в конец цепочки;

3) добавление записи на заданное место в цепочке.

Однако часто бывает необходимо просматривать цепочку подчиненных записей в прямом и обратном направлениях. В этом случае применяют двойные указатели. В основном файле один указатель равен номеру первой записи в цепочке записей подчиненного файла, а второй — номеру последней записи. В подчиненном файле один указатель равен номеру следующей записи в цепочке, а другой — номеру предыдущей записи в цепочке. Для первой и последней записей в цепочке один из указателей пуст, т. е. равен пробелу.

Для нашего примера это выглядит следующим образом:

Один файл (подчиненный или основной) может быть связан с несколькими другими файлами, при этом для каждой связи моделируются свои указатели. Связь двух основных файлов F1 и F2 с одним связующим файлом F3 моделируется как показано на рис. 11.5.

Рис. 11.5. Взаимосвязь двух основных и одного связующего файлов

11.5. Инвертированные списки

До сих пор мы рассматривали структуры данных, которые использовались для ускорения доступа по первичному ключу. Однако достаточно часто в базах данных требуется проводить операции доступа по вторичным ключам. Напомним, что вторичным ключом является набор атрибутов, которому соответствует набор искомых записей. Это означает, что существует множество записей, имеющих одинаковые значения вторичного ключа. Например, в случае нашей БД «Библиотека» вторичным ключом может служить место издания, год издания. Множество книг могут быть изданы в одном месте, и множество книг могут быть изданы в один год.

Для обеспечения ускорения доступа по вторичным ключам используются структуры, называемые инвертированными списками, которые послужили основой организации индексных файлов для доступа по вторичным ключам. Инвертированный список в общем случае — это двухуровневая индексная структура. Здесь на первом уровне находится файл или часть файла, в которой упорядоченно расположены значения вторичных ключей. Каждая запись с вторичным ключом имеет ссылку на номер первого блока в цепочке блоков, содержащих номера записей с данным значением вторичного ключа. На втором уровне находится цепочка блоков, содержащих номера записей, содержащих одно и то же значение вторичного ключа. При этом блоки второго уровня упорядочены по значениям вторичного ключа. И, наконец, на третьем уровне находится собственно основной файл.

Механизм доступа к записям по вторичному ключу при подобной организации записей весьма прост. На первом шаге мы ищем в области первого уровня индексации заданное значение вторичного ключа, а затем по ссылке считываем блоки второго уровня, содержащие номера записей с заданным значением вторичного ключа, а далее уже прямым доступом загружаем в рабочую область пользователя содержимое всех записей, содержащих заданное значение вторичного ключа.

Для одного основного файла может быть создано несколько инвертированных списков по разным вторичным ключам.

Следует отметить, что организация вторичных списков действительно ускоряет поиск записей с заданным значением вторичного ключа. Но рассмотрим вопрос модификации основного файла. При модификации основного файла осуществляется следующие действия:

При этом следует отметить, что два последних шага выполняются для всех вторичных ключей, по которым созданы инвертированные списки. И, разумеется, такой процесс требует гораздо больше времени, чем просто изменение содержимого записи основного файла без поддержки всех инвертированных списков.

Таким образом, не следует безусловно утверждать, что введение индексных файлов (в том числе и инвертированных списков) всегда ускоряет обработку информации в базе данных. Отнюдь, если база данных постоянно изменяется и дополняется, модифицируется содержимое записей, то наличие большого количества инвертированных списков или индексных файлов по вторичным ключам может резко замедлить процесс обработки информации. Из сказанного можно заключить, что если база данных достаточно стабильна и ее содержимое практически не меняется, то построение вторичных индексов действительно может ускорить процесс обработки информации.

В SQL существует команда создания индексных файлов. При этом по умолчанию стандартно создаются индексные файлы для первичных ключей, для вторичных ключей индексные файлы создаются дополнительной командой CREATE INDEX, которая имеет следующий формат:

CREATE [UNIQUE] INDEX ON

— уникальный идентификатор в системе.

Здесь ASC — признак упорядочения по возрастанию, DESC — признак упорядочения по убыванию значений соответствующего столбца в индексе.

Индекс может быть удален командой DROP, которая имеет следующий формат:

11.6. Модели физической организации данных при страничной организации

Файловая структура и система управления файлами являются прерогативой операционной среды, поэтому принципы обмена данными подчиняются законам операционной системы. По отношению к базам данных эти принципы могут быть далеки от оптимальности. СУБД подчиняется несколько иным принципам и стратегиям управления внешней памятью, чем те, которые поддерживают операционные среды для большинства пользовательских процессов или задач.

Это и послужило причиной того, что СУБД взяли на себя непосредственное управление внешней памятью. При этом пространство внешней памяти предоставляется СУБД полностью для управления, а операционная среда не получает непосредственного доступа к этому пространству.

Физическая организация современных баз данных является наиболее закрытой, она определяется как коммерческая тайна для большинства поставщиков коммерческих СУБД. И здесь не существует никаких стандартов, поэтому в общем случае каждый поставщик создает свою уникальную структуру и пытается обосновать ее наилучшие качества по сравнению со своими конкурентами. Физическая организация является в настоящий момент наиболее динамичной частью СУБД. Стремительно расширяются возможность устройств внешней памяти, дешевеет оперативная память, увеличивается ее объем, и поэтому изменяются сами принципы организации физических структур данных. Можно предположить, что и в дальнейшем эта часть современных СУБД будет постоянно меняться.

11.6.1. Структуры хранения данных в SQL Server 2000

SQL Server 2000 организует следующую иерархию хранения.

На начальном этапе заполнения объект может занимать внутри экстента несколько страниц. Поэтому существуют два типа экстентов:

Когда объект создается, то обычно его первые страницы отводятся в смешанном блоке, по мере роста объекта он размещается в однородных блоках

В SQL 2000 существуют 6 основных типов страниц:

Кроме того, отдельно в MS SQL Server 2000 хранятся страницы журнала транзакций (Log page).

Все страницы имеют стандартный заголовок размером 96 байтов. В заголовке хранится общая информация, используемая ядром СУБД для работы со страницами. На странице, в отличие от экстента, хранится однородная информация, т. е. информация, принадлежащая одному объекту БД. Поэтому каждая страница имеет своего владельца, объект, данные которого хранятся на странице. Среди параметров страницы задаются:

Новыми в архитектуре дисковой памяти являются страницы размещения. В этих страницах хранятся сведения о размещении данных. SQL Server 2000 использует три типа страниц размещения: карты распределения блоков, карты свободного пространства, индексные карты размещения. SQL Server 2000 хранит информацию размещения на разных уровнях: на уровне блоков, на уровне страниц, на уровне объектов. Такой разносторонний мониторинг помогает СУБД оптимизировать работу в соответствии с требованиями конкретного запроса.

Карты распределения блоков

В данных картах хранится информация о распределении блоков. Карта распределения блоков состоит из стандартного заголовка и одного битового массива в 64 000 битов. Каждый бит характеризует один блок. Поэтому одна страница карты распределения описывает пространство в 64 000 блоков или 4 Гбайт данных.

Карты распределения блоков делятся на два типа:

При отведении пространства сервер использует обе карты распределения.

Значение полей GAM и SGAM — представлено в табл. 11.1.

При отведении пространства сервер использует обе карты распределения. Алгоритм распределения можно представить следующим образом.

Если нужен новый однородный экстент:

1) производится поиск бита со значением 1 в GAM;

2) отводится новый однородный экстент;

3) соответствующий бит в GAM устанавливается в 0.

Если нужен новый смешанный экстент:

4) производится поиск бита со значением 1 в GAM;

5) отводится новый однородный экстент;

6) соответствующий бит в GAM устанавливается в 0.

Если требуется новая страница в смешанном экстенте, достаточно найти экстент, для которого в SGAM установлена 1.

При заполнении смешанного экстента полностью связанный с ним бит обнуляется. При освобождении экстента устанавливаются в 1 соответствующий ему бит. Первые страницы файла БД всегда используются под карты распределения.

Карты размещения

Для организации связи между экстентами и расположенными на них объектами используются индексные карты размещения (Index Allocation Map, IAM). Каждая таблица или индекс имеют одну или более страниц IAM. В каждом файле, в котором размещаются таблица или индекс, существует как минимум одна карта размещения для этой таблицы или индекса. Страницы IAM размещаются произвольно внутри файла и отводятся по мере необходимости. Страницы IAM объединены друг с другом в цепочку двунаправленными ссылками. Указатель на первую карту размещения содержится в поле FirstIAM системной таблицы Sysindex.

Каждая страница IAM описывает диапазон экстентов размером 64 000 и представляет собой битовую карту: если бит установлен в 1, то в данном экстенте есть страницы, принадлежащие данному объекту, если в 0 — то нет. Если объект, которым является таблица или индекс, размещается в разных файлах, то в каждом файле для данного объекта существуют его страницы IAM, которые связаны в цепочку. Если в одном файле размещены несколько объектов, то для каждого объекта в этом файле организуются страницы IAM (рис. 11.6).

Рис. 11.6. Пример размещения в одном файле двух таблиц

При этом для каждой таблицы существует своя страница IAM, которая описывает наличие страниц, содержащих данные данного объекта в конкретном экстенте. В IAM 1 первый бит равен 1, второй 0, третий 1. В IAM 2 первый бит равен 0, второй 1, третий 0, четвертый 1.

Все страницы размещения не связаны напрямую некоторым объектом БД, они соответствуют некоторой системной информации, поэтому параметр «идентификатор объекта» для всех этих страниц одинаков и равен 99.

Карты свободного пространства

Степень заполнения страниц в MS SQL 2000 отслеживает специальный механизм — карты свободного пространства (Page free space page, PFS). Каждая PFS-страница хранит информацию о 8000 страниц, по 1 байту на страницу. Каждый байт представляет собой битовую карту, которая сообщает о степени занятости страницы и о том, принадлежит ли она объекту. Отслеживаются следующие диапазоны занятости страниц: 1 — 50 %, 51 — 80 %, 81 — 95 %, 96 — 100 %. При размещении данных MS SQL Server определяет, на какой странице достаточно места для размещения данных и, минимизируя обращения к внешней памяти, ищет страницу, на которой можно сразу разместить всю вновь введенную информацию.

Страницы данных

На самом общем уровне страница данных делится на 3 зоны: заголовок, область данных и таблицу смещений. В новой версии сервера страницы данных не связаны друг с другом в цепочки. За связь между страницами и объектами отвечает новая специальная структура — карты размещения. Кроме того, ранее данные на странице хранились непрерывно. При удалении строки данные внутри страницы перемещались так, чтобы не оставалось пустот. Однако такой подход затруднял строчные блокировки. И в новой версии данные на странице не обязательно хранятся непрерывно. Здесь допустимы пропуски. При удалении строки пустое пространство помечается и потом его может занять новая строка, но перемещения строк не происходит.

В SQL Sever 2000 разрешены блокировки на уровне строк, это означает, что одновременно несколько пользователей могут проводить операции модификации данных на одной странице. В этом случае при удалении строки ее место резервируется до окончания транзакции. В противном случае может произойти ситуация, что при откате транзакции нам некуда будет вернуть ранее удаленную строку.

В SQL Server 2000 теперь поддерживается классический термин «слот» (Slot), и это место размещения строки на странице. Если таблица не имеет кластеризованного индекса, то номер слота является идентификатором строки и не меняется, пока не будет удалена соответствующая строка. Если же таблица имеет кластеризованный индекс, то слоты располагаются в порядке, задаваемом индексом.

Строки данных

Строки данных претерпели существенное изменение. Отметим наиболее важные моменты.

Индексные страницы

Некластерные индексы хранятся отдельно от данных. Однако если на таблице построен кластерный индекс, то индексные записи некластерных индексов данной таблицы ссылаются на значение кластерного ключа. Если кластерный индекс построен не для уникального поля, то дополнительно вводится специальный унификатор, позволяющий однозначно идентифицировать строку. Именно на этот унификатор и ссылаются в этом случае все некластерные индексы.

Текстовые страницы

В версии 2000 изменены принципы хранения текстовых полей. Строки данных по-прежнему содержат 16-байтные указатели на текстовые данные. Однако хранение самих текстовых данных производится иначе.

Текстовая страница теперь может содержать несколько текстовых полей. Собственно данные хранятся в виде сбалансированного дерева (B-tree). Строка данных содержит указатель на корневую структуру (Root structure) размером 84 байта.

Данные длиной менее 64 байт хранятся в корневой структуре. Для данных до 32 Кбайт корневая структура (Root structure) может адресовать 4 блока данных (это не блоки страниц) до 8 Кбайт каждый. Блоки наращиваются до 8 Кбайт (реально на одной текстовой странице может быть размещено 8080 байт). Например, если первая порция данных составляет 4 Кбайта, то отводится один блок. Если в дальнейшем данные увеличиваются до 6 Кбайт, то первый блок увеличивается до 6 Кбайт, а второй блок имеет размер всего 2 Кбайта.

Если же длина текстового поля более 32 Кбайт, то строятся промежуточные узлы.

Структура файлов

Каждый файл базы данных имеет сходную структуру. В рамках БД каждый файл имеет уникальный порядковый номер. Внутри файла страницы нумеруются последовательно, начиная с 0, поэтому комбинация позволяет однозначно идентифицировать страницу внутри БД.

В начале файла располагаются страницы заголовка файла (страница 0). В странице заголовка файла хранятся атрибуты файла. Сразу же за нулевой страницей располагается страница PFS (страница 1), в ней хранится информация об использовании страниц в экстенте. Затем располагаются битовые страницы GAM и SGAM. Страницы IAM располагаются в произвольном месте файла. На каждые 8000 страниц данных создается своя страница PFS. Страницы GAM и SGAM создаются на каждые 64 000 экстентов или на каждые 512 000 страниц. Кроме того, каждая девятая страница первичного файла файла типа primary — это загрузочная страница БД (database boot page), содержащая описание БД и параметры конфигурации.

В общем случае сложные и большие базы данных в MS SQL Server 2000 могут располагаться в более чем двух файлах. Эти файлы объединяются в группы файлов. Все файлы внутри базы данных подразделяются на 3 типа Primary. Основной файл содержит системную информацию, системные таблицы, информацию об атрибутах всей БД. В общем случае в файле этого типа могут храниться и данные. По умолчанию этот файл имеет расширение. mdf. Такой файл на каждую базу данных может быть создан только один. Кроме того, может быть создано множество файлов типа Secondary. Это дополнительный тип файла. Он используется только для хранения данных. По умолчанию файлы данного типа имеют расширение. ndf. Третий тип файлов — это Transaction Log тип. Эти файлы предназначены для хранения журнала транзакций. Можно использовать несколько таких файлов для ускорения операций дискового ввода-вывода, в этом случае данные о транзакциях записываются параллельно в несколько файлов. По умолчанию файлам данного типа присваивается расширение. ldf.

В MS SQL Server 2000 предусмотрено автоматическое увеличение размера файлов. Файлы данных могут быть объединены в две группы файлов, первая из них называется Primary File Group, вторая User — define file Group. Одна из этих групп назначается группой по-умолчанию, и при внесении новых данных они равномерно размещаются в файлах группы по умолчанию, если не указано явным образом, в какой файл заносятся данные.

11.6.2. Архитектура разделяемой памяти

По причинам объективно существующей разницы в скорости работы процессоров, оперативной памяти и устройств внешней памяти (эта разница в скорости существовала, существует и будет существовать всегда) буферизация страниц базы данных в оперативной памяти — единственный реальный способ достижения удовлетворительной эффективности СУБД.

Операционные системы создают специальные системные буферы, которые служат для кэширования пользовательских процессов. Однако стратегия буферизации, применяемая в операционных средах, не соответствует целям и задачам СУБД, поэтому для оптимизации обработки данных одной из главных задач СУБД является создание эффективной системы управления процессом буферизации.

Разделяемая память, управляемая СУБД, состоит из нескольких типов буферов:

Информация в буферах взаимосвязана, и требуется эффективная система поддержки единой работы всех частей разделяемой памяти.

Если бы запись об изменении базы данных реально немедленно записывалась во внешнюю память, это привело бы к существенному замедлению работы системы. Поэтому записи в журнал тоже буферизуются: при нормальной работе очередная страница выталкивается во внешнюю память журнала только при полном заполнении записями.

Но реальная ситуация является более сложной. Имеются два вида буферов — буфер журнала и буфер страниц оперативной памяти, которые содержат связанную информацию. И те, и другие буферы могут выталкиваться во внешнюю память. Проблема состоит в выработке некоторой общей политики выталкивания, которая обеспечивала бы возможности восстановления состояния базы данных после сбоев.

Буфера не выделяются для каждого пользовательского процесса, они выделяются для всех процессов сервера БД. Это позволяет увеличить степень параллелизма при исполнении клиентских процессов.

Разделяемая память наиболее эффективно используется вспомогательными процессами сервера, иногда называемыми демонами, которые используются для синхронизации взаимодействующих процессов на сервере.

11.7. Проблемы создания информационных хранилищ и складов данных. Управление складами данных

11.7.1. Основные подходы к архитектуре хранилищ данных

Хранилища данных — это сравнительно новое технологическое решение, которое стало широко использоваться только в начале 90-х гг. ХХ в., после того, как Билл Инмон (Bill Inmon), ныне получивший всеобщее признание как «отец концепции хранилища данных», опубликовал свою первую книгу по этой теме (W.H. Inmon, Building the Data Warehouse, QED/Wiley, 1991). Хотя отдельные элементы этой концепции и их техническое воплощение существовали и ранее (по сути дела, с 70-х гг. прошлого века), только к концу 80-х гг. была в полной мере осознана необходимость интеграции корпоративной информации и надлежащего управления ею, а также появились технические возможности для создания соответствующих систем, первоначально названных хранилищами информации, а затем, с выходом книги Инмона, получивших свое нынешнее наименование «хранилища данных».

На сегодняшний день существует два основных подхода к архитектуре хранилищ данных. Это так называемая корпоративная информационная фабрика (Corporate Information Factory, сокр. CIF) Билла Инмона (рис. 1.7) и хранилище данных с архитектурой шины (Data Warehouse Bus, сокр. BUS) Ральфа Кимболла (Ralph Kimball) (рис. 11.8). Рассмотрим каждый из них подробнее.

Рис. 11.7. Архитектура корпоративной информационной фабрики

Работа хранилища, показанного на рис. 11.7, начинается со скоординированного извлечения данных из источников. После этого загружается реляционная база данных с третьей нормальной формой, содержащая атомарные данные. Получившееся нормализованное хранилище используется для того, чтобы наполнить информацией дополнительные репозитории презентационных данных, т. е. данных, подготовленных для анализа. Эти репозитории, в частности, включают специализированные хранилища для изучения и «добычи» данных (Data Mining), а также витрины данных. Отличительными особенностями подхода Билла Инмона к архитектуре хранилищ данных являются:

На рис. 11.8 приведена схема хранилища данных с архитектурой шины.

Рис. 11.8. Хранилище с архитектурой шины

В отличие от подхода Билла Инмона, пространственные модели строятся для обслуживания бизнес-процессов (которые, в свою очередь, связаны с бизнес-показателями или бизнес-событиями), а не бизнес-отделов. Например, данные о заказах, которые должны быть доступны для общекорпоративного использования, вносятся в пространственное хранилище данных только один раз, в отличие от CIF-подхода, в котором их пришлось бы трижды копировать в витрины данных отделов маркетинга, продаж и финансов. После того, как в хранилище появляется информация об основных бизнес-процессах, консолидированные пространственные модели могут выдавать их перекрестные характеристики. Матрица корпоративного хранилища данных с архитектурой шины выявляет и усиливает связи между показателями бизнес-процессов (фактами) и описательными атрибутами (измерениями).

Суммируя все вышесказанное, можно отметить типичные черты подхода Ральфа Кимболла.

Преимущества и недостатки каждого из подходов напрямую вытекают из их архитектурных решений. Считается, что пространственная организация с архитектурой «звезда» облегчает доступ к данным и требует меньше времени на выполнение запросов, а также упрощает работу с атомарными данными. С другой стороны, сторонники подхода Билла Инмона критикуют эту схему за отсутствие необходимой гибкости и уязвимость структуры, полагая, что в пространственно организованные атомарные данные труднее вносить необходимые изменения.

Реляционная схема организации атомарных данных замедляет доступ к данным и требует больше времени для выполнения запросов в силу разной организации атомарных и суммарных данных. Но с другой стороны, эта схема предоставляет широкие возможности для манипулирования атомарными данными и изменения их формата и способа представления по мере необходимости.

Основой аналитической обработки данных на базе хранилищ данных является технология OLAP (online analytical processing, аналитическая обработка в реальном времени) — технология обработки информации, включающая составление и динамическую публикацию отчетов и документов. Данная технология используется аналитиками для быстрой обработки сложных запросов к базе данных. Причина использования OLAP для обработки запросов — это скорость. Реляционные БД хранят сущности в отдельных таблицах, которые обычно хорошо нормализованы. Эта структура удобна для операционных (оперативных) БД (системы OLTP), но сложные многотабличные запросы в ней выполняются относительно медленно. Более хорошей моделью для запросов, а не для изменения, является пространственная БД

Вместе с базовой концепцией существуют три типа OLAP:

MOLAP — это классическая форма OLAP, так что ее часто называют просто OLAP. Она использует суммирующую БД, специальный вариант процессора пространственных БД и создает требуемую пространственную схему данных с сохранением как базовых данных, так и агрегатов. ROLAP работает напрямую с реляционным хранилищем, факты и таблицы с измерениями хранятся в реляционных таблицах, и для хранения агрегатов создаются дополнительные реляционные таблицы. HOLAP использует реляционные таблицы для хранения базовых данных и многомерные таблицы для агрегатов. Особым случаем ROLAP является ROLAP реального времени (Real-time ROLAP — R-ROLAP). В отличие от ROLAP в R-ROLAP для хранения агрегатов не создаются дополнительные реляционные таблицы, а агрегаты рассчитываются в момент запроса. При этом многомерный запрос к OLAP-системе автоматически преобразуется в SQL-запрос к реляционным данным.

Одной из проблем обработки больших объемов информации становится технология сжатия данных.

11.7.2. Основы фракталов. Фрактальная математика и фрактальные методы в архивации

Фракталы, эти красивые образы динамических систем, ранее использовались в машинной графике в основном для построения изображений неба, листьев, гор, травы. Красивое и, что важнее, достоверно имитирующее природный объект изображение могло быть задано всего несколькими коэффициентами. Неудивительно, что идея использовать фракталы при сжатии возникала и раньше, но считалось практически невозможным построить соответствующий алгоритм, который подбирал бы коэффициенты за приемлемое время. Итак, в 1991 г. такой алгоритм был найден. Фрактальный архиватор позволяет, например, при распаковке произвольно менять разрешение (размеры) изображения без появления эффекта зернистости. Более того, он распаковывает гораздо быстрее, чем ближайший конкурент JPEG, и не только статическую графику, но и видео.

Фактически фрактальная компрессия — это поиск самоподобных областей в изображении и определение для них параметров аффинных преобразований.

Для фрактального алгоритма компрессии, как и для других алгоритмов сжатия с потерями, очень важны механизмы, с помощью которых можно будет регулировать степень сжатия и степень потерь. К настоящему времени разработан достаточно большой набор таких методов. Во-первых, можно ограничить количество преобразований, заведомо обеспечив степень сжатия не ниже фиксированной величины. Во-вторых, можно потребовать, чтобы в ситуации, когда разница между обрабатываемым фрагментом и наилучшим его приближением выше определенного порогового значения, этот фрагмент дробился обязательно, и для него обязательно заводится технология преобразования. В-третьих, можно запретить дробить фрагменты размером меньше, допустим, четырех точек. Изменяя пороговые значения и приоритет этих условий, можно очень гибко управлять коэффициентом компрессии изображения: от побитного соответствия, до любой степени сжатия.

Источник

• ← даск мчс что это
• Брусчатка или тротуарная плитка в чем разница →