Внешние деревья поиска

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

Обобщением дерева двоичного поиска является m -арное дерево, в котором каждый узел имеет не более m сыновей. Так же, как и для деревьев бинарного поиска, для m -арного дерева считается, что выполняется следующее условие: если и являются двумя сыновьями одного узла, и находится слева от тогда все элементы, исходящие вниз от оказываются меньше элементов, исходящих вниз от Операции поиска, вставки и удаления элементов для m -арного дерева поиска реализуются путем обобщения аналогичных операция для деревьев бинарного поиска.

Однако для внешних деревьев поиска важна проблема хранения записей в файлах, когда файлы хранятся в виде блоков внешней памяти. Правильным применением идеи разветвленного дерева является представление об узлах как о физических блоках. Внутренний узел содержит указатели на своих m сыновей, а также m -1 ключевых значений, которые разделяют потомков этих сыновей. Листья также являются блоками, а они содержат записи основного файла.

Если использовать дерево двоичного поиска из n узлов для представления файла, хранящегося во внешней памяти, то для поиска записи в таком файле потребуется в среднем обращений к блокам. Если вместо бинарного дерева поиска использовать для представления файла m -арное дерево поиска, то для поиска записи в таком файле потребуется обращений к блокам. В случае n=1000000 дерево бинарного поиска потребовало бы примерно 20 обращения к блокам, тогда как 128-арное дерево поиска потребовало бы лишь 3 обращений к блокам. Однако нельзя сделать m очень большим, поскольку, чем больше m, тем больше должен быть размер блока. Кроме того, считывание и обработка более крупного блока занимают больше времени, поэтому существует оптимальное значение m, которое позволяет минимизировать время, требующееся для просмотра внешнего m -арного дерева поиска.

В-деревья

В-дерево – это особый вид сбалансированного m -арного дерева, который позволяет выполнять операции поиска, вставки и удаления записей из внешнего файла с гарантированной производительностью для самой неблагоприятной ситуации.

В-дерево порядка m представляет собой m -арное дерево поиска, характеризующееся следующими свойствами.

1. Корень либо является листом, либо имеет хотя бы двух сыновей.

2. Каждый узел, за исключением корня и листьев, имеет от m/2 до m сыновей.

3. Все пути от корня до любого листа имеют одинаковую длину.

На рис. 52 показано В-дерево порядка 5, здесь предполагается, что в блоке листа помещается не более трех записей.

Рис. 52 – В-дерево порядка 5

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

Существует несколько способов организации листьев. В данном случае предполагается, что записи основного файла хранятся только в листьях, и каждый лист занимает один блок.

Не нашли, что искали? Воспользуйтесь поиском: