Einer der weitest verbreiteten Mythen sagt, dass ein Index im Laufe der Zeit degeneriert und in regelmäßigen Abständen neu aufgebaut werden muss (rebuild). Dazu muss man zuerst sagen, dass die Datenbank den Index immer in der Balance hält – wirklich immer. Es ist unmöglich, dass ein einzelner Zweig des Baumes tiefer wächst als andere.
Was jedoch passieren kann, ist, dass der Index größer wird als unbedingt notwendig. Wenn zum Beispiel viele update oder delete Anweisungen ausgeführt werden, kann es vorkommen, dass der Index „löchrig“ wird. Doch selbst wenn der Index doppelt so groß wird, heißt das nicht, dass der Index-Baum in die Tiefe wächst. Das logarithmische Wachstum bewirkt, dass der Index-Baum erst wächst, wenn der Index zum Beispiel hundertmal größer wird. Das wurde bereits in „Der Suchbaum (B-Tree) macht den Index schnell“ erklärt. Das heißt, dass das Durchwandern des Baumes selbst dann nicht langsamer wird, wenn sich die Index-Größe durch Löcher verdoppelt.
