Использование key-search с дублируемыми ключами

Дублируемые ключи часто называют дуплетами. При поиске ключа в B-де-

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

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

тот же ключ, что и предикат key_search. Если Турбо Пролог гарантирует,

что выбранный ключ всегда первый из идентичных ключей, то предикат

key_search станет очень медленным во всех деревьях. Чтобы найти первый из

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

key_search:

predicates

keysearch_dupl(db_selector, bt_selector, string, ref)

first_dupl(db_selector, bt_selector, string, ref, ref)

try_prev(db_selector, bt_selector, ref, string)

clauses

keysearch_dupl(Db_selector, Bt_selector, Key, Ref) :-

key_search(Db_selector, Bt_selector, Key, Relf),

first_dupl(Db_selector, Bt_selector, Key, Refl, Ref).

first_dupl(Db_selector, Bt_selector, Key, _, Ref) :-

try_prev(Db_selector, Bt_selector, Ref, Key), !,

first_dupl(Db_selector, Bt_selector, Key, Relf, Ref).

first_dupl(_, _, _, Ref, Ref).

try_prev(Db_selector, Bt_selector, Ref, OldKey) :-

key_prev(Db_selector, Bt_selector, Ref),

key_current(Db_selector, Bt_selector, NewKey, _),

NewKey=OldKey, !.

try_prev(Db_selector, Bt_selector, _, _,) :-

key_next(Db_selector, Bt_selector, _),

fail.