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