B-деревья.

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

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

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

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

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

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

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

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

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

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

B-дерево.

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

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

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

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

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

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

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

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

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

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

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

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

узле.

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

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

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

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