Naja, wenn man etwas schielt, ist die binäre Suche in einem sortierten Vector/Array eine Suche in einem Binärbaum. Damit hat man
maximal log_2(4096) =
12 Schritte, um einen Eintrag zu finden.
Den Vorteil hat man dann aber nur beim Suchen, beim Einfügen/Löschen können Kopieroperationen teuer werden.
Dabei kommt es natürlich auch darauf an, wie die anderen Datenstrukturen verwaltet werden.
Ein Baum, der durch seine Verteilung im Speicher auch nur einen Pagefault mehr auslöst, sollte dadurch für mostly-read-Fälle deutlich unattraktiver werden
