Then you must have a look at the amazing elastic binary trees used in haproxy, the article describes their properties quite well in terms of binary search: https://wtarreau.blogspot.com/2011/12/elastic-binary-trees-e...

These were featured at QCon last June by one of their authors. Really great work.