В-дерево

Cтраница 3

Оно состоит из двух частей: последовательного индекса, содержащего указатели всех записей файла, и В-дерева, выступающего в качестве многоуровневого указателя на элементы последовательного индекса. [31]

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

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

Тогда, чтобы начать обработку, достаточно записать trav ( root), считая, что root является указателем на корень В-дерева. [34]

Если используемая система поддерживает виртуальную память, проведите эксперименты с целью определения значения Л /, обеспечивающего наименьшее время выполнения для реализации В-дерева, которое поддерживает случайные операции insert в очень большой таблице символов. Прежде чем выполнять подобные эксперименты, которые могут потребовать больших затрат, возможно, стоит изучить основные характеристики используемой системы. [35]

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

Эта команда допустима в том случае, когда для ключей определен порядок, например, когда используется индекс, организованный в виде В-дерева, а отнюдь не тогда, когда используется рандомизирующее хеширование. [37]

Если записи главного файла большие, то общее число блоков в плотном индексе может быть существенно меньшим, чем потребовалось бы для разреженного индекса или В-дерева, построенных для главного файла. Кроме того, нет необходимости в таком большом числе участков или среднем числе блоков на участок для хешировании. [38]

Способ организации динамической иерархической структуры данных, реализованный в ИНЕС, обеспечивает эффективность работы, равную эффективности работы с одноуровневым массивом, организованным в виде В-дерева. [39]

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

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

Там же доказывается сложность 1ок logn для интерполяционного поиска. В-дерево, используемое в качестве плотного индекса, описанного в разд. Я [178] анализирует математическое ожидание заполнения 2 - 3 деревьев ( Й - деревьсв с двумя или тремя сыновьями на узел) и показывает, что в среднем внутренние узлы имеют примерно между 21 и 30 % неиспользуемого пространства. [42]

Пример В-дерева. Порядок п 2. Для наглядности использованы числовые значения ключей из диапазона 1 - 31. Число ключей в корне от 1 до 4, число ключей в других узлах от 2 до 4. [43]

Ниже будет показано, что структура В-дерева имеет смысл для организации поиска во внешней памяти только при относительно больших значениях порядка дерева, а ( 2 - 3) - деревья больше подходят для поиска в оперативной памяти. В-дерево порядка п 2 выбрано в качестве примера только для уменьшения и упрощения рисунка. Поскольку В-дерево является сильно ветвящимся деревом, его высота невелика, поэтому и число обращений к внешней памяти при поиске также невелико. Кроме того: 1) сравнительно просто может быть реализован последовательный доступ, поскольку листья расположены на одном уровне; 2) при добавлении и удалении ключей изменения ограничиваются, как правило, одним узлом, а не затрагивают всю структуру дерева, поскольку во всех узлах есть свободные поля, максимальное число которых, за исключением корня, составляет п ( 2п) / 2; 3) область влияния изменений оказывается очень узкой даже в случае, когда изменения затрагивают всю структуру дерева, так как участок, на котором сказываются изменения, располагается между непосредственным исходным и его предком. [44]

Пример плотного индекса се только для значения ключа первой записи блока. Пример плотного индекса представлен на Над плотным индексом также можно построить В-дерево. [45]

Страницы: 1 2 3 4