Der normale Standard-Index ist bei gängigen Datenbanken immer ein balancierter Baum, wenn man nichts anderes spezifiziert.
Ein B-Baum ist aber kein 'balancierter Baum' (na ja, irgendwie schon).
Natürlich ist der balanciert?
Erfüllt genau die Definition von Wikipedia: „Ein balancierter Baum (englisch oft self-balancing tree) ist in der Informatik ein Spezialfall der Datenstruktur Baum, der eine maximale Höhe von c⋅log(n) garantiert, wobei n die Anzahl der Elemente im Baum angibt und c eine von n unabhängige Konstante ist.“
Außerdem muss es ja nicht zwangsläufig ein B-Baum sein. Ich weiß nicht, was da in der Praxis zum Einsatz kommt. Auch wenn es gut sein kann, dass es tatsächlich ein B-Baum ist. Auf jeden Fall ist es aber ein balancierter Baum.
Geht das mit SQLite? Ich würde zeit BETWEEN t1 and t2
nehmen.
Keine Ahnung, ich mach nur alle paar Jahre mal was mit
SQL.
...fast gleich schnell (O(log n))
Die Basis des Logarithmus ist aber sehr groß: PageSize div SizeOf(Key). Das geht gegen O(1).
Ja, „fast gleich schnell“ in der Praxis.