LDT: A Logarithmic Distributed Search Tree.
Panayiotis Bozanis, Yannis Manolopoulos · 2002
We propose LDT, a new Scalable Distributed Search Tree for the dictionary problem, as an alternative to both random trees and deterministic height balanced trees. Our scheme exhibits logarithmic update time, either constant or logarithmic search time for single key queries and output sensitive query time for range search query, depending whether one affords linear or O(n log n) space overhead.