В-дерево
Cтраница 1
В-дерево имеет более сложную структуру, чем бинарное дерево поиска. Известно несколько разновидностей этой структуры, что расширяет диапазон практического применения В-деревьев. [1]
 |
Сравнительная оценка методов доступа ФАЙЛЫ С ЗАПИСЯМИ ПЕРЕМЕННОЙ ДЛИНЫ. [2] |
В-дерева, по-видимому, оказываются более эффективными, чем простая схема В-дерева с участками. [3]
В-дерево отличается от индексно-последовательной организации весьма существенным образом: оно не требует явной реорганизации при вставке новых или удалении старых записей. [4]
В-дерево порядка 3 носит отдельное название 2 - 3-дерева. [5]
Определение 16.2 В-дерево порядка М - это дерево, которое либо пусто, либо состоит из k - узлов с k - 1 ключами и k связями с деревьями, представляющими каждый из k ограниченных ключами интервалов, и обладающее следующими структурными свойствами: k должно находиться в интервале между 2 и М для корня и между М / 2 и М для любого другого узла; все связи с пустыми деревьями должны находиться на равном расстоянии от корня. [6]
Лемма 16.3 В-дерево порядка М, сконструированное из N случайных элементов, предположительно должно иметь около IA4N / M страниц. [7]
Модифицируйте реализацию В-дерева, приведенную в разделе 16.3 ( программы 16.1 - 16.3), чтобы она работала в среде, в которой таблица размещается на внешнем устройстве хранения информации. Если система допускает произвольный доступ к файлам, поместите всю таблицу в один ( очень большой) файл и в структуре данных вместо указателей используйте смещение внутри файла. Если система допускает непосредственное обращение к страницам на внешних устройствах, в структуре данных вместо указателей используйте адреса страниц. Если система допускает оба вида доступа, выберите подход, который, по вашему мнению, наиболее подходит для реализации очень большой таблицы символов. [8]
Покажите организацию В-дерева для файла, если вставлены пятнадцать записей в порядке их ключей. [9]
 |
Зависимость высоты В-дерева от его порядка п и числа ключей N. [10] |
Следовательно, для любого В-дерева высоты h любой ключ может быть найден не более чем за h шагов поиска. [11]
Каждый узел в В-дереве содержит массив и счетчик количества активных записей в массиве. Каждая запись массива представляет собой ключ, элемент и связь с узлом. Во внутренних узлах используются только ключи и связи; во внешних узлах используются только ключи и элементы. [12]
Поскольку большая часть ключей В-дерева содержится в листьях, то основные затраты при работе алгоритма trav приходятся на спуск вниз по дереву и однородную последовательную обработку ключей, расположенных в листьях. Однако нельзя пренебречь и затратами, связанными с возвратом на более высокий уровень дерева, так как для этого требуется обращение к внешней памяти. В - дерево, рассматриваемое далее, свободно от этого недостатка и является одной из разновидностей В-дерева. [13]
Многие вариации базовой абстракции В-дерева приходят на ум немедленно. Один класс вариаций позволяет экономить время за счет упаковки во внутренние узлы максимально возможного количества ссылок страниц, в результате чего коэффициент ветвления повышается, а дерево становится более плоским. Как уже отмечалось, в современных системах преимущества, получаемые в результате таких изменений, ограничены, поскольку стандартные значения параметров позволяют реализовать операции search и insert при помощи всего двух зондирований - эффективность, которую вряд ли удастся повысить. Другой класс вариантов повышает эффективность использования дискового пространства, перед разделением объединяя узлы с их родственными узлами. Упражнения 16.13 - 16.16 посвящены такому методу, который при работе со случайными ключами позволяет уменьшить дополнительно используемый объем дискового пространства с 44 до 23 процентов. Как обычно, выбор того или иного варианта зависит от свойств приложения. Помня о широком множестве различных ситуаций, в которых применимы В-деревья, мы не будем подробно рассматривать эти вопросы. [14]
Найдем путь от корня В-дерева к некоторому листу, в котором будет находиться требуемая запись, если она существует. [15]
Страницы: 1 2 3 4