В-дерево
Cтраница 4
Для осуществления последовательного поиска блоки первого уровня могут быть связаны в цепь по возрастанию значения ключа. Поиск в В-дереве выполняется так же, как и в неплотном индексе. Удачный и неудачный поиск записи в В-дереве требует Л - обменов, где h - число уровней В-дерева. [46]
 |
Физическая структура глобального массива А. [47] |
Как следует из вышеприведенных определений, физическая структура глобальных данных не совпадает с их логической структурой. Система автоматически строит для такой структуры сбалансированное В-дерево. [48]
Поименованный ключ может содержать один или несколько элементов данных, объявленных во фразе KEY. Обычно такая методика поддерживается индексом или В-деревом, которые ассоциируют значения ключа с DBKEY. При поиске выдается запись указанного типа с минимальным соответствующим значением ключа. [49]
Процедурная компонента системы содержит функции создания структур данных, поддержки корректности базы знаний, наследования свойств и ряд других функций. Для обеспечения поиска по именам элементов типа вершина и атрибут в системе реализовано В-дерево. Доступ ко всем элементам базы осуществляется через виртуальную память. Каждый элемент имеет внутренний идентификатор, по значению которого однозначно определяется его размещение в оперативной или внешней памяти. Для работы с объектами, отсутствующими в оперативной памяти, осуществляется их динамический перенос из внешней памяти в оперативную. Это позволяет системе работать на компьютере с ограниченным объемом оперативной памяти. [50]
Функциональная модель данных использует такой подход для определения объекта. Вместо того чтобы представлять объект записью с определенным содержанием или же кортежем в В-дереве, функциональная модель сообщает, какие функции ( или операции) определены на этом объекте. Представление объекта - это дело реализации, и оно определяется на более низком уровне абстракции. Этот же принцип используется в предложениях ANSI / SPARC ( Комитета по планированию Американского национального института стандартов) по отделению деталей кодасиловских структур хранения данных от концептуальной схемы ( см. гл. [51]
 |
Массив А после второго добавления нового узла. [52] |
Самой оптимальной физической структурой является такая, которая использует минимальное количество дисковой памяти и обеспечивает быстрый поиск глобальных данных. Это означает, что пользователь должен стремиться к тому, чтобы на низшем уровне данных создавалось как можно меньше физических блоков, поскольку рост их числа ведет не только к сокращению числа свободных блоков на диске, но и к увеличению количества уровней в В-дереве, что в значительной степени сказывается на скорости доступа к глобальным данным. [53]
Ниже будет показано, что структура В-дерева имеет смысл для организации поиска во внешней памяти только при относительно больших значениях порядка дерева, а ( 2 - 3) - деревья больше подходят для поиска в оперативной памяти. В-дерево порядка п 2 выбрано в качестве примера только для уменьшения и упрощения рисунка. Поскольку В-дерево является сильно ветвящимся деревом, его высота невелика, поэтому и число обращений к внешней памяти при поиске также невелико. Кроме того: 1) сравнительно просто может быть реализован последовательный доступ, поскольку листья расположены на одном уровне; 2) при добавлении и удалении ключей изменения ограничиваются, как правило, одним узлом, а не затрагивают всю структуру дерева, поскольку во всех узлах есть свободные поля, максимальное число которых, за исключением корня, составляет п ( 2п) / 2; 3) область влияния изменений оказывается очень узкой даже в случае, когда изменения затрагивают всю структуру дерева, так как участок, на котором сказываются изменения, располагается между непосредственным исходным и его предком. [54]
 |
Использование косвенности в страницах. [55] |
Он может быть организован как плотный индекс, описанный в разд. Внутренние узлы этого В-дерева представляют собой страницы, заполненные парами, состоящими из указателей на другие страницы и ассоциированных с ними значений атрибутов, по которым определяется индекс. Узлы, являющиеся листьями, состоят из значений таких атрибутов и связанных с ними списков идентификаторов кортежей. Существует один идентификатор кортежа в списке для каждого кортежа, имеющего заданные значения атрибутов из индекса. Идентификаторы кортежей являются, по существу, указателями на кортежи, но они обеспечивают некоторую степень косвенности. Фактически идентификаторы кортежей указывают на некоторое место в нижней части страницы, где может находиться сам указатель на кортеж. Действительно, такая степень косвенности позволяет интерпретировать кортежи как незакрепленные записи, даже если на них ссылаются указатели из В-дерева. На рис. 4.10 показан пример страницы. [56]
Для осуществления последовательного поиска блоки первого уровня могут быть связаны в цепь по возрастанию значения ключа. Поиск в В-дереве выполняется так же, как и в неплотном индексе. Удачный и неудачный поиск записи в В-дереве требует Л - обменов, где h - число уровней В-дерева. [57]
Таким образом, указатель р в вершине-предке заменяется на последовательность р, W [ mi2 ], p, что в свою очередь может привести к расщеплению. Если нужно расще - пить корень дерева, который не имеет предка, то просто создают новый корень и помещают в него единственное слово W [ m / 2i, в таком случае дерево становится на единицу выше. Данная процедура включения слов сохраняет все свойства В-дерева. [58]
Страницы: 1 2 3 4