Käänteistiedosto B-puulla

Jos tekstiä päivitetään paljon, voidaan käänteistiedosto toteuttaa B-puilla. Tällöin haut, sekä uusien avainsanojen lisäykset ja vanhojen poistot voidaan toteuttaa $O(\log n)$ ajassa, missä $n$ on käänteistiedoston kaikkien avainsanojen lukumäärä. B-puu toteutus tarvitsee järjestettyyn taulukkoon verrattuna enemmän tilaa. Mikäli jokaisesta B-puun solmusta on linkki solmun vasempaan lapseen, solmun oikeaan lapseen ja solmun tekstiin, on B-puun tilavaatimus $(3*4)a=12a$.