B-деревья.

B-дерево является структурой данных, которую можно применять для

очень эффективного метода сортировки больших количеств данных; B-деревья

дают возможность использовать эффективный алгоритм поиска. B-деревья ана-

логичны указателям базы данных, вот почему B-деревья иногда сравнивают с

указателями.

В Турбо Прологе B-деревья находятся во внешней базе данных. Каждый

вход в B-дерево это пара величин: ключевая строка и связанный с ней ука-

затель базы данных. При создании вашей базы данных вы, сначала, заводите

в ней запись и вырабатываете ключ для этой записи. Затем Турбо Пролог

включает этот ключ и указательный номер, соответствующий этой записи, в

B-дерево.

При поиске записи в базе данных все, что вам необходимо сделать, это

применить ключ для этой записи, и B-дерево выдаст вам соответствующий

указатель. Используя этот указатель, вы можете выбрать запись из базы

данных. По мере развития B-дерева его входы содержаться в порядке, опре-

деляемом ключами. Это значит, что вы можете легко получить отсортирован-

ный список записей.

B-дерево подобно бинарным деревьям, за исключением того, что в B-де-

реве более чем одна ключевая строка запоминается в каждом узле. B-деревья

сбалансированы; это значит, что пути поиска каждого ключа в "листьях" де-

рева имеют одну и ту же длину. Вследствие этого поиск каждого ключа, сре-

ди более чем миллиона ключей, требует только нескольких операций доступа

к диску, в зависимости от того, как много ключей запоминается в каждом

узле.

Хотя B-деревья помещаются во внешних базах данных, они не нуждаются

в указателях на термы в той же самой базе данных. Есть возможность иметь

базу данных содержащую ряд цепочек и другую базу данных с B-деревом, ука-

зывающим на термы в этих цепочках.

Страницы, порядок и длина ключа.

В B-дереве ключи сгруппированы в страницы, причем каждая страница

имеет свой размер и все страницы могут содержать одно и то же число клю-

чей, это значит что все ключи B-дерева должны иметь одинаковый размер.

Размер ключей определяется аргументом KeyLen, который вы должны опреде-

лить в момент создания B-дерева. При попытке внесения в B-дерево строки

длиннее чем KeyLen, Турбо Пролог обрежет их. В общем вы должны выбрать

минимально возможную величину для KeyLen в целях экономии памяти и увели-

чения быстродействия.

В момент создания B-дерева необходимо создать величину аргумента

Order. Этот аргумент определяет сколько ключей должно запоминаться в каж-

дом узле дерева. Наименьшая величина аргумента выбирается методом проб и

ошибок. Хорошее первое приближение для Order это 4, что соответствует за-

поминанию от 4 до 8 ключей в каждом узле. Вы можете выбрать величину

Order экспериментально, так как скорость поиска в B-дереве зависит от ве-

личин KeyLen и Order, числа ключей в B-дереве и конфигурации вашей вычис-

лительной системы.

Двойные ключи.

В момент определения B-дерева вы должны предусмотреть все повторяю-

щиеся включения вашего ключа. Например, если вы создаете B-дерево для ба-

зы данных покупателей, в которой ключем является фамилия покупателя, вам

необходимо учесть всех покупателей с фамилией Смит. Для этого можно ис-

пользовать двойные ключи B-дерева. При использовании стандартного преди-

ката key_search для поиска в базе данных, Турбо Пролог ищет соответствую-

щий ключ в B-дереве и возвращает соответствущий ему указатель базы дан-

ных.

После этого можно использовать стандартные предикаты key_next и

key_prev для нахождения указателей, соответствующих последующим и преды-

дущим ключам, т.е. другим Смитам в B-дереве. Когда вы удаляете терм из

базы данных, необходимо удалить соответствующий вход в B-дерево путем за-

дания как ключа, так и указателя базы данных.