В-дерево

Cтраница 2

Чтобы разделить узел в В-дереве, мы создаем новый узел, перемещаем большую половину ключей в новый узел, а затем изменяем значения счетчиков и устанавливаем служебные ключи в середине обоих узлов. В этой программе предполагается, что значение М является четным, а в каждом узле имеется лишняя позиция для элемента, который вызывает разделение. Другими словами, максимальное количество ключей в узле равно М-1, и когда количество ключей в узле достигает значения М, узел разделяется на два узла с М / 2 ключей в каждом. [16]

Результат удаления ключа 29 из В-дерева, показанного на Случай почти аналогичен представленному на, за исключением того, что ключ 30 претерпевает более сложное перемещение. [17]

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

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

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

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

Графовое представление бинарных моделей дает структуру так называемого В-дерева в отличие от Е - дерева - иерархической структуры общего вида. [22]

Лемма 16.2 Для выполнения поиска или вставки в В-дереве порядка М, содержащем N элементов, требуется от log N до logu / iN зондировании - число, которое на практике можно считать постоянным. [23]

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

В программе 16.1 приведены определения типа для узлов рассматриваемой реализации В-дерева. Мы не указываем подробно структуру узлов, что следовало бы сделать в реальной реализации, поскольку для этого потребовалась бы ссылка на конкретные страницы диска. Для простоты мы используем один тип узлов, когда каждый узел состоит из массива записей, каждая из которых содержит элемент, ключ и связь. Каждый узел содержит также счетчик, указывающий количество активных записей. [25]

Реализуйте операцию remove для таблицы символов, основанной на применении В-дерева, при использовании простого метода, когда указанный элемент удаляется из внешней страницы ( возможно, допустив, чтобы количество элементов на странице становилось меньше М / 2), но чтобы изменение не распространялось вверх по дереву, за исключением, возможно, настройки значений ключей, если удаленный элемент оказался наименьшим на данной странице. [26]

В-дерева, по-видимому, оказываются более эффективными, чем простая схема В-дерева с участками. [27]

Ph, но, поскольку общее число ключей, содержащихся в В-дереве от корня до ( i - 1) - го уровня, относится к числу ключей, содержащихся на i - м уровне, как число, заключенное между п и 2п, к единице, поиск в большинстве случаев продолжается до листьев. [28]

При этом очевидно, что максимальный размер стека не будет больше высоты В-дерева. [29]

В этой версии рис. 16.8 показано, как страницы заполняются во время процесса роста В-дерева. Когда вставка приходится на полную страницу, страница разделяется на две полупустые страницы. [30]

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