Алгоритм верхних узлов — это алгоритм управления календарем резервирования ресурсов. Алгоритм был впервые опубликован в 2003 г. [1] и был улучшен в 2009 г. [2] Он используется, когда ресурс используется совместно многими пользователями (например , полоса пропускания в телекоммуникационном канале или емкость диска в большом центре обработки данных ). ).
Календарь хранится в виде двоичного дерева, листья которого представляют собой элементарные периоды времени. Другие узлы представляют период времени, охватываемый всеми их потомками.
Период времени, охватываемый резервированием, представлен набором «верхних узлов». Этот набор является минимальным набором узлов, которые точно покрывают период времени резервирования.
Преимущество этого алгоритма в том, что время регистрации нового резервирования ресурса зависит только от размера календаря (оно не зависит от общего количества резервирований).