Я вот все никак до конца не могу догнать (чисто теоритически) - как наш
любимый сервер может параллельно удалять элементы из этого дерева.
с чего ты взял, что он может? добавление и удаление ключа в дереве -
монопольная операция.
Я взял с того, что Влад, чуть менее двух лет назад тут сказал, что дерево
полностью никогда не блокируется. Только соседние страницы обрабатываемого
нода.
Да и в "учебниках" по алгоритмам говорится, что это возможно.
Но, сцуко, не говорится как конкретно :-)
Коваленко Дмитрий.
