Der wesentlich Unterschied der beiden Datenstrukturen besteht darin, dass bei B*-Bäumen die Daten in den Blättern stehen und die übrigen Knoten nur Schlüssel als Wegweiser zum Auffinden der Elemente enthalten. In B-Bäumen enthalten dagegen alle Knoten Schlüssel und Daten.
Obwohl alle Daten in den Blättern stehen ist die direkte Suche in B*-Bäumen schneller, da die Höhe h* durch den höheren Verzweigungsgrad i. A. kleiner als die Höhe h in B-Bäumen ist. Durch die Verkettung der Blattseiten bei B*-Bäumen ist auch eine sequentielle Suche einfacher durchführbar als in B-Bäumen.
Das Löschen ist in B*-Bäumen ebenfalls einfacher: Da alle Datenelemente in den Blättern stehen, muss nicht zwischen dem Löschen aus inneren Knoten und Blattknoten unterschieden werden. Beim Löschen eines Schlüssel aus einem Blatt muss dieser meist nicht aus dem Indexteil entfernt werden und behält seine Funktion als Wegweiser.
Das Einfügen läuft nahezu analog ab. Wird jedoch eine Blattseite gesplittet muss im B*-Baum noch gewährleistet werden, dass der mittlere Schlüssel als Wegweiser in den Vaterknoten geschrieben wird.
Als Nachteil von B*-Bäumen ist der geringfügig höhere Speicherbedarf durch Verdopplung einiger Elemente in den Indexknoten zu nennen.