Понятие данных
 Скачать 1.56 Mb.
|
|
Удаление записей из B+ - дерева Если требуется удалить запись со значением ключа k, выполняется поиск листа L, содержащего запись с ключом k. Если такая запись существует, то она удаляется из L. Если это первая запись в L, то в узле - родителе Р, устанавливается новое значение первого ключа key1 из L. Но если L является первым сыном узла Р, то первый ключ из L не фиксируется в Р, а появляется в одном из предков Р. Таким образом, распространяется изменение значений ключей по наименьшему значению ключа из L в обратном направлении вдоль пути от L к корню. Если блок листа L после удаления записи оказывается пустым, он удаляется. После этого корректируются ключи и указатели в Р, чтобы отразить факт удаления листа L. Если количество сыновей узла Р оказывается теперь меньшим, чем m/2, проверяется узел Р1, расположенный в дереве на том же уровне слева (или справа) от Р. Если узел Р1 имеет по крайней мере m/2+1 сыновей, то ключи и указатели распределяются поровну между Р и Р1 так, чтобы оба эти узла имели по меньшей мере m/2 потомков. Затем необходимо изменить значения ключей в родителе Р и, если необходимо, распространить изменения на всех предков узла Р, на которых это изменение отразилось. Если же у Р1 имеется ровно m/2 - 1 ключей и m/2 сыновей, то нужно объединить Р и Р1 в один узел с 2m - 1 сыновьями на базе узла P. Затем необходимо удалить ключ и указатель на Р1 у родителя узла Р. В свою очередь у родителя узла P может остаться меньше m/2 сыновей и процесс удаления перейдет вверх по дереву. Этот восходящий процесс удаления может распространиться до самого корня и, возможно, придется объединить только двух сыновей корня. В этом случае новым корнем становится объединенный узел, а старый корень можно удалить. Высота В+ - дерева уменьшается на единицу. А) до удаления Б) после удаления 32. Методы доступа к данным в БД на основе хеш индексов. Идея хеширования. Методы разрешения коллизий. Хэш-индексы: являются таблицами с вычисляемым входом. Созданы для удобного доступа к данным с произвольным доступом. Хеш-функция отображает индекс в физический адрес хранения соотв. строки таблицы. Адрес, получаемый в результате, должен попасть в диапазон адресов, соответствующий выделенному пространству. Пространство под таблицу резервируется при создании таблицы, и в хэш-функции часто используется операция % (остаток от деления на размер таблицы). Хэш-функция должна давать достаточно однородные значения хэш-индексов, чтобы не было скопления синонимов (или коллизий), требующих специальных методов обработки. В реальности могут возникать ситуации, когда несколько элементов могут отображаться на одну ячейку, эти ситуации называются коллизиями (элементы, для которых возникает коллизия называются синонимами). Правила построения хэш-функции:1. первичный ключ обязательно входит в атрибуты, на которых строится хэш-индекс. 2. хэш-функция должна использовать значения всех атрибутов первичного ключа. Бакет представляет собой ячейку, с записями, в которой хранятся данные, для которых хэш-функция одинакова. Разрешение коллизий разбивается на 2 составляющие: выявление свободного пространства в бакете, если бакет занят, то обрабатываем переполнение бакета. Решение коллизий методом открытой адресации: в случае заполнения бакета мы, последовательно, идём по ячейкам до нахождения первой свободной ячейки, куда и записываем данные. Когда мы доходим до конца списка бакетов, поиск свободных ячеек продолжаем сначала. В случае, если мы дойдём до того места, откуда мы начали поиск, это означает что мы заняли всю таблицу. Поиск осуществляется также как и запись. Удаление: Т.к. при удалении элемента, находящегося не в своём бакете возможны проблемы с поиском других элементов, вводится специальная метка, которая означает что место свободно для записи, но будет учитываться как занятое при поиске. Метод доступа посредством хеширования Хешированием называется метод доступа, обеспечивающий прямую адресацию данных путем преобразования значения ключа в относительный или абсолютный физический адрес. Не требуется логическая упорядоченность значений ключей физических записей. Значениям нескольких ключей может соответствовать один и тот же физический адрес (блок). Может применяться как для хранения, так и для поиска записей. Эффективность доступа и хранения зависят от распределения ключей, алгоритма их преобразования и распределения памяти. Между методом прямого доступа и методом доступа посредством хеширования существует сходство. При методе доступа посредством хеширования адрес физической записи алгоритмически определяется из значения ключа записи. Алгоритм преобразования ключа называют также подпрограммой рандомизации. При использовании функции хеширования возможно преобразование двух или более ключей в один и тот же физический адрес, который называется собственным адресом. Записи, ключи которых отображаются в один и тот же физический адрес, называются синонимами, а случай преобразования нового ключа в уже заданный собственный адрес называется коллизией. Поскольку по адресу, определяемому функцией хеширования, может физически храниться только одна запись, синонимы должны храниться в каких-нибудь других ячейках памяти. При возникновении коллизий образуются цепочки синонимов, необходимых для обеспечения механизма поиска синонимов (рис. 1). Сущность метода хеширования заключается в том, что все адресное пространство делится на несколько областей фиксированного размера, которые называются бакетами. В качестве бакета может выступать цилиндр, дорожка, блок, страница, т.е. любой участок памяти, адресуемый в операционной среде как единое целое. Наименьшая составная единицей бакета называется фрагментом записи или секцией. Если при занесении нового значения индекса все бакеты заняты, то для него выделяется дополнительная область памяти, называемая областью переполнения. Главным ограничением этого метода является фиксированный размер таблицы. Если таблица заполнена слишком сильно или переполнена, то возникнет слишком много цепочек переполнения, и главное преимущество хеширования — доступ к записи почти всегда за одно обращение к таблице — будет утрачено. Расширение таблицы требует ее полной переделки на основе новой хэш-функции (со значением свертки большего размера). В случае баз данных такие действия являются абсолютно неприемлемыми. Поэтому обычно вводят промежуточные таблицы-справочники, содержащие значения ключей и адреса записей, а сами записи хранятся отдельно. Тогда при переполнении справочника требуется только его переделка, что вызывает меньше накладных расходов. Характеристики метода: 1. при хеш-файлах распределение ключевых значений оказывает значительное влияние на распределение собственных адресов и количество синонимов; 2. вид функции хеширования оказывает влияние на распределение собственных адресов и на количество синонимов; 3. упорядоченность данных при загрузке данных влияет на общую производительность системы; 4. объем адресного пространства или количество бакетов влияет на количество синонимов и коэффициент резервирования памяти; 5. большой размер бакета обеспечивает гибкость обработки коллизий без использования области переполнения; 6. метод обработки переполнения влияет на время обслуживания и зависит от метода хеширования ключа; 7. хеширование ключа обеспечивает эффективную выборку и обновление записей. Платой за эту эффективность является нарушение логической упорядоченности файла; 8. хеширование допускает возможность вторичного преобразования по специальному ключу. 33. Сравнительные характеристики хеш индексов и B+ дерева индексов. Смволический ключ (идентификатор) – совокупность атрибутов, на которых строится хэш-индекс; должен уникально идентифицировать каждую запись таблицы. Он преобразуется в физический адрес. Функция преобразования – это и есть хэш-функция. Хэш индексы • Для произвольного доступа к данным • Строится на уникальных атрибутах • Хэш функция отображает индекс в физический адрес хранения соответствующей строки таблицы • Принцип отображения – m : 1 Принцип отображения – т.е. m разных идентификаторов могут быть преобразованы в один и тот же хэш-индекс (или собственно адрес). Такие идентификаторы называются синонимами, а ситуация, в которой возникают синонимы, - коллизией. Бакет – некоторая область адресного пространства, фиксированного размера Идея хеширования: Для k1 ≠ k2 hash(k1) = hash(k2) k1, k2 – синонимы Разрешение коллизий: • выявление свободного пространства в бакете • обработка переполнения бакета Сравнение методов индексирования В+ деревья • представляются объектами базы данных • не влияют на представление таблицы • упорядоченное хранение строк таблицы • определены и операции < и > для сравнения ключей • пространство для таблицы выделяется по мере вставки строк • могут создаваться на ключевых и не ключевых атрибутах • используются всеми СУБД Хэш индексы • не представляются объектами базы данных • влияют на представление таблицы • упорядоченность строк отсутствует • определены только операции = и ≠ для сравнения ключей • пространство для таблицы выделяется при создании таблицы • должны создаваться только на ключевых атрибутах • используются не всеми СУБД Рекомендации Если размер таблицы сильно изменяется – не хэш таблица Если часто организуется поиск по критериям < > – не хэш таблица Если используются справочники (мало изменяемые таблицы, поиск в них по =) – хэш таблицы 34. Организация физических структур хранения в MS SQL Server: типы файлов, структура файлов базы данных. Типы и назначение страниц. Организация страницы данных. Файлы и файловые группы На физическом уровне база данных в Microsoft SQL Server 2008 представляется набором файлов операционной системы. Данные и сведения журналов транзакций всегда размещаются в разных файлах. Отдельные файлы используются только одной базой данных. Файловые группы представляют собой именованные коллекции файлов и используются для упрощения размещения данных и выполнения задач администрирования, например резервного копирования и восстановления. Базы данных SQL Server содержат файлы трех типов: • Первичные файлы данных. Первичный файл данных является отправной точкой базы данных. Он указывает на остальные файлы базы данных. В каждой базе данных имеется один первичный файл данных. Для имени первичного файла данных рекомендуется использовать расширение MDF. • Вторичные файлы данных. Ко вторичным файлам данных относятся все файлы данных, за исключением первичного файла данных. Базы данных могут вообще не содержать вторичных файлов данных, или содержать один или несколько вторичных файлов данных. Для имени вторичного файла данных рекомендуется использовать расширение NDF. • Файлы журналов. Файлы журналов содержат все сведения журналов, используемые для восстановления базы данных. В каждой базе данных должен быть по меньшей мере один файл журнала, но их может быть и больше. Для имен файлов журналов рекомендуется использовать расширение MDF, NDF и LDF. Однако эти расширения помогают пользователю идентифицировать различные виды файлов и правильно их использовать. В SQL Server расположение всех файлов базы данных записывается в первичный файл базы данных и в специальную служебную структуру СУБД SQL Server, называемою базой данных master. В большинстве случаев при работе с базой данных компонент СУБД (SQL Server Database Engine) использует сведения о размещении файлов, хранимые в базе данных master. Однако в некоторых случаях (например, при восстановлении базы данных master из копии, при определенным образом проводимым присоединении базы данных) компонент Database Engine использует сведения о расположении файлов из первичного файла, чтобы инициализировать записи о расположении файлов в базе данных master. Файлы SQL Server имеют два имени: • logical_file_name — имя, используемое для ссылки на физический файл во всех инструкциях Transact-SQL. Логическое имя файла должно соответствовать правилам для идентификаторов SQL Server и быть уникальным среди логических имен файлов в соответствующей базе данных. • os_file_name — это имя физического файла, включая путь к каталогу. Оно должно соответствовать правилам для имен файлов операционной системы. Изначально можно указать максимальный размер каждого файла. Если максимальный размер файла не указан, файлы SQL Server могут автоматически увеличиваться в размерах, превосходя первоначально заданные показатели, пока не займут все доступное место на диске. При определении файла пользователь может указывать требуемый шаг роста. Каждый раз при заполнении файла его размер увеличивается на указанный шаг роста. Если в файловой группе имеется несколько файлов, их автоматический рост начинается лишь по заполнении всех файлов. Затем файлы увеличиваются в размерах по кольцевому списку. Эта функция особенно полезна в случаях, когда SQL Server используется в качестве базы данных, внедренной в приложение, где пользователь не имеет удобного доступа к системному администратору. По мере необходимости пользователь может предоставить файлам возможность увеличиваться в размерах автоматически, тем самым снимая с администратора часть забот по наблюдению за свободным пространством базы данных и по распределению дополнительного пространства вручную. Страницы и экстенты Основной единицей хранилища данных и обмена информацией между внешней и оперативной памятью в SQL Server является страница. Место на диске, предоставляемое для размещения файла данных (MDF- или NDF-файл) в базе данных, логически разделяется на страницы с непрерывным перечислением от 0 до n. Дисковые операции ввода-вывода выполняются на уровне страницы. А именно, SQL Server считывает или записывает целые страницы данных. В SQL Server размер страницы составляет 8 КБ. Это значит, что в одном мегабайте базы данных SQL Server содержится 128 страниц. Каждая страница начинается с 96-байтового заголовка, который используется для хранения системных данных о странице. Эти данные включают номер страницы, тип страницы, объем свободного места на странице и идентификатор единицы распределения объекта, которому принадлежит страница. В файлах данных базы данных SQL Server используется 8 типов страниц (данные с типами данных небольших размеров, данные с типами данных больших размеров, записи индекса, сведения о размещении экстентов, сведения о размещении страниц и доступном на них свободном месте и т. д.). Для эффективного управления памятью страницы объединяются в экстенты, которые являются основными единицами организации пространства. Экстент — это коллекция, состоящая из восьми физически непрерывных страниц или 64 Кб; они используются для эффективного управления страницами. Все страницы хранятся в экстентах. Таким образом, в одном мегабайте базы данных SQL Server содержится 16 экстентов. Чтобы сделать распределение места эффективным, SQL Server не выделяет целые экстенты для таблиц с небольшим объемом данных. SQL Server имеет два типа экстентов: • Однородные экстенты принадлежат одному объекту (определенной таблице, индексу и т. д.); все восемь страниц могут быть использованы только этим владеющим объектом. • Смешанные экстенты могут находиться в общем пользовании у не более восьми объектов. Каждая из восьми страниц в экстенте может находиться во владении разных объектов. Новая таблица или индекс — это обычно страницы, выделенные из смешанных экстентов. При увеличении размера таблицы или индекса до восьми страниц эти таблица или индекс переходят на использование однородных экстентов для последовательных единиц распределения. При создании индекса для существующей таблицы, в которой содержится достаточно строк, чтобы сформировать восемь страниц в индексе, все единицы распределения для индекса находятся в однородных экстентах. Пример размещения объектов в смешанном и однородном экстентах приводится на рис. 10.2. Рис. 10.2. Размещение объектов в смешанном и однородном экстентах Страницы файлов данных Страницы файлов данных SQL Server нумеруются последовательно; первая страница файла получает нулевой номер (0). Каждый файл базы данных имеет уникальный цифровой идентификатор. Чтобы уникальным образом определить страницу базы данных, необходимо использовать как идентификатор файла, так и номер этой страницы. На рис. 10.3. показаны номера страниц базы данных, содержащей первичный файл данных объемом в 4 МБ и вторичный файл данных объемом в 1 МБ. Рис. 10.3. Пример нумерации страниц файлов базы данных 35. Архитектура таблиц и индексов. Кластерный и некластерный индексы, куча. Организация таблиц и индексов Таблицы и индексы хранятся в виде коллекции страниц размером 8 КБ. Страницы таблиц и индексов содержатся в одной или нескольких секциях. Секция — это пользовательская единица организации данных. По умолчанию таблица или индекс имеет единственную секцию, которая содержит все страницы таблицы или индекса. Секция располагается в одной файловой группе. Таблица или индекс, имеющие одну секцию, эквивалентны организационной структуре таблиц и индексов предыдущих версий SQL Server. Если таблица или индекс используют несколько секций, данные секционируются горизонтально, так что группы строк сопоставляются отдельным секциям, основываясь на указанном столбце. Секции могут храниться в одной или нескольких файловых группах в базе данных. Таблица или индекс рассматриваются как единая логическая сущность при выполнении над данными запросов или обновлений. Секция состоит из фрагментов одного или нескольких файлов. Данные внутри фрагмента файла представляются в виде кучи (строки данных хранятся без определенного порядка – последовательное размещение) или сбалансированного дерева. Фрагмент файла может иметь один из трех видов: данные с типами небольших размеров (данные IN_ROW_DATA), данные с типами больших размеров (LOB_DATA), данные переменной длины (переполнение строки ROW_OVERFLOW_DATA). В каждой секции кучи или индекса содержится по крайней мере одна единица распределения IN_ROW_DATA. Кроме того, в зависимости от схемы кучи или индекса, там могут содержаться единицы распределения LOB_DATA или ROW_OVERFLOW_DATA. Рис. 10.4. Физическая структура таблицы в базе данных SQL Server Каждая секция содержит строки данных либо в куче, либо в структуре кластеризованного индекса. |