Понятие данных
 Скачать 1.56 Mb.
|
|
Инвертированный (метод вторичного индексирования) Значения ключей физических записей необязательно находятся в логической последовательности. Метод применяется только для выборки данных. Индекс может быть построен для каждого инвертированного поля. Эффективность доступа зависит от числа записей БД, числа уровней индексации и распределения памяти для размещения индекса. Инвертированные списки формируются системой для поисковых атрибутов, причем для каждого возможного значения такого атрибута составляется список уникальных номеров записей, в которых это значение атрибутов присутствует. Записи с одним и тем же значением поля группируются, а общее для всей группы значение используется в качестве указателя этой группы. Тогда при поиске записей по значениям поисковых атрибутов системе достаточно отыскать списки, соответствующие требуемым значениям, и выбрать номер записи согласно заданной «схеме» пересечения или объединения условий на значениях поисковых атрибутов, а также отрицания некоторого условия. На рис. 2. приведен пример поиска записей инверсированным методом доступа. • Последовательный метод доступа: для получения целевой записи – обращение ко всем предшествующим цели записям • Произвольный метод доступа: для получения целевой записи – непосредственное обращение к ней 26. Бинарные деревья поиска, структура узла дерева. Многоходовое дерево. Бинарное дерево поиска на множестве NR ключей есть бинарное дерево TNR, в котором каждая вершина помечена отдельным ключом и расположена в соответствии с определенным порядком ключей. Для любой вершины i ключи вершин в его левом поддереве «меньше» ключа вершины i, который, в свою очередь, «меньше» ключей вершин в его правом поддереве. Упорядоченная тройка (TL, R, TR) R – корень дерева TL, TR – левое и правое поддеревья корня R; NL, NR – количество узлов в поддеревьях, NL≥ 0, NR≥ 0 Общее количество узлов в дереве NQ = NL + NR + 1 • Значение узла – ключ и некоторая запись RowId • Левый и правый указатели на поддеревья Длина поиска – длина пути от корня до целевой записи • 1. Уровень вершины или листа i, обозначаемый Li, определяется длиной пути от корневой вершины TNR до вершины i. Корневая вершина, по определению, имеет уровень 0. • 2. Высота дерева определяется как максимальный уровень среди всех вершин дерева. • 3. Бинарное дерево называется сбалансированным, если разница уровней любых двух листьев не превышает 1. Структура вершины В-дерева Обозначим записи, размещенные в одной вершине дерева, через R 1 , R 2 , …, R j , а указатели на подчиненные вершины через P 0 , P 1 , P 2 , …, P j . Тогда структура вершины будет следующей: P 0 R 1 P 1 R 2 P 2 … P j-1 R j P j Правила следования: 1. Ключи записей в текущей вершине упорядочены по возрастанию, т.е. ключ записи R 1 меньше ключа записи R 2 , который, в свою очередь, меньше ключа записи R 3 , и т.д. 2. Записи в подчиненной вершине, на которую указывает P 0 , имеют ключи, меньшие, чем ключ записи R 1 3. Записи в подчиненной вершине, на которую указывает P j , имеют ключи, большие, чем ключ записи R j 4. Записи в подчиненной вершине, на которую указывает P i (0 < i < j), имеют ключи, большие, чем ключ записи R i , и меньшие, чем ключ записи R i+1 Многоходовые деревья по структуре похожи на бинарные, за исключением того факта, что в одной вершине хранится больше одного ключа и оно имеет больше 2-х потомков. Для B дерева: в узле дерева степени n содержится минимум n- 1, максимум 2n-1 ключей и j+1 потомок, где j=количеству ключей в узле. Ключи в узле упорядочены по возрастанию. В остальном структура в таких деревьях аналогична обычным бинарным деревьям. Структура ключа на рисунке. Должно выполняться условие { K(Pi-1)} Структура узла B-дерева может выглядеть так: • Текущее количество ключей в узле • Значения ключей и сопутствующая ключам информация • Указатели на дочерние узлы (для листьев здесь NULL) • Указатель на родительский узел 27. Определение В дерева. Структура узла В дерева. Бинарное дерево поиска на множестве NR ключей есть бинарное дерево TNR, в котором каждая вершина помечена отдельным ключом и расположена в соответствии с определенным порядком ключей. Для любой вершины i ключи вершин в его левом поддереве «меньше» ключа вершины i, который, в свою очередь, «меньше» ключей вершин в его правом поддереве Упорядоченная тройка (TL, R, TR) R – корень дерева TL, TR – левое и правое поддеревья корня R; NL, NR – количество узлов в поддеревьях, NL≥ 0, NR≥ 0 Общее количество узлов в дереве NQ = NL + NR + 1 • Значение узла – ключ и некоторая запись RowId • Левый и правый указатели на поддеревья Длина поиска – длина пути от корня до целевой записи • 1. Уровень вершины или листа i, обозначаемый Li, определяется длиной пути от корневой вершины TNR до вершины i. Корневая вершина, по определению, имеет уровень 0. • 2. Высота дерева определяется как максимальный уровень среди всех вершин дерева. • 3. Бинарное дерево называется сбалансированным, если разница уровней любых двух листьев не превышает 1. Структура вершины В-дерева Обозначим записи, размещенные в одной вершине дерева, через R 1 , R 2 , …, R j , а указатели на подчиненные вершины через P 0 , P 1 , P 2 , …, P j . Тогда структура вершины будет следующей: P 0 R 1 P 1 R 2 P 2 … P j-1 R j P j Правила следования: 1. Ключи записей в текущей вершине упорядочены по возрастанию, т.е. ключ записи R 1 меньше ключа записи R 2 , который, в свою очередь, меньше ключа записи R 3 , и т.д. 2. Записи в подчиненной вершине, на которую указывает P 0 , имеют ключи, меньшие, чем ключ записи R 1 3. Записи в подчиненной вершине, на которую указывает P j , имеют ключи, большие, чем ключ записи R j 4. Записи в подчиненной вершине, на которую указывает P i (0 < i < j), имеют ключи, большие, чем ключ записи R i , и меньшие, чем ключ записи R i+1 Структура узла B-дерева может выглядеть так: • Текущее количество ключей в узле • Значения ключей и сопутствующая ключам информация • Указатели на дочерние узлы (для листьев здесь NULL) • Указатель на родительский узел 28. Правила вставки нового ключа в В дерево. Операции вставки предшествует поиск, который должен завершиться не успешно. Операция вставки позволяет включить новый элемент только в лист В-дерева. Поэтому, прежде всего, определяется целевая вершина – лист В-дерева, куда должен быть вставлен новый элемент, не нарушая упорядоченности записей. Когда целевая вершина (лист) В-дерева будет найдена, можно столкнуться со следующими ситуациями. 1. Простейший случай, когда найденный лист имеет свободные позиции (не заполнен полностью). В этом случае новый элемент вставляется в найденный лист, не нарушая упорядоченности ключей. Пусть, например, имеется следующий фрагмент В-дерева порядка 2. Необходимо вставить элемент с ключом 7. Новый элемент должен быть размещен в листе с номером 2, в котором есть свободные позиции. В результате выполнения операции вставки получим новое В-дерево. 2. Случай переполнения вершины: найденный целевой лист заполнен полностью. При вставке нового элемента в целевой лист получим последовательность из 2n+1 ключей, тогда как в листе могут находиться максимум 2n ключей. В этом случае выполняется операция расщепления листа: ключ из средней позиции переносится в родительскую вершину, а на уровне листьев появляются два новых листа. Рассмотрим пример. Пусть в представленное выше дерево порядка 2 вставляется элемент с ключом 37. Поэтому получим последовательность ключей: 7, 10, 15, 23, 37. В средней позиции находится элемент с ключом 15; он перемещается в родительскую вершину, и появляются два новых листа. Когда элемент перемещается в родительскую вершину, для нее также рассматриваются эти же две ситуации. Если родительская вершина заполнена полностью, для нее также выполняется операция расщепления с перемещением элемента на вышерасположенный уровень. В результате высота дерева может увеличиться на 1. Рассмотрим пример вставки нескольких значений в В-дерево порядка 1. Пусть вставляется следующая последовательность элементов: 20, 12, 48, 3, 5, 70, 101. 1. Первые два элемента заполняют первый лист, который является одновременно и корнем В-дерева. 2. Вставляется следующий элемент – 48. Получаем переполнение: 12, 20, 48. Элемент из средней позиции поднимается вверх и создает новую вершину – корень В-дерева, которой подчинены два листа 3. Элемент с ключом 3 вставляется в самый левый лист 4. Элемент с ключом 5 также должен быть вставлен в самый левый лист; получаем переполнение – 3, 5, 12, и элемент из средней позиции перемещается в родительскую вершину, в которой есть свободное место. 5. Следующий элемент (70) вставляется в самый правый лист, в котором есть свободная позиция. 6. В тот же лист должен быть вставлен следующий элемент с ключом 101; получаем переполнение – 48, 70, 101, и элемент из средней позиции перемещается в родительскую вершину. В родительской вершине также возникает переполнение – 5, 20, 70; в результате перемещения элемента из средней позиции образуется новая вершина – корень В-дерева , и высота дерева увеличивается на 1. 20 12 20 а) б) 12 48 20 3 12 48 20 3 12 5 20 48 3 5 12 а) переполнение листа б) расщепление листа 3 12 5 20 48 70 3 12 5 20 48 3 12 5 20 101 70 а) результат расщепления листа 48 101 70 б) результат расщепления промежуточной вершины Процесс вставок можно продолжать, включая в дерево новые элементы. Таким образом, при вставке элементов в дерево В-дерево растет вверх – появляется новый корень, хотя новый элемент вставляется в лист дерева. 47 101 7 10 15 23 50 53 110 129 а) переполнение листа 15 47 101 7 10 23 37 50 53 б) после расщепления листа 1 2 3 4 1 2 5 3 110 129 4 37 29. Правила удаления ключа из В дерева. При удалении возможны две ситуации: • Удаляемый элемент находится в листе; • Удаляемый элемент находится в промежуточном узле: тогда он заменяется следующим за ним (минимальный ключ из правого поддерева) или предшествующим ему (максимальный ключ из левого поддерева) элементом либо левое и правое поддеревья объединяются и их родителем становится ближайший левый от удаляемого ключа и ближайший правый от удаляемого ключа ключ. Нормальное удаление - когда в листе содержится более чем n элементов (n – степень дерева). Антипереполнение листа возникает тогда, когда в целевом листе находится только n ключей (минимально допустимое количество). Тогда нарушается свойство B-дерева и возможны два варианта решения: 1. Перераспределение ключей; 2. Слияние узлов. Перераспределение ключей. Удаление из листа. Метод возможно применить, если существует соседний лист (находящийся рядом с целевым и имеющий такого же родителя), который содержит больше n ключей (n – степень дерева, т.е. минимально возможное количество ключей), тогда выбираем ключ из этого соседа, который является разделителем между оставшимися ключами узла-соседа и исходного узла (то есть не больше всех из одной группы и не меньше всех из другой). Пусть это ключ k1. Выберем ключ k2 из узла-родителя, который является разделителем исходного узла и его соседа, который мы выбрали ранее. Удалим из исходного листа нужный ключ (который необходимо было удалить), спустим k2 в этот узел, а вместо k2 в узле-родителе поставим k1. Пример: фрагмент В-дерева степени 3; удаляется ключ 276 В соседнем листе больше n ключей. Значит, удаляем 276 из нужного листа, перемещаем ключ-родитель 253 в этот лист, а на место родителя помещаем максимальный элемент листа-соседа 211. Результат: Удаление из промежуточного узла. Метод возможно применить, если у хотя бы одного дочернего узла количество ключей больше n. Ситуация: удаляем ключ k из узла x. Если левый дочерний узел (содержащий ключи, предшествующие ключу k ) содержит больше n ключей, то находим k1 – максимальный элемент левого дочернего узла. Удаляем k. Заменяем место k в узле x на k1. Проделываем аналогичную работу, если правый дочерний узел (содержащий ключи, бОльшие ключа k ) имеет больше n ключей. Пример. Фрагмент В-дерева степени 3; удаляется ключ 253 из узла. Ключ 253 мы можем заменить лишь ключом из левого дочернего узла, так как правый содержит ровно n ключей, а левый n+2 ключа (5 ключей). Максимальный элемент левого дочернего узла 211. Удаляем ключ 253, и на его место ставим ключ 211. Результат: Слияние листьев. Удаление из листа. Метод применим, если все соседние листы имеют ровно n ключей. Тогда целевой лист (из которого удаляем) мы объединяем с каким-либо соседом, удаляем нужный ключ. И тот ключ из узла-родителя, который был разделителем для этих двух «бывших» соседей, переместим в новообразовавшийся лист (очевидно, он будет в нём медианой, то есть находиться между ключами одного листа и другого листа). Пример. Фрагмент В-дерева степени 2; удаляется ключ 15. Перераспределить ключи нельзя, так как в соседнем листе тоже минимально возможное количество ключей – 2. Удаляем ключ 15. Перемещаем из родителя ключ 32 в левое поддерево. Сливаем лист с соседним узлом. Получаем: Удаление из промежуточного узла. Метод возможно применить если у обоих дочерних узлов количество ключей равно n. Ситуация: удаляем ключ k из узла x. Если оба (левый и правый дочерние узлы) имеют по n ключей, то объединяем этих детей, удаляем ключ k. Пример. Фрагмент В-дерева степени 2; удаляется ключ 32. Оба поддерева содержат n ключей, перераспределить нельзя. Сливаем оба узла в один, удаляем ключ 32, а следующие за ключом 32 ключи смещаем влево. Результат: 30. Структуры типа В+ дерево. Структура узла В+ дерева. Правила вставки нового ключа в В+ дерево. Дерево - это иерархическая структура, состоящая из множества вершин (или элементов). Каждая вершина дерева относится к определенному уровню и обладает тем свойством, что, помимо внутренней информации, в ней также содержатся указатели на вершины более низкого уровня. Чтобы устранить недостатки, свойственные В-дереву при выполнении последовательной выборки данных, было введено В+ дерево. В+ дерево во многом аналогично В-дереву. Как и В-дерево, В+ дерево является сбалансированным. Для В+ дерева устанавливаются те же ограничения на количество ключей в каждой вершине дерева, зависящие от порядка дерева. Различие между В+ деревом от В-деревом заключается в следующем. В В-дереве все вершины дерева равноправны и содержат ключи и ассоциированные с ними данные. В В+ дереве выделяются два типа вершин: промежуточные вершины индексов и листья. Ключи и ассоциированные с ними данные размещаются только в листьях. Листья объединяются в связанное последовательное упорядоченное множество. Это позволяет эффективно выполнять последовательные запросы. Доступ к листьям осуществляется через промежуточные вершины В+ дерева, организованные в виде обычного В-дерева индексов. Два типа узлов В+ дерева: внутренние узлы–представляют собой В - дерево индексов; содержат только ключи • листья– объединены в двухсвязный список; содержат все ключи и ассоциированные с ними данные (RowID). Основные свойства: 1) Для любой вершины В+ дерева, включая листья, выполняются те же ограничения на количество ключей и указателей (в зависимости от порядка дерева), что и в В-дереве. 2) Все ключи в В+ дереве хранятся в листьях. Для обеспечения правильного доступа отдельные ключи могут дублироваться и в промежуточных вершинах индексов. 3) Доступ к информации в В+ дереве выполняется всегда за h шагов, где h – высота В+ дерева. 4) Выполнение операций включения и удаления в В+ дереве несколько отличается от выполнения соответствующих операций в В-дереве. Операция вставки в B+ дерево: В+ дерево также растет от листьев к корню. Включение начинается с листьев. Также в случае переполнения выполняется расщепление вершины, но в В+ дереве по-разному выполняется расщепление листа и расщепление промежуточной вершины дерева. При расщеплении листа в В+ дереве ключ, расположенный в средней позиции листа, перемещается в родительскую вершину и остается в листе – в правом или левом, но в каком-то одном для всех операций вставки. Расщепление промежуточной вершины В+ дерева выполняется точно так же, как и в В- дереве. 1) Включение первых двух элементов ничем не отличается от их включения в В-дерево; 2) Включение третьего элемента вызывает переполнение листа: 12, 20, 48. Элемент из средней позиции перемещается в родительскую вершину, в результате чего создается новый корень В+ дерева. Но так как в В+ дереве все ключи должны находиться в листьях, перемещаемый элемент остается и в одном из двух листьев – например, в левом (примем для определенности). 3) Включение следующего элемента (3) также вызывает переполнение левого листа: 3, 12, 20. Элемент из средней позиции перемещается в родительскую вершину, в которой есть свободная позиция, и остается в левом листе 4) Элемент 5 также должен быть размещен в левом листе – возникает переполнение: 3, 5, 12. В результате расщепления вершины элемент из средней позиции перемещается в родительскую вершину, в которой возникает переполнение: 5, 12, 20, и сохраняется в левом листе. Переполнение родительской вершины обрабатывается по правилам В- дерева – образуются две вершины с элементами 5 в левой и 20 в правой, а элемент 12 перемещается в родительскую вершину – создается новый корень В+ дерева 5) Элемент 70 должен быть размещен в самом правом листе – в нем есть свободная позиция, поэтому реорганизация дерева не происходи 6) Включение последнего элемента (101) вызывает переполнение: 48, 70, 101. В результате расщепления вершины появляются два новых листа, элемент 70 сохраняется в левом листе и дублируется в родительской вершине, в которой есть свободная позиция 31. Правила удаления значения из В+ дерева. В+ - дерево – это особый вид сбалансированного m - арного дерева, которое позволяет выполнять операции поиска, вставки и удаления записей из внешнего файла с гарантированной производительностью для самой неблагоприятной ситуации. С формальной точки зрения В+ - дерево порядка m представляет собой m - арное дерево поиска, характеризующееся следующими свойствами: • Корень является листом, либо имеет по крайней мере двух сыновей. • Каждый узел, за исключением корня и листьев, имеет от (m/2) до m сыновей. • Все пути от корня до любого листа имеют одинаковую длину. • Указатели на записи файла с данными хранятся только в листьях. В+ - дерево можно рассматривать как иерархический индексный файл, каждый узел в котором занимает блок во внешней памяти. Корень В+ - дерева является индексом первого уровня. Каждый внутренний узел в В+ - дереве имеет форму (p0, key1, p1, key2, p2 , . . . ,keyn, pn), где рi является указателем на i - го сына, 0 i n, а keyi – ключ, 1 i n. Ключи в узле упорядочены, поэтому key1 < key2 < . . . < keyn. Все ключи в поддереве, на которые указывает р0, меньше, чем k1. В случае 1 i < n все ключи в поддереве, на которое указывает рi, имеют значения не меньше, чем, keyi, и меньше, чем keyi+1. Все ключи в поддереве, на которое указывает pn, имеют значения, не меньшие, чем keyn. |