Wo binäre Suche schneller, mit Array oder StringList?

[Namenloser]

Zitat von Dejan Vu:

Zitat von Namenloser:

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.

Zitat von Dejan Vu:

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.

Zitat von Dejan Vu:

Zitat von Namenloser:

...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.