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

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

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

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

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

Дата добавления: 2015-07-16