Die Suche/Einfügen/Löschen ist in einen B-Baum mit b-Einträge pro Knoten in schlechtesten Fall in O(b_log n) Schritten geschafft. Der B+ Baum hat sogar den Vorteil, dass nur die Blätter echte Daten enthalten und in einer linearen Liste verkettet sind, so dass eine Speicherung nur O(n) Speicherplatz braucht.
Dieses Video zeigt, wie ein B-Baum erstellt wird
http://youtube.com/watch?v=coRJrcIYbF4
Also warum sollte so ein Kunststück fehlen sollen?